Abstract
Stabilizing algorithms can automatically recover their specifications from an arbitrary configuration in finite time. They are therefore well-suited for dynamic and failure prone environments. A silent algorithm always reaches a terminal configuration in a finite time. The spanning-tree construction is a fundamental task in distributed systems which forms the basis for many other network algorithms (like Token Circulation, Routing or Propagation of Information with Feedback). In this paper we present a silent stabilizing algorithm working in n 2 steps (where n is the number of processors in the network) with a distributed daemon, without any fairness assumptions. This complexity is totally independent of the initial values present in the network. So, this improves all the previous results of the literature.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Tel, G.: Introduction to distributed algorithms. Cambridge University Press, Cambridge (2001)
Dijkstra, E.W.: Self-stabilizing systems in spite of distributed control. Communication of the Association of the Computing Machinery 17, 643–644 (1974)
Bui, A., Datta, A.K., Petit, F., Villain, V.: State-optimal snap-stabilizing pif in tree networks. In: Arora, A. (ed.) WSS, pp. 78–85. IEEE Computer Society, Los Alamitos (1999)
Berge, C.: Graphes et hypergraphes. Dunod (1985)
Aho, A., Ullman, J.: Foundations of Computer Science. W.H. Freeman and Company, New York (1992)
Cournier, A., Devismes, S., Villain, V.: A Snap-Stabilizing DFS with a Lower Space Requirement. In: Tixeuil, S., Herman, T. (eds.) SSS 2005. LNCS, vol. 3764, pp. 33–47. Springer, Heidelberg (2005)
Cournier, A., Devismes, S., Villain, V.: Snap-Stabilizing PIF and Useless Computations. In: ICPADS (1), pp. 39–48. IEEE Computer Society, Los Alamitos (2006)
Dolev, S., Israeli, A., Moran, S.: Self-stabilization of dynamic systems assuming only read/write atomicity. Distributed Computing 7(1), 3–16 (1993)
Chen, N.S., Yu, H.P., Huang, S.T.: A Self-Stabilizing Algorithm for Constructing Spanning Trees. Inf. Process. Lett. 39(3), 147–151 (1991)
Huang, S.T., Chen, N.S.: A Self-Stabilizing Algorithm for Constructing Breadth-First Trees. Inf. Process. Lett. 41(2), 109–117 (1992)
Cournier, A., Datta, A.K., Petit, F., Villain, V.: Self-Stabilizing PIF Algorithm in Arbitrary Rooted Networks. In: ICDCS, pp. 91–98 (2001)
Cournier, A., Datta, A.K., Petit, F., Villain, V.: Snap-Stabilizing PIF Algorithm in Arbitrary Networks. In: 22th IEEE International Conference on Distributed Computing Systems (ICDCS 2002), Vienna, July 2002, pp. 199–208. IEEE Computer Society Press, Los Alamitos (2002)
Cournier, A., Devismes, S., Villain, V.: Snap-Stabilizing Detection of Cutsets. In: Bader, D.A., Parashar, M., Sridhar, V., Prasanna, V.K. (eds.) HiPC 2005. LNCS, vol. 3769, pp. 488–497. Springer, Heidelberg (2005)
Devismes, S.: A Silent Self-Stabilizing Algorithm for finding Cut-nodes and Bridges. Parallel Processing Letters 49(1-2), 183–198 (2005)
Kosowski, A., Kuszner, L.: A self-stabilizing algorithm for finding a spanning tree in a polynomial number of moves. In: Wyrzykowski, R., Dongarra, J., Meyer, N., Waśniewski, J. (eds.) PPAM 2005. LNCS, vol. 3911, pp. 75–82. Springer, Heidelberg (2006)
Burman, J., Kutten, S.: Time optimal asynchronous self-stabilizing spanning tree. In: Pelc, A. (ed.) DISC 2007. LNCS, vol. 4731, pp. 92–107. Springer, Heidelberg (2007)
Gaertner, F.C.: A Survey of Self-Stabilizing Spanning-Tree Construction Algorithms. Technical report, Swiss Federal Institute of Technology, EPFL (2003)
Datta, A.K., Larmore, L.L., Vemula, P.: Self-stabilizing leader election in optimal space. In: Kulkarni, S., Schiper, A. (eds.) SSS 2008. LNCS, vol. 5340, pp. 109–123. Springer, Heidelberg (2008)
Arora, A., Gouda, M.G.: Distributed reset. IEEE Trans. Computers 43(9), 1026–1038 (1994)
Dolev, S., Israeli, A., Moran, S.: Uniform dynamic self-stabilizing leader election. IEEE Trans. Parallel Distrib. Syst. 8(4), 424–440 (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cournier, A. (2010). A New Polynomial Silent Stabilizing Spanning-Tree Construction Algorithm. In: Kutten, S., Žerovnik, J. (eds) Structural Information and Communication Complexity. SIROCCO 2009. Lecture Notes in Computer Science, vol 5869. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-11476-2_12
Download citation
DOI: https://doi.org/10.1007/978-3-642-11476-2_12
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-11475-5
Online ISBN: 978-3-642-11476-2
eBook Packages: Computer ScienceComputer Science (R0)