Abstract
We introduce a self-stabilizing algorithm that builds and maintains a spanning tree topology on any large scale system. We assume that the existing topology is a complete graph and that nodes may arrive or leave at any time. To cope with the large number of processes of a grid or a peer to peer system, we limit the memory usage of each process to a small constant number of variables, combining this with previous results concerning failure detectors and resource discovery.
This work is partially funded by the PCRI/INRIA Futurs – Project Grand-Large and ACI Grid (French incentive).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Chandra, T.D., Toueg, S.: Unreliable failure detectors for reliable distributed systems. Journal of the ACM 43 (March 1996)
Dijkstra, E.: Self stabilizing systems in spite of distributed control. Communications of the Association of the computing Machinery 17(11), 643–644 (1974)
Herault, T., Lemarinier, P., Peres, O., Pilard, L., Beauquier, J.: Self-stabilizing spanning tree algorithm for large scale systems. Technical Report 1457, LRI (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Herault, T., Lemarinier, P., Peres, O., Pilard, L., Beauquier, J. (2006). Brief Announcement: Self-stabilizing Spanning Tree Algorithm for Large Scale Systems. In: Datta, A.K., Gradinariu, M. (eds) Stabilization, Safety, and Security of Distributed Systems. SSS 2006. Lecture Notes in Computer Science, vol 4280. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-49823-0_44
Download citation
DOI: https://doi.org/10.1007/978-3-540-49823-0_44
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-49018-0
Online ISBN: 978-3-540-49823-0
eBook Packages: Computer ScienceComputer Science (R0)