Introduction to Distributed Self-Stabilizing Algorithms (Synthesis Lectures on Distributed Computing Theory)

This book aims at being a comprehensive and pedagogical introduction to the concept of self-stabilization, introduced by Edsger Wybe Dijkstra in 1973. Self-stabilization characterizes the ability of a distributed algorithm to converge within finite time to a configuration from which its behavior is correct (i.e., satisfies a given specification), regardless the arbitrary initial configuration of the system. This arbitrary initial configuration may be the result of the occurrence of a finite number of transient faults. Hence, self-stabilization is actually considered as a versatile non-masking fault tolerance approach, since it recovers from the effect of any finite number of such faults in an unified manner. Another major interest of such an automatic recovery method comes from the difficulty of resetting malfunctioning devices in a large-scale (and so, geographically spread) distributed system (the Internet, Pair-to-Pair networks, and Delay Tolerant Networks are examples of such distributed systems). Furthermore, self-stabilization is usually recognized as a lightweight property to achieve fault tolerance as compared to other classical fault tolerance approaches. Indeed, the overhead, both in terms of time and space, of state-of-the-art self-stabilizing algorithms is commonly small. This makes self-stabilization very attractive for distributed systems equipped of processes with low computational and memory capabilities, such as wireless sensor networks. After more than 40 years of existence, self-stabilization is now sufficiently established as an important field of research in theoretical distributed computing to justify its teaching in advanced research-oriented graduate courses. This book is an initiation course, which consists of the formal definition of self-stabilization and its related concepts, followed by a deep review and study of classical (simple) algorithms, commonly used proof schemes and design patterns, as well as premium results issued from the self-stabilizing community. As often happens in the self-stabilizing area, in this book we focus on the proof of correctness and the analytical complexity of the studied distributed self-stabilizing algorithms. Finally, we underline that most of the algorithms studied in this book are actually dedicated to the high-level atomic-state model, which is the most commonly used computational model in the self-stabilizing area. However, in the last chapter, we present general techniques to achieve self-stabilization in the low-level message passing model, as well as example algorithms.

This book aims at being a comprehensive and pedagogical introduction to the concept of self-stabilization, introduced by Edsger Wybe Dijkstra in 1973.

Self-stabilization characterizes the ability of a distributed algorithm to converge within finite time to a configuration from which its behavior is correct (i.e., satisfies a given specification), regardless the arbitrary initial configuration of the system. This arbitrary initial configuration may be the result of the occurrence of a finite number of transient faults. Hence, self-stabilization is actually considered as a versatile non-masking fault tolerance approach, since it recovers from the effect of any finite number of such faults in a unified manner. Another major interest of such an automatic recovery method comes from the difficulty of resetting malfunctioning devices in a large-scale (and so, geographically spread) distributed system (the Internet, Pair-to-Pair networks, and Delay Tolerant Networks are examples of such distributed systems). Furthermore, self-stabilization is usually recognized as a lightweight property to achieve fault tolerance as compared to other classical fault tolerance approaches. Indeed, the overhead, both in terms of time and space, of state-of-the-art self-stabilizing algorithms is commonly small. This makes self-stabilization very attractive for distributed systems equipped of processes with low computational and memory capabilities, such as wireless sensor networks.

After more than 40 years of existence, self-stabilization is now sufficiently established as an important field of research in theoretical distributed computing to justify its teaching in advanced research-oriented graduate courses. This book is an initiation course, which consists of the formal definition of self-stabilization and its related concepts, followed by a deep review and study of classical (simple) algorithms, commonly used proof schemes and design patterns, as well as premium results issued from the self-stabilizing community. As often happens in the self-stabilizing area, in this book we focus on the proof of correctness and the analytical complexity of the studied distributed self-stabilizing algorithms.

Finally, we underline that most of the algorithms studied in this book are actually dedicated to the high-level atomic-state model, which is the most commonly used computational model in the self-stabilizing area. However, in the last chapter, we present general techniques to achieve self-stabilization in the low-level message passing model, as well as example algorithms.

This book aims at being a comprehensive and pedagogical introduction to the concept of self-stabilization, introduced by Edsger Wybe Dijkstra in 1973. Self-stabilization characterizes the ability of a distributed algorithm to converge within finite time to a configuration from which its behavior is correct (i.e., satisfies a given specification), regardless the arbitrary initial configuration of the system. This arbitrary initial configuration may be the result of the occurrence of a finite number of transient faults. Hence, self-stabilization is actually considered as a versatile non-masking fault tolerance approach, since it recovers from the effect of any finite number of such faults in an unified manner. Another major interest of such an automatic recovery method comes from the difficulty of resetting malfunctioning devices in a large-scale (and so, geographically spread) distributed system (e.g., the Internet, Pair-to-Pair networks, and Delay Tolerant Networks are examples of such distributed systems). Furthermore, self-stabilization is usually recognized as a lightweightproperty to achieve fault tolerance as compared to other classical fault tolerance approaches. Indeed, the overhead, both in terms of time and space, of state-of-the-art self-stabilizing algorithms is commonly small. This makes self-stabilization very attractive for distributed systems equipped of processes with low computational and memory capabilities, such as wireless sensor networks. After more than 40 years of existence, self-stabilization is now sufficiently established as an important field of research in theoretical distributed computing to justify its teaching in advanced research-oriented graduate courses. This book is an initiation course, which consists of the formal definition of self-stabilization and its related concepts, followed by a deep review and study of classical (simple) algorithms, commonly used proof schemes and design patterns, as well as premium results issued from the self-stabilizing community. As often happens in the self-stabilizing area, in this book we focus on the proof of correctness and the analytical complexity of the studied distributed self-stabilizing algorithms. Finally, we underline that most of the algorithms studied in this book are actually dedicated to the high-level atomic-state model, which is the most commonly used computational model in the self-stabilizing area. However, in the last chapter, we present general techniques to achieve self-stabilization in the low-level message passing model, as well as example algorithms Preface......Page 15 Acknowledgments......Page 19 Parable of the Collatz Conjecture......Page 21 Major Advantage: Fault Tolerance......Page 22 Other Advantages......Page 24 Relative Drawbacks and Alternatives......Page 25 Expressiveness......Page 26 Taxonomy of the Self-Stabilizing Literature......Page 27 Roadmap of this Book......Page 29 Graph Notions......Page 31 Variables......Page 32 Steps and Executions......Page 33 Daemons......Page 34 Self-Stabilization......Page 36 Self-Stabilization and Silence......Page 37 Time Complexity......Page 38 Space Complexity......Page 41 The Problem......Page 43 The Algorithm......Page 44 Partial Correctness......Page 45 Termination......Page 46 Time Complexity......Page 49 The Algorithm......Page 53 Closure and Correctness......Page 55 Convergence and Complexity......Page 56 Memory Requirement......Page 63 Related Work......Page 64 The Problem......Page 67 The Algorithm......Page 68 Partial Correctness......Page 71 Termination......Page 73 Time Complexity......Page 75 The Problem......Page 81 The Algorithm......Page 82 Proof of Self-Stabilization......Page 85 Complexity Analysis......Page 91 Proof of Self-Stabilization......Page 102 Complexity Analysis......Page 103 Hierarchical Collateral Composition......Page 109 A Sufficient Condition......Page 111 A Toy Example......Page 116 Algorithm BFS......Page 117 Algorithm STM......Page 118 Algorithm INMAX......Page 121 Hierarchical vs. Nonhierarchical Collateral Composition......Page 123 Communication Links......Page 127 Process Execution......Page 128 Related Work......Page 129 Silence in Message Passing......Page 131 An Example......Page 132 Memory Requirement......Page 133 Message Passing Version of the Token Ring Algorithm of Dijkstra......Page 134 Data-Link Protocol......Page 136 From Atomic-State to Message Passing Model......Page 137 Propagation of Information with Feedback (PIF)......Page 139 A PIF-Based Universal Transformer......Page 142 Stabilization Time in Message Passing......Page 145 Bibliography......Page 149 Authors' Biographies......Page 163 Index......Page 165 Blank Page......Page 2 Provides a comprehensive and pedagogical introduction to the concept of self-stabilization. The includes a formal definition of self-stabilization and related concepts, a deep review and study of classical (simple) algorithms, commonly used proof schemes and design patterns, and premium results issued from the self-stabilizing community. Provides a comprehensive and pedagogical introduction to the concept of self-stabilization. This book is an initiation course, which consists of the formal definition of self-stabilization and its related concepts, followed by a review of classical (simple) algorithms, commonly used proof schemes and design patterns.