THE LOCAL DETECTION PARADIGM AND ITS APPLICATIONS TO SELF-STABILIZATION

A new paradigm for the design of self-stabilizing distributed algorith ms, called local detection, is introduced. The essence of the paradigm is in defining a local condition based on the state of a processor an d its immediate neighborhood such that the system is in a globally leg al state if and only if the local condition is satisfied at all the no des. In this work we also extend the model of self-stabilizing network s traditionally assuming memory failure to include the model of dynami c networks (assuming edge failures and recoveries). We apply the parad igm to the extended model which we call ''dynamic self-stabilizing net works''. Without loss of generality, we present the results in the lea st restrictive shared memory model of read/write atomicity, to which e nd we construct basic information transfer primitives. Using local det ection, we develop deterministic and randomized self-stabilizing algor ithms that maintain a rooted spanning tree in a general network whose topology changes dynamically. The deterministic algorithm assumes uniq ue identities while the randomized assumes an anonymous network. The a lgorithms 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 bi ts necessary to represent a node identity (typically O(log n) bits whe re n is the size of the network). These algorithms provide for the eas y construction of self-stabilizing protocols for numerous tasks: reset , routing, topology-update and self-stabilization transformers that au tomatically self-stabilize existing protocols for which local detectio n conditions can be defined.