Technical Report CS0641

Authors: s. Dolev, A. Israeli, and S. Moran
Abstract: A self-stabilizing system is a distributed system which can be started in any possible global state. Once started the system regains its consistency qy itself, without any kind of an outside intervention. The self-stabilization property is very useful for systems in which processors may crash and then recover spontaneously in an arbitrary state. When the intermediate period in between one recovery and the next crash is long enough the system stabilizes. Most of the work in this field assumes the communication model of shared variables. The paradigm of self-stabilization is a very general one and does not depend on the communication media used by the system's processors. A very natural subject would be to look at self stabilizing message passing systems. Surprisingly, there are very few papers which addressed this subject. In this work the class of self stabilizing message driven protocols is defined and studied. The viability of this new class is demonstrated by proving non-trivial lower and upper bounds on the resources required by self stabilizing message driven protocols for token passing. The main technical contribution of this paper is a self stabilizing token passing protocol in which processors are finite state machines and (hence) messages are of fixed size. Our results have an interesting interpretation in terms of automata theory.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1990
To the main CS technical reports page

Computer science department, Technion