Scalable Self-Stabilization

✍ Scribed by Sukumar Ghosh; Xin He

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 232 KB
• Volume: 62
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.2001.1824

✦ Synopsis

This paper presents a methodology for a synchronous non-reactive distributed system on a tree topology to stabilize from a k-faulty configuration in a time independent of the size n of the system. In the proposed methodology, processes first measure and compare the sizes of the faulty regions, and then use this information to schedule actions in such a way that the size of the faulty regions progressively shrink, until they completely disappear. We demonstrate that when k processes fail, the stabilization time is Oðk 2 Þ. Apart from its applicability to a wide class of problems, the proposed method achieves scalability with a low space complexity of OðD:ðD:k þ log 2 nÞÞ per process, where D is the maximum degree of a node. # 2002 Elsevier Science (USA)