
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

A Time and CommunicationOptimal Distributed Sorting Algorithm in a Line Network and Its Extension to the Dynamic Sorting Problem
Atsushi SASAKI
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E87A
No.2
pp.444453 Publication Date: 2004/02/01
Online ISSN:
DOI:
Print ISSN: 09168508 Type of Manuscript: PAPER Category: Algorithms and Data Structures Keyword: distributed algorithms, sorting, time complexity, communication complexity, dynamic sorting, line network,
Full Text: PDF>>
Summary:
This paper presents a strictly time and communicationoptimal distributed sorting algorithm in a line network. A strictly timeoptimal distributed sorting algorithm in a line network has already been designed. However, its communication complexity is not strictly optimal and it seems to be difficult to extend it to other problems, such as that related to multiple elements in a process, and also the dynamic sorting problem where the number of elements each process should have as its solution is not the same as that in the initial state. Therefore, the algorithm in this paper was designed by an alternative approach to make it strictly time and communicationoptimal. Moreover, an extension to the dynamic sorting problem is described.

