Hello. Sign in to personalize your visit. New user? Register now.


 
 

Introduction to Distributed Self-Stabilizing Algorithms

Synthesis Lectures on Distributed Computing Theory

Karine Altisen​‌
VERIMAG/Grenoble INP, Grenoble, France
Stéphane Devismes​‌
VERIMAG/Université de Grenoble Alpes, Grenoble, France
Swan Dubois​‌
LIP6/Sorbonne Université, Paris, France
Franck Petit​‌
LIP6/Sorbonne Université, Paris, France

Abstract

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.

Table of Contents: Preface / Acknowledgments / Introduction / Preliminaries / Coloring under a Locally Central Unfair Daemon / Synchronous Unison / BFS Spanning Tree Under a Distributed Unfair Daemon / Dijkstra's Token Ring / Hierarchical Collateral Composition / Self-Stabilization in Message Passing Systems / Bibliography / Authors' Biographies / Index

PDF (1694 KB) PDF Plus (1694 KB)

Cited by

Karine Altisen, Stéphane Devismes, Erwan Jahier​‌. (2022) sasa : a SimulAtor of Self-stabilizing Algorithms. The Computer Journal 17.
Online publication date: 7-Jan-2022.
Crossref
Hirotsugu Kakugawa, Sayaka Kamei, Yoshiaki Katayama​‌. (2022) A self-stabilizing token circulation with graceful handover on bidirectional ring networks. International Journal of Networking and Computing 12:1, 103-130.
Online publication date: 1-Jan-2022.
Crossref
Stéphane Devismes, David Ilcinkas, Colette Johnen​‌. (2021) Optimized Silent Self-Stabilizing Scheme for Tree-Based Constructions. Algorithmica 254.
Online publication date: 5-Nov-2021.
Crossref
Yu Liu, Tian Gao, Xiaolong Sun, Zexin Yang, Yujia Zhang, Shan Gao, Xueliang Huang​‌. (2021) A Weak-Consistency–Oriented Collaborative Strategy for Large-Scale Distributed Demand Response. Frontiers in Energy Research 9.
Online publication date: 26-Aug-2021.
Crossref
Shota Kameyama, Keisuke Okumura, Yasumasa Tamura, Xavier Defago​‌. (2021) Active Modular Environment for Robot Navigation. 2021 IEEE International Conference on Robotics and Automation (ICRA), 8636-8642.
Crossref
Karine Altisen, Pierre Corbineau, Stéphane Devismes​‌. (2021) Certification of an Exact Worst-Case Self-Stabilization Time. International Conference on Distributed Computing and Networking 2021, 46-55.
Crossref
Oskar Lundström, Michel Raynal, Elad Michael Schiller​‌. (2021) Self-Stabilizing Indulgent Zero-degrading Binary Consensus. International Conference on Distributed Computing and Networking 2021, 106-115.
Crossref
Karine Altisen, Stéphane Devismes, Anaïs Durand, Colette Johnen, Franck Petit​‌. (2021) Self-stabilizing Systems in Spite of High Dynamics. International Conference on Distributed Computing and Networking 2021, 156-165.
Crossref
Oskar Lundström, Michel Raynal, Elad M. Schiller​‌. 2021. Self-stabilizing Uniform Reliable Broadcast. Networked Systems, 296-313.
Crossref
Junya Nakamura, Masahiro Shibata, Yuichi Sudo, Yonghwan Kim​‌. (2020) Self-Stabilizing Construction of a Minimal Weakly ST-Reachable Directed Acyclic Graph. 2020 International Symposium on Reliable Distributed Systems (SRDS), 1-10.
Crossref
Karine Altisen, Stéphane Devismes, Erwan Jahier​‌. 2020. sasa: A SimulAtor of Self-stabilizing Algorithms. Tests and Proofs, 143-154.
Crossref
Sergio Rajsbaum, Michel Raynal, Karla Vargas​‌. 2020. Brief Announcement: Leader Election in the ADD Communication Model. Stabilization, Safety, and Security of Distributed Systems, 229-234.
Crossref
 



Prev. lecture | Next lecture
View/Print PDF (1694 KB)
View PDF Plus (1694 KB)
Add to favorites
Email to a friend
TOC Alert | Citation Alert What is RSS?

Quick Search
for
Authors:
Karine Altisen
Stéphane Devismes
Swan Dubois
Franck Petit
Keywords:
distributed computing
distributed algorithms
fault tolerance
transient faults
self-stabilization
convergence
closure
stabilization time
atomic-state model
daemons
Home | Synthesis | Search | Profile | Access | Author | Help | About
Technology Partner - Atypon Systems, Inc.