Abstract
A distributed system is self-stabilizing if it returns to a legitimate state in a finite number of steps regardless of the initial state, and the system remains in a legitimate state until another fault occurs. A routing algorithm is loop-free if, a path being constructed between two processors p and q, any edges cost change induces a modification of the routing tables in such a way that at any time, there always exists a path from p to q.
We present a self-stabilizing loop-free routing algorithm that is also route preserving. This last property means that, a tree being constructed, any message sent to the root is received in a bounded amount of time, even in the presence of continuous edge cost changes. Also, and unlike previous approaches, we do not require that a bound on the network diameter is known to the processors that perform the routing algorithm. We guarantee self-stabilization for many metrics (such as minimum distance, shortest path, best transmitter, depth first search metrics, etc.), by reusing previous results on r-operators.
This work was supported in part by the French projects STAR and DYNAMO.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
A Arora, MG Gouda, and T Herman. Composite routing protocols. In Proceedings of the 2nd IEEE Symposium on Parallel and Distributed Processing, pages 70–78, 1990. 185, 186, 195
B Awerbuch, S Kutten, Y Mansour, B Patt-Shamir, and G Varghese. Time optimal self-stabilizing synchronization. In STOC93 Proceedings of the 25th Annual ACM Symposium on Theory of Computing, pages 652–661, 1993. 185
F Baccelli, G Cohen, G Olsder, and JP Quadrat. Synchronization and linearity, an algebra for discrete event systems. Series in Probability and Mathematical Statistics, 1992. 195
JA Cobb and MG Gouda. Stabilization of general loop-free routing. Journal of Parallel and Distributed Computing, 62(5):922–944, 2002. 185, 186, 195
EW Dijkstra. Self stabilizing systems in spite of distributed control. Communications of the Association of the Computing Machinery, 17(11):643–644, 1974. 184
S Dolev. Self-stabilizing routing and related protocols. Journal of Parallel and Distributed Computing, 42(2):122–127, 1997. 185
S Dolev, MG Gouda, and M Schneider. Memory requirements for silent stabilization. Acta Informatica, 36(6):447–462, 1999. 188
B Ducourthial. New operators for computing with associative nets. In Proceedings of the Fifth International Colloquium on Structural Information and Communication Complexity (SIROCCO’98), Amalfi, Italia, pages 51–65, 1998. 195
B Ducourthial and S Tixeuil. Self-stabilization with r-operators. Distributed Computing, 14(3):147–162, 2001. 185, 186, 195, 196, 197
B Ducourthial and S Tixeuil. Self-stabilization with path algebra. Theoretical Computer Science, 293(1):219–236, 2003. 185, 197
MG Gouda and M Schneider. Stabilization of maximal metric trees. In Proceedings of the Fourth Workshop on Self-Stabilizing Systems (published in association with ICDCS99 The 19th IEEE International Conference on Distributed Computing Systems), pages 10–17. IEEE Computer Society, 1999. 185
C Johnen and S Tixeuil. Route preserving stabilization. Technical Report 1353, LRI, Université Paris-Sud XI, 2003. 195
R Perlman. Interconnexion Networks. Addison Wesley, 2000. 184, 185
G Tel. Introduction to Distributed Algorithms. Cambridge University Press, 1994. 195
G Varghese and M Jayaram. The fault span of crash failures. Journal of the Association of the Computing Machinery, 47(2):244–293, 2000. 185
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Johnen, C., Tixeuil, S. (2003). Route Preserving Stabilization. In: Huang, ST., Herman, T. (eds) Self-Stabilizing Systems. SSS 2003. Lecture Notes in Computer Science, vol 2704. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45032-7_14
Download citation
DOI: https://doi.org/10.1007/3-540-45032-7_14
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40453-8
Online ISBN: 978-3-540-45032-0
eBook Packages: Springer Book Archive