Local MST computation with short advice

ABSTRACT

We use the recently introduced advising scheme framework for measuring the difficulty of locally distributively computing a Minimum Spanning Tree (MST). An (m,t)-advising scheme for a distributed problem P is a way, for every possible input I of P, to provide an "advice" (i.e., a bit string) about I to each node so that: (1) the maximum size of the advices is at most m bits, and (2) the problem P can be solved distributively in at most t rounds using the advices as inputs. In case of MST, the output returned by each node of a weighted graph G is the edge leading to its parent in some rooted MST T of G. Clearly, there is a trivial (log n,0)-advising scheme for MST (each node is given the local port number of the edge leading to the root of some MST T), and it is known that any (0,t)-advising scheme satisfies t ≥ Ω (√n). Our main result is the construction of an (O(1),O(log n))-advising scheme for MST. That is, by only giving a constant number of bits of advice to each node, one can decrease exponentially the distributed computation time of MST in arbitrary graph, compared to algorithms dealing with the problem in absence of any a priori information. We also consider the average size of the advices. On the one hand, we show that any (m,0)-advising scheme for MST gives advices of average size Ω(log n). On the other hand we design an (m,1)-advising scheme for MST with advices of constant average size, that is one round is enough to decrease the average size of the advices from log(n) to constant.

REFERENCES

• 1: 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 [doi>10.1145/28395.28421]
• 2: Yehuda Afek , Shay Kutten , Moti Yung, Memory-efficient self stabilizing protocols for general networks, Proceedings of the 4th international workshop on Distributed algorithms, p.15-28, June 1991, Bari, Italy
• 3: R. Cohen, P. Fraigniaud, D. Ilcinkas, A. Korman, and D. Peleg. Labeling schemes for tree representation. In Proc. 7th International Workshop on Distributed Computing (IWDC), pp. 13--24, 2005.
• 4: R. Cohen, P. Fraigniaud, D. Ilcinkas, A. Korman, and D. Peleg. Label-Guided Graph Exploration by a Finite Automaton. In 32nd Int. Colloquium on Automata, Languages and Programming (ICALP), LNCS 3580, Springer, pp. 335--346, 2005.
• 5: F. Chin and H. F. Ting. An almost linear time and O(n log n+e) messages distributed algorithm for minimum-weight spanning trees. In Proc 26th IEEE Symp. on Foundations of Computer Science (FOCS), pp. 257--266, 1985.
• 6: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 7: Michael Elkin, A faster distributed protocol for constructing a minimum spanning tree, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 8: Michael Elkin, Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007407]
• 9: Pierre Fraigniaud , David Ilcinkas , Andrzej Pelc, Oracle size: a new measure of difficulty for communication tasks, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146410]
• 10: P. Fraigniaud, D. Ilcinkas, and A. Pelc. Tree Exploration with an Oracle. 31st Int. Symp. on Mathematical Foundations of Computer Science (MFCS), LNCS 4162, Springer, pp. 24--37, 2006.
• 11: Eli Gafni, Improvements in the time complexity of two message-optimal election algorithms, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.175-185, August 1985, Minaki, Ontario, Canada [doi>10.1145/323596.323612]
• 12: R. G. Gallager , P. A. Humblet , P. M. Spira, A Distributed Algorithm for Minimum-Weight Spanning Trees, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.1, p.66-77, Jan. 1983 [doi>10.1145/357195.357200]
• 13: Amos Korman , Shay Kutten, Distributed verification of minimum spanning trees, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146389]
• 14: Amos Korman , Shay Kutten , David Peleg, Proof labeling schemes, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073817]
• 15: Fabian Kuhn , Thomas Moscibroda , Roger Wattenhofer, What cannot be computed locally!, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011811]
• 16: Nathan Linial, Locality in distributed graph algorithms, SIAM Journal on Computing, v.21 n.1, p.193-201, Feb. 1992 [doi>10.1137/0221015]
• 17: Zvi Lotker , Boaz Patt-Shamir , David Peleg, Distributed MST for constant diameter graphs, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.63-71, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.383984]
• 18: Moni Naor , Larry Stockmeyer, What can be computed locally?, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.184-193, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167149]
• 19: David Peleg, Distributed computing: a locality-sensitive approach, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 20: David Peleg , Vitaly Rubinovich, A Near-Tight Lower Bound on the Time Complexity of Distributed MST Construction, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.253, October 17-18, 1999

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees; Graph labeling

General Terms:
Algorithms, Design, Performance

Keywords:
distributed algorithm, local computation, minimum spanning tree