Lower bounds on communication complexity in distributed computer networks
- 1 October 1987
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 34 (4) , 921-938
- https://doi.org/10.1145/31846.32978
Abstract
The main result of this paper is a general technique for determining lower bounds on the communication complexity of problems on various distributed computer networks. This general technique is derived by simulating the general network by a linear array and then using a lower bound on the communication complexity of the problem on the linear array. Applications of this technique yield optimal bounds on the communication complexity of merging, ranking, uniqueness, and triangle-detection problems on a ring of processors. Nontrivial near-optimal lower bounds on the communication complexity of distinctness, merging, and ranking on meshes and complete binary trees are also derived.Keywords
This publication has 6 references indexed in Scilit:
- Communication complexityJournal of Computer and System Sciences, 1984
- The complexity of sorting on distributed systemsInformation and Control, 1984
- Information Transfer in Distributed Computing with Applications to VLSIJournal of the ACM, 1984
- Communication Issues in the Design and Analysis of Parallel AlgorithmsIEEE Transactions on Software Engineering, 1981
- On the Complexity of VLSI ComputationsPublished by Springer Nature ,1981
- Lower Bounds on Information Transfer in Distributed ComputationsJournal of the ACM, 1980