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.

• Preformatted versions of the article
  • DVI (118,836 bytes)
  • PostScript (504,376 bytes)
  • PDF (400,354 bytes)
  • Audio by AsTeR (to appear)
• Source materials for custom formatting
  • LaTeX ( cj97-03.tex , 86,787 bytes)
  • BIBTeX ( cj97-03.bib , 3,369 bytes)
  • Parameter settings for custom formatting ( cjropts.tex , 165 bytes)
  • Self citation in BIBTeX (282 bytes)
• Online discussion
• Instructions for Readers

---

Article 2 Article 4
Volume 1997 Published articles

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