Lower Bounds on Communication Complexity in Distributed Computer Networks (Preliminary Version)

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.

Authors

• Prasoon Tiwari

Keywords

• Complexity theory
• Intelligent networks
• Computer networks
• Distributed computing
• Optical computing
• Computer simulation
• Coordinate measuring machines
• Electric variables measurement
• Distributed algorithms
• Repeaters
• Lower Bound
• Proof Of Theorem
• Set Of Elements
• Lower Error
• Perfect Match
• Linear Array
• Rank Of Matrix
• Complex Communication
• Binary Tree
• Upper Triangular
• Case Of Theorem
• Linkage System
• Distinct Vertices