Publication
Journal of the ACM
Paper

Lower Bounds on Communication Complexity in Distributed Computer Networks

Download paper

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. © 1987, ACM. All rights reserved.

Date

01 Oct 1987

Publication

Journal of the ACM

Authors

Topics

Resources

Share