AbstractIn this paper we introduce the notion of time optimality in the strong sense and we investigate the communication complexity of strong time-optimal distributed algorithms. We show that a strong time-optimal algorithm solving the MST problem on networks with n nodes and m links interchanges at least (m-n)2 messages. We also present an Theta(m2) bound on communication complexity for strong time-optimal algorithms solving the gossip problem. As a consequence, similar results can be shown for other interesting problems on arbitrary networks, such as electing a leader, determining the median and the center, computing the diameter and others.
Categories and Subject Descriptors: C.2.1 [Computer-Communication Networks]: Network Architecture and Design; G.2.2 [Discrete Mathematics]: Graph Theory; C.2.2 [Computer-Communication Networks]: Network Protocols; F.1.3 [Computation by Abstract Devices]: Complexity Classes; F.2.3 [Analysis of Algorithms and Problem Complexity]: Tradeoffs among Complexity Measures
Additional Key Words and Phrases: distributed algorithms, time and communication complexity, asynchronous networks
Selected references
- Yehuda Afek and Eli Gafni. Time and message bounds for election in synchronous and asynchronous complete networks. SIAM Journal on Computing, 20(2):376-394, April 1991.
- Baruch Awerbuch. A new distributed depth-first-search algorithm. Information Processing Letters, 20(3):147-150, 8 April 1985.
- Baruch Awerbuch. Complexity of network synchronization. Journal of the ACM, 32(4):804-823, October 1985.
- Baruch Awerbuch. Optimal distributed algorithms for minimum weight spanning tree, counting, leader election and related problems (detailed summary). In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, pages 230-240, New York City, 25-27 May 1987.
- Isreal Cidon. Yet another distributed depth-first-search algorithm. Information Processing Letters, 26(6):301-305, 25 January 1988.
- R. G. Gallager, P. A. Humblet, and Philip M. Spira. A distributed algorithm for minimum-weight spanning trees. ACM Transactions on Programming Languages and Systems, 5(1):66-77, January 1983.
- Juan A. Garay, Shay Kutten, and David Peleg. A sub-linear time distributed algorithm for minimum-weight spanning trees (extended abstract). In 34th Annual Symposium on Foundations of Computer Science, pages 659-668, Palo Alto, California, 3-5 November 1993. IEEE.
- Gurdip Singh and Arthur J. Bernstein. A highly asynchronous minimum spanning tree protocol. Distributed Computing, 8(3):151-161, 1995.