Technical Report CS0423

Title: Tight Lower and Upper Bounds for Some Distributed Algorithms for a Complete Network of Processors
Authors: E. Korach, S. Moran and S. Zaks
Abstract: Distributed algorithms for complete asynchronous networks of processors (i.e networks where each pair of processors is connected by a communication line) are discussed. The main results are an O(nlogn) algorithm and an O(nlogn) lower bound on the number of messages required by any algorithm iIi a given class. This class includes algorithms for problems like finding a leader or constructing a spanning tree (all previously known algorithms for those problems may require O(n^2) messages when applied to complete networks). O(n^2) bounds for other problems, like constructing a maximal matching or a namiltonian circuit are also given. In proving the lower bound we are counting the edges which carry messages during the executions of the algorithms (ignoring the actual number of messages carried by each edge). Interestingly, this number is shown to be of the same order of magnitude as the total number of messages needed by these algorithms. Moreover, the proofs of the lower bounds apply also for synchronous networks. In the upper bounds, the length of any message is at most log2[4mlog2(n)] bits, where m is the maximum identity of a node in the network. One implication of our results is that finding a spanning tree in a complete network is easier than tinding a minimum weight spanning tree in such a network, which may require O(n^2) messages.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1986
To the main CS technical reports page

Computer science department, Technion