Nordic Journal of Computing Bibliography

Stefan Dobrev and Peter Ruzicka. On the Communication Complexity of Strong Time-Optimal Distributed Algorithms. Nordic Journal of Computing, 5(2):87-104, Summer 1998.

In 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


  • Nordic Journal of Computing homepage
  • Bibliography top level
  • Nordic Journal of Computing Author Index
  • Search the HBP database