Self-Stabilizing Routing and Related Protocols

✍ Scribed by Shlomi Dolev

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 85 KB
• Volume: 42
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.1997.1317

✦ Synopsis

A self-stabilizing system is a distributed system which can tolerate any number and any type of faults in the history. After the last fault occurs the system converges to a legitimate behavior. The self-stabilization property is very useful for systems in which processors may malfunction for a while and then recover. When there is a long enough period during which no processor malfunctions the system stabilizes. Dynamic distributed systems are systems in which communication links and processors may fail and recover during normal operation. Such failures could cause partitioning of the system communication graph. The application of self-stabilizing protocols to dynamic systems is natural. Following the last topology change each connected component of the system stabilizes independently. We present self-stabilizing dynamic protocols for a variety of tasks including: routing, leader election, and topology update. For systems that support local broadcasts to neighbors in a single time unit the protocol for each of those tasks stabilizes in (d) time, where d is the actual diameter of the system.