Self-Stabilizing Systems

1. Front Matter

   Pages I-VII

   PDF

2. Cooperating Mobile Agents and Stabilization

   • Sukumar Ghosh

   Pages 1-18

3. Cross-Over Composition - Enforcement of Fairness under Unfair Adversary

   • Joffroy Beauquier, Maria Gradinariu, Colette Johnen

   Pages 19-34

4. Easy Stabilization with an Agent

   • Joffroy Beauquier, Thomas Hérault, Elad Schiller

   Pages 35-50

5. Stabilization of Routing in Directed Networks

   • Jorge A. Cobb, Mohamed G. Gouda

   Pages 51-66

6. Dijkstra’s Self-Stabilizing Algorithm in Unsupportive Environments

   • Shlomi Dolev, Ted Herman

   Pages 67-81

7. Communication Adaptive Self-Stabilizing Group Membership Service

   • Shlomi Dolev, Elad Schiller

   Pages 82-97

8. (Im)Possibilities of Predicate Detection in Crash-Affected Systems

   • Felix C. Gärtner, Stefan Pleisch

   Pages 98-113

9. The Theory of Weak Stabilization

   • Mohamed G. Gouda

   Pages 114-123

10. On the Security and Vulnerability of PING

    • Mohamed G. Gouda, Chin-Tser Huang, Anish Arora

    Pages 124-135

11. A New Efficient Tool for the Design of Self-Stabilizing ℓ-Exclusion Algorithms: The Controller

    • Rachid Hadid, Vincent Villain

    Pages 136-151

12. Self-Stabilizing Agent Traversal

    • Ted Herman, Toshimitsu Masuzawa

    Pages 152-166

13. A Composite Stabilizing Data Structure

    • Ted Herman, Imran Pirwani

    Pages 167-182

14. Stabilizing Causal Deterministic Merge

    • Sandeep S. Kulkarni, Ravikant

    Pages 183-199

15. Fast Self-Stabilizing Depth-First Token Circulation

    • Franck Petit

    Pages 200-215

16. On a Space-Optimal Distributed Traversal Algorithm

    • Sébastien Tixeuil

    Pages 216-228

17. Back Matter

    Pages 229-229

    PDF

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.

• Adaptive Self-Stabilization
• Adaptive Systems
• Distributed Algorithms
• Error-Correcting Codes
• Fault-Tolerant Systems
• Self-Stabilization
• Self-Stabilizing Systems
• communication
• distributed systems
• routing
• algorithm analysis and problem complexity

• Department of Computer Science, University of Nevada, Las Vegas, USA

  Ajoy K. Datta

• Department of Computer Science, University of Iowa, Iowa City, USA

  Ted Herman

Policies and ethics