CJTCS Volume 1997 Article 3

Self-Stabilization by Tree Correction

George Varghese (Washington University in St. Louis), Anish Arora (Ohio State University), Mohamed Gouda (University of Texas, Austin)
4 November 1997
Special Issue on Self-Stabilization , Shlomi Dolev and Jennifer Welch editors
Abstract

We describe a simple tree-correction theorem that states that any locally checkable protocol that works on a tree can be efficiently stabilized in time proportional to the height of the tree. We show how new protocols can be designed, and how existing work can be easily understood using this theorem.


[] Article 2 [] Article 4
[back] Volume 1997 [back] Published articles
[CJCTS home]

Last modified: Thu Dec 18 22:30:08 CST