|
 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 result is O(nlogn) lower and upper bounds on the number of messages required by any algorithm in a given class of distributed algorithms for such networks. This class includes algorithms for problems like finding a leader or constructing a spanning tree (as far as we know, all known algorithms for those problems may require O(n2) messages when applied to complete networks). O(n2) bounds for other problems, like constructing a maximal matching or a Hamiltonian 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 actually number of messages carried by each edge). Interestingly, this number is shown to be of the same order of magnitude of the total number of messages needed by these algorithms. In the upper bounds, the length of any message is at most log2[4mlog2n] 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 finding a minimum weight spanning tree in such a network, which may require O(n2) messages.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
J. E. Burns, A formal model for message passing systems, TR-91, Indiana University, September 1980.
|
| |
2
|
D. Dolev, M. Klawe and M. Rodeh, An O(nlogn) unidirectional distributed algorithm for extrema finding in a circle, J. of Algorithms, 3, 1982, pp. 245-260.
|
| |
3
|
R. G. Gallager, Choosing a leader in a network, unpublished memorandum, M.I.T.
|
 |
4
|
|
| |
5
|
|
| |
6
|
E. Korach, S. Moran and S. Zaks, Finding a Minimum Spanning Tree can be harder than finding a spanning tree in a distributed network, TR #294, Dept. of Computer Science, Technion, Israel (October 1983).
|
| |
7
|
|
| |
8
|
|
| |
9
|
N. Santoro, On the message complexity of distributed systems, SCS-TR-13, School of Computer Science, Carleton University, Ottawa, Canada (1982).
|
CITED BY 25
|
|
|
|
|
Yehuda Afek , Gad M. Landau , Baruch Schieber , Moti Yung, The power of multimedia: combining point-to point and multi-access networks, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.90-104, August 15-17, 1988, Toronto, Ontario, Canada
|
|
|
B. Awerbuch, Optimal distributed algorithms for minimum weight spanning tree, counting, leader election, and related problems, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.230-240, January 1987, New York, New York, United States
|
|
|
Yefim Dinitz , Shlomo Moran , Sergio Rajsbaum, Bit complexity of breaking and achieving symmetry in chains and rings (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.265-274, May 01-04, 1999, Atlanta, Georgia, United States
|
|
|
Ofer Biran , Shlomo Moran , Shmuel Zaks, A combinatorial characterization of the distributed tasks which are solvable in the presence of one faulty processor, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.263-275, August 15-17, 1988, Toronto, Ontario, Canada
|
|
|
|
|
|
|
|
|
M. J. Fischer , S. Moran , R. Rudich , G. Taubenfeld, The wakeup problem, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.106-116, May 13-17, 1990, Baltimore, Maryland, United States
|
|
|
|
|
|
|
|
|
|
|
|
Shlomo Moran , Gadi Taubenfeld , Irit Yadin, Concurrent counting, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.59-70, August 10-12, 1992, Vancouver, British Columbia, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
C.2