skip to main content
10.1145/1146381.1146389acmconferencesArticle/Chapter ViewAbstractPublication PagespodcConference Proceedingsconference-collections
Article

Distributed verification of minimum spanning trees

Published: 23 July 2006 Publication History

Abstract

The problem of verifying a Minimum Spanning Tree (MST) was introduced by Tarjan in a sequential setting. Given a graph and a tree that spans it, the algorithm is required to check whether this tree is an MST. This paper investigates the problem in the distributed setting, where the input is given in a distributed manner, i.e., every node "knows" which of its own emanating edges belong to the tree. Informally, the distributed MST verification problem is the following. Label the vertices of the graph in such a way that for every node, given its own label and the labels of its neighbors only, the node can detect whether these edges are indeed its MST edges. In this paper we present such a verification scheme with a maximum label size of O(log n log W), where n is the number of nodes and W is the largest weight of an edge. We also give a matching lower bound of Ω(log n log W) (except when W ≤ log n). Both our bounds improve previously known bounds for the problem.For the related problem of tree sensitivity also presented by Tarjan, our method yields rather efficient schemes for both the distributed and the sequential settings. Our techniques (both for the lower bound and for the upper bound) may indicate a strong relation between the fields of proof labeling schemes and implicit labeling schemes.

References

[1]
Y. Afek, S. Kutten, and M. Yung. The Local Detection Paradigm and its Applications to Self Stabilization. Theoretical Computer Science, Vol. 186, No. 1--2, pages 199--230, 1997.]]
[2]
B. Awerbuch and G. Varghese. Distributed Program Checking: a Paradigm for Building Self-Stabilizing Distributed Protocols. Proc. IEEE FOCS 1991, pages 258--267.]]
[3]
I. Cidon, I. Gopal, M. Kaplan, and S. Kutten. A Distributed Control Architecture of High-Speed Networks. IEEE Transactions on Communications, Vol. 43, No. 5, pp. 1950--1960, May 1995.]]
[4]
S. Deering, D. Estrin, D. Farinacci, V. Jacobson, C. Liu, and L. Wei. Protocol Independent Multicast (PIM): Motivation and Architecture. Internet Draft draft-ietf-pim-arch-01.ps, January 1995.]]
[5]
B. Dixon, M. Rauch, and R. E. Tarjan. Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time. SIAM Journal on Computing, Vol. 21, No 6, pages 1184--1192, December 1992.]]
[6]
B. Dixon and R. E. Tarjan. Optimal Parallel Verification of Minimum Spanning Trees in Logarithmic Time. Algorithmica Issue: Volume 17, Number 1, pages 11 -- 18, January 1997.]]
[7]
S. Dolev, M. G. Gouda, and M. Schnieider. Memory requirements for silent stabilization. Acta Informatica, Vol. 36, Issue 6, October 1999, pages 447--462.]]
[8]
P. Fraigniaud and C. Gavoille. Routing in trees. In Proc. 28th Int. Colloq. on Automata, Languages & Prog., LNCS 2076, pages 757--772, July 2001.]]
[9]
M.L. Fredman and D.E. Willard. Trans-Dichotomous algorithms for minimum spanning trees and shortest paths. Proc. 31st IEEE FOCS, Los Alamitos, CA, 1990, pages 719--725.]]
[10]
R.G. Gallager, P.A. Humblet, P.M. Spira. A distributed algorithm for minimum-weight spanning trees. ACM Trans. on Programming Languages and Systems, 5 (1983) 66--77.]]
[11]
C. Gavoille, M. Katz, N.A. Katz, C. Paul and D. Peleg. Approximate Distance Labeling Schemes. In 9th European Symp. on Algorithms, Aug. 2001, Aarhus, Denmark, SV-LNCS 2161, 476--488.]]
[12]
C. Gavoille, D. Peleg, S. Pérennes, and R. Raz. Distance labeling in graphs. In Proc. 12th ACM-SIAM Symp. on Discrete Algorithms, pages 210--219, Jan. 2001.]]
[13]
D. Harel. A linear Time Algorithm for Finding Dominators in Flow Graphs and Related Problems. Proc. 17th ACM STOC, Salem, MA, 1985, pages 18--194.]]
[14]
M. Jayaram, G. Varghese. The Complexity of Crash Failures. Proc ACM PODC 1997, pages 179--188.]]
[15]
M. Jayaram, G. Varghese. Crash Failures Can Drive Protocols to Arbitrary States. Proc ACM PODC 1996, pages 247--256.]]
[16]
S. Kannan, M. Naor, and S. Rudich. Implicit representation of graphs. In SIAM J. on Descrete Math 5, (1992), 596--603.]]
[17]
M. Katz, N.A. Katz, A. Korman, and D. Peleg. Labeling schemes for flow and connectivity. In Proc. 19th ACM-SIAM Symp. on Discrete Algorithms, Jan. 2002.]]
[18]
D. R. Karger, P.N. Klein, and R.E. Tarjan. A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees. JACM Vol. 42, No. 2, pages 3210328, 1955.]]
[19]
J. Koml'os. Linear verification for spanning trees. Combinatorica, 5 (1985), pages 57--65.]]
[20]
A. Korman, S. Kutten, and D. Peleg. Proof Labeling Schemes. Proc. the 24th Annual ACM Symposium on Principles of Distributed Computing (PODC 2005), Las Vegas, NV, USA, July 2005.]]
[21]
S. Kutten and D. Peleg. Fast Distributed Construction of Small k-Dominating Sets, and Applications. Journal of Algorithms 28(1), pages 40--66 (1998).]]
[22]
V. King. A simpler minimum spanning tree verification algorithm. Algorithmica (1997) 18: 263--270.]]
[23]
V. King, C.K Poon, V. Ramachandran, S. Sinha. An Optimal EREW PRAM Algorithm for Minimum Spanning Tree Verification. IPL 62(3):153--159, 1997.]]
[24]
R. E. Tarjan. Sensitivity Analysis of Minimum Spanning Trees and Shortest Paths Trees. Information Processing Letters, 14 (1982), Pages 30--33; Corrigendum, Ibid. 23 (1986) page 219.]]
[25]
R. E. Tarjan. Data Structures and Network Algorithms. SIAM, Philadelphia, PA, USA, 1983.]]
[26]
F. Kuhn and R. Watenhoffer. Constant Time Distributed Dominating Set Approximation. Distributed Computing 17(4) 303--310 (2005).]]
[27]
F. Kuhn, T. Moscibroda, and R. Watenhoffer. What cannot be computed locally! ACM PODC 2004, pages 300--309.]]
[28]
S Pettie and V. Ramachandran. An optimal minimum spanning tree algorithm. JACM 49(1): 16--34 (2002).]]
[29]
E. E. Tarjan. Applications of path compression on balanced trees. JACM 26 (1979), pages 690715.]]

Cited By

View all
  • (2024)Decreasing Verification Radius in Local CertificationAlgorithmics of Wireless Networks10.1007/978-3-031-74580-5_14(188-201)Online publication date: 5-Sep-2024
  • (2016)Distributed alarming in the on-duty and off-duty modelsIEEE/ACM Transactions on Networking10.1109/TNET.2014.235968424:1(218-230)Online publication date: 1-Feb-2016
  • (2015)A new algorithm for the minimum spanning tree verification problemComputational Optimization and Applications10.1007/s10589-014-9702-861:1(189-204)Online publication date: 1-May-2015
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
PODC '06: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing
July 2006
230 pages
ISBN:1595933840
DOI:10.1145/1146381
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 July 2006

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. distributed algorithms
  2. graph property verification
  3. labeling schemes
  4. minimum spanning tree
  5. network algorithms
  6. proof labeling
  7. self stabilization

Qualifiers

  • Article

Conference

PODC06

Acceptance Rates

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)11
  • Downloads (Last 6 weeks)0
Reflects downloads up to 14 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Decreasing Verification Radius in Local CertificationAlgorithmics of Wireless Networks10.1007/978-3-031-74580-5_14(188-201)Online publication date: 5-Sep-2024
  • (2016)Distributed alarming in the on-duty and off-duty modelsIEEE/ACM Transactions on Networking10.1109/TNET.2014.235968424:1(218-230)Online publication date: 1-Feb-2016
  • (2015)A new algorithm for the minimum spanning tree verification problemComputational Optimization and Applications10.1007/s10589-014-9702-861:1(189-204)Online publication date: 1-May-2015
  • (2014)Fast and Compact Distributed Verification and Self-stabilization of a DFS TreePrinciples of Distributed Systems10.1007/978-3-319-14472-6_22(323-338)Online publication date: 2014
  • (2012)Memory lower bounds for randomized collaborative search and implications for biologyProceedings of the 26th international conference on Distributed Computing10.1007/978-3-642-33651-5_5(61-75)Online publication date: 16-Oct-2012
  • (2011)Distributed decision problemsProceedings of the First international ICST conference on Theory and practice of algorithms in (computer) systems10.5555/1987334.1987335(1-5)Online publication date: 18-Apr-2011
  • (2011)Distributed verification and hardness of distributed approximationProceedings of the forty-third annual ACM symposium on Theory of computing10.1145/1993636.1993686(363-372)Online publication date: 6-Jun-2011
  • (2011)Online computation with adviceTheoretical Computer Science10.1016/j.tcs.2010.08.007412:24(2642-2656)Online publication date: 1-May-2011
  • (2010)Proof labeling schemesDistributed Computing10.1007/s00446-010-0095-322:4(215-233)Online publication date: 1-May-2010
  • (2010)Local MST Computation with Short AdviceTheory of Computing Systems10.1007/s00224-010-9280-947:4(920-933)Online publication date: 1-Nov-2010
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media