Chicago Journal of Theoretical Computer Science

Volume 1997

Article 3

Published by MIT Press. Copyright 1997 Massachusetts Institute of Technology.

Your institution may already be a subscriber to CJTCS. If not, please subscribe for legitimate access to all journal articles.

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

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.

DOI: 10.4086/cjtcs.1997.003
[] Article 2 [] Article 4
[back] Volume 1997 [back] Published articles
[CJCTS home]

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