Table of Contents

2   Definitions, Techniques, and Paradigms

2.1 Definitions of the Computational Model

2.2 Self-Stabilization Requirements

2.3 Complexity Measures

2.4 Randomized Self-Stabilization

2.5 Example: Spanning-Tree Construction

2.6 Example: Mutual Exclusion

2.7 Fair Composition of Self-Stabilizing Algorithms

2.8 Recomputation of Floating Output

2.9 Proof Techniques

2.10 Pseudo-Self-Stabilization

3   Motivating Self-Stabilization

3.1 Initialization of a Data-Link Algorithm in the Presence of Faults

3.2 Arbitrary Configuration Because of Crashes

3.3 Frequently Asked Questions

4   Self-Stabilizing Algorithms for Model Conversions

4.1 Token-Passing: Converting a Central Daemon to read/write

4.2 Data-Link Algorithms: Converting Shared Memory to Message Passing

4.3 Self-Stabilizing Ranking: Converting an Id-based System to a Special-processor System

4.4 Update: Converting a Special Processor to an Id-based Dynamic System

4.5 Stabilizing Synchronizers: Converting Synchronous to Asynchronous Algorithms

4.6 Self-Stabilizing Naming in Uniform Systems: Converting Id-based to Uniform Dynamic Systems

5   Stabilizers

5.1 Resynchsonous Stabilizer

5.2 Monitoring and Resetting

6   Convergence in the Presence of Faults

6.1 Digital Clock Synchonization

6.2 Stabilization in Spite of Napping

6.3 Stabilization in Spite of Byzantine Faults

6.4 Stabilization in the Presence of Faults in Asynchronous Systems

7   Local Stabilization

7.1 Superstabilization

7.2 Self-Stabilizing Fault-Containing Algorithms

7.3 Error-Detection Codes and Repair

8   Self-Stabilizing Computing

8.1 The Computation Power of Self-Stabilizing Systems

8.2 Queue Machine