The Local Detection Paradigm and its
Applications to Self Stabilization
Yehuda Afek Shay Kutten
Computer Science Department, IBM T.J. Watson Research Center,
Tel-Aviv University, Israel 69978, P.O. Box 704, Yorktown Heights, NY 10598
afek@math.tau.ac.il kutten@watson.ibm.com
Moti Yung
IBM T.J. Watson Research Center,
P.O. Box 704, Yorktown Heights, NY 10598
moti@watson.ibm.com
* A preliminary version of this paper appeared in the Proc. of the 1990 International
Workshop on Distributed Algorithms, Bari, Italy.
Abstract
A new paradigm for the design of self-stabilizing distributed algorithms, called local
detection, is introduced. The essence of the paradigm is in defining a local condition based
on the state of a processor and its immediate neighborhood, such that the system is in a
globally legal state if and only if the local condition is satisfied at all the nodes. In
this work we also extend the model of self-stabilizing networks traditionally assuming memory
failure to include the model of dynamic networks (assuming edge failures and recoveries). We
apply the paradigm to the extended model which we call "dynamic self-stabilizing networks.
" Without loss of generality, we present the results in the least restrictive shared memory
model of read/write atomicity, to which end we construct basic information transfer primitives.
Using local detection, we develop deterministic and randomized self-stabilizing algorithms
that maintain a rooted spanning tree in a general network whose topology changes dynamically.
The deterministic algorithm assumes unique identities while the randomized assumes an
anonymous network. The algorithms use a constant number of memory words per edge in each node;
and both The size of memory words and of messages is the number of bits necessary to represent
a node identity (typically O(log n) bits where n is the size of the network). These algorithms
routing, topology-update and self-stabilization transformers that automatically self-stabilize
existing protocols for which local detection conditions can be defined.
Key words: self-stabilizing distributed algorithms, spanning-tree algorithm, leader election,
reset protocol, dynamic networks algorithms, locality in distributed computing, local
detection/ local checking.