Lower Bounds On Communication Complexity In Distributed Computer Networks
- 25 August 2005
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 109-117
- https://doi.org/10.1109/sfcs.1984.715907
Abstract
We prove that for almost all boolean functions f , the conmunication complexity of f on a linear array with p+1 processors is approximately p times its commuication complexity on a system with two processors. We use this result to develop a technique for establishing lower bounds on communication complexity on general networks by simulating them on linear arrays. Using this technique, we derive optimal lower bounds for ranking, distinctness, uniqueness and triangle-detection problems on the ring. The application of this technique to meshes and trees yields nontrivial near optimal lower bounds on the communicaton complexity of ranking and distinctness problems on these networks.Keywords
This publication has 11 references indexed in Scilit:
- Communication complexityJournal of Computer and System Sciences, 1984
- The impact of synchronous communication on the problem of electing a leader in a ringPublished by Association for Computing Machinery (ACM) ,1984
- Lower bounds on communication complexityPublished by Association for Computing Machinery (ACM) ,1984
- Information Transfer in Distributed Computing with Applications to VLSIJournal of the ACM, 1984
- On notions of information transfer in VLSI circuitsPublished by Association for Computing Machinery (ACM) ,1983
- Communication complexityPublished by Association for Computing Machinery (ACM) ,1982
- Communication Issues in the Design and Analysis of Parallel AlgorithmsIEEE Transactions on Software Engineering, 1981
- Lower Bounds on Information Transfer in Distributed ComputationsJournal of the ACM, 1980
- Area-time complexity for VLSIPublished by Association for Computing Machinery (ACM) ,1979
- Contentment in graph theory: Covering graphs with cliquesIndagationes Mathematicae, 1977