Physicalsystemswhichrightthemselvesafterbeingdisturbedevokeourcuriosity becausewe wantto understand howsuchsystemsareableto reactto unexpected stimuli. Themechanismsareallthe morefascinatingwhensystemsarecomposed of small, simple units, and the ability of the system to self-stabilize emerges out of its components. Faithful computer simulations of such physical systems exhibit the self-stabilizing property, but in the realm of computing, particularly for distributed systems, wehavegreaterambition. We imaginethat all manner of software, ranging from basic communication protocols to high-level applications, could enjoy self-corrective properties. Self-stabilizing software o? ers a unique, non-traditional approach to the c- cial problem of transient fault tolerance. Many successful instances of modern fault-tolerant networks are based on principles of self-stabilization. Surprisingly, the most widely accepted technical de? nition of a self-stabilizing system does not refer to faults: it is the property that the system can be started in any i- tial state, possibly an "illegal state," and yet the system guarantees to behave properly in ? nite time. This, and similar de? nitions, break many traditional approaches to program design, in which the programmer by habit makes - sumptions about initial conditions. The composition of self-stabilizing systems, initially seen as a daunting challenge, has been transformed into a mana- able task, thanks to an accumulation of discoveries by many investigators. - search on various topics in self-stabilization continues to supply new methods for constructing self-stabilizing systems, determines limits and applicability of the paradigm of self-stabilization, and connects self-stabilization to related areas of fault tolerance anddistributed computing.
Inhaltsverzeichnis
Cooperating Mobile Agents and Stabilization. - Cross-Over Composition - Enforcement of Fairness under Unfair Adversary. - Easy Stabilization with an Agent. - Stabilization of Routing in Directed Networks. - Dijkstra s Self-Stabilizing Algorithm in Unsupportive Environments. - Communication Adaptive Self-Stabilizing Group Membership Service. - (Im)Possibilities of Predicate Detection in Crash-Affected Systems. - The Theory of Weak Stabilization. - On the Security and Vulnerability of PING. - A New Efficient Tool for the Design of Self-Stabilizing ? -Exclusion Algorithms: The Controller. - Self-Stabilizing Agent Traversal. - A Composite Stabilizing Data Structure. - Stabilizing Causal Deterministic Merge. - Fast Self-Stabilizing Depth-First Token Circulation. - On a Space-Optimal Distributed Traversal Algorithm.
