Self-stabilization by local checking and global reset
We describe a method for transforming asynchronous network protocols into protocols that can sustain any transient fault, i.e., become self-stabilizing. We combine the known notion of local checking with a new notion of internal reset, and prove that given any self-stabilizing internal reset protocol, any locally-checkable protocol can be made self-stabilizing. Our proof is constructive in the sense that we provide explicit code. The method applies to many practical network problems, including spanning tree construction, topology update, and virtual circuit setup.
|Series||Lecture Notes in Computer Science|
Awerbuch, B. (Baruch), Patt-Shamir, B. (Boaz), Varghese, G. (George), & Dolev, S. (Shlomi). (1994). Self-stabilization by local checking and global reset. In Lecture Notes in Computer Science.