Distributed sorting on local area networks

1 January 1988

journal article
Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers

Vol. 37 (2) , 239-243
https://doi.org/10.1109/12.2156

Abstract

[[abstract]]A straight-line-topology local area network (LAN) to which a number of nodes are connected either in series or in parallel is considered. A file F is arbitrarily partitioned among these sites. The problem studied is that of rearranging the records of the file such that the keys of records at lower-ranking sites are all smaller than those at higher-ranking sites. Lower bounds on the worst-case communication complexity are given for both the series and parallel arrangements, and algorithms optimal for all networks and files are presented.[[fileno]]2030209030073[[department]]資訊工程學

Keywords

This publication has 6 references indexed in Scilit:

Shout echo selection in distributed files
Networks, 1986
Optimal Distributed Algorithms for Sorting and Ranking
IEEE Transactions on Computers, 1985
Distributed Sorting
IEEE Transactions on Computers, 1985
Ordering subscribers on cable networks
ACM Transactions on Computer Systems, 1984
The complexity of sorting on distributed systems
Information and Control, 1984
Finding the median distributively
Journal of Computer and System Sciences, 1982