Search

It is almost fifty years since Dijkstra coined the term "self-stabilization" to denote a distributed system able to recover correct behavior starting from any arbitrary (even unreachable) configuration. His seminal paper triggered many works since then, exploring over the years new variants of the original concept, new application domains, and new complexity results. While the huge majority of those contributions relates to theory, considering computability and worst case complexity issues, this talk revisits old and recent contributions from the prism of "realistic" distributed systems, aiming to address the following question: is self-stabilization relevant in practice for distributed systems?, LIPIcs, Vol. 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022), pages 3:1-3:1

International audience; It is almost fifty years since Dijkstra coined the term "self-stabilization" to denote a distributed system able to recover correct behavior starting from any arbitrary (even unreachable) configuration. His seminal paper triggered many works since then, exploring over the years new variants of the original concept, new application domains, and new complexity results. While the huge majority of those contributions relates to theory, considering computability and worst case complexity issues, this talk revisits old and recent contributions from the prism of ``realistic'' distributed systems, aiming to address the following question: is self-stabilization relevant in practice for distributed systems?

In sensor networks, correct clocks have arbitrary starting offsets and nondeterministic fluctuating skews. We consider an adversary that aims at tampering with the clock synchronization by intercepting messages, replaying intercepted messages (after the adversary’s choice of delay), and capturing nodes (i.e., revealing their secret keys and impersonating them). We present an efficient clock sampling algorithm which tolerates attacks by this adversary, collisions, a bounded amount of losses due to ambient noise, and a bounded number of captured nodes that can jam, intercept, and send fake messages. The algorithm is self-stabilizing, so if these bounds are temporarily violated, the system can efficiently stabilize back to a correct state. Using this clock sampling algorithm, we construct the first self-stabilizing algorithm for secure clock synchronization in sensor networks that is resilient to the aforementioned adversarial attacks.

International audience; A self-stabilizing algorithm, regardless of the initial system state, converges in finite time to a set of states that satisfy a legitimacy predicate without the need for explicit exception handler of backward recovery. The vertex coloration problem consists in ensuring that every node in the system has a color that is different from any of its neighbors. We provide three self-stabilizing solutions to the vertex coloration problem under unfair scheduling that are based on a greedy technique. We use at most $B+1$ different colors (in complete graphs), where $B$ is the graph degree, and ensure stabilization within $O(n\times B)$ processor atomic steps. Two of our algorithms deal with uniform networks where nodes do not have identifiers. Our solutions lead to directed acyclic orientation and maximal independent set construction at no additional cost.

26 pages; We survey existing scheduling hypotheses made in the literature in self-stabilization, commonly referred to under the notion of daemon. We show that four main characteristics (distribution, fairness, boundedness, and enabledness) are enough to encapsulate the various differences presented in existing work. Our naming scheme makes it easy to compare daemons of particular classes, and to extend existing possibility or impossibility results to new daemons. We further examine existing daemon transformer schemes and provide the exact transformed characteristics of those transformers in our taxonomy.

Self-stabilization is a versatile approach to fault-tolerance since it permits a distributed system to recover from any transient fault that arbitrarily corrupts the contents of all memories in the system. Byzantine tolerance is an attractive feature of distributed systems that permits to cope with arbitrary malicious behaviors. We consider the well known problem of constructing a maximum metric tree in this context. Combining these two properties leads to some impossibility results. In this paper, we provide two necessary conditions to construct maximum metric tree in presence of transients and (permanent) Byzantine faults.

Distributed fault-tolerance can mask the effect of a limited number of permanent faults, while self-stabilization provides forward recovery after an arbitrary number of transient fault hit the system. FTSS protocols combine the best of both worlds since they are simultaneously fault-tolerant and self-stabilizing. To date, FTSS solutions either consider static (i.e. fixed point) tasks, or assume synchronous scheduling of the system components. In this paper, we present the first study of dynamic tasks in asynchronous systems, considering the unison problem as a benchmark. Unison can be seen as a local clock synchronization problem as neighbors must maintain digital clocks at most one time unit away from each other, and increment their own clock value infinitely often. We present many impossibility results for this difficult problem and propose a FTSS solution when the problem is solvable that exhibits optimal fault containment.

A distributed algorithm is self-stabilizing if after faults and attacks hit the system and place it in some arbitrary global state, the system recovers from this catastrophic situation without external intervention in finite time. In this paper, we consider the problem of constructing self-stabilizingly a \emph{maximal independent set} in uniform unidirectional networks of arbitrary shape. On the negative side, we present evidence that in uniform networks, \emph{deterministic} self-stabilization of this problem is \emph{impossible}. Also, the \emph{silence} property (\emph{i.e.} having communication fixed from some point in every execution) is impossible to guarantee, either for deterministic or for probabilistic variants of protocols. On the positive side, we present a deterministic protocol for networks with arbitrary unidirectional networks with unique identifiers that exhibits polynomial space and time complexity in asynchronous scheduling. We complement the study with probabilistic protocols for the uniform case: the first probabilistic protocol requires infinite memory but copes with asynchronous scheduling, while the second probabilistic protocol has polynomial space complexity but can only handle synchronous scheduling. Both probabilistic solutions have expected polynomial time complexity.

We analyze in this paper the longest increasing contiguous sequence or maximal ascending run of random variables with common uniform distribution but not independent. Their dependence is characterized by the fact that two successive random variables cannot take the same value. Using a Markov chain approach, we study the distribution of the maximal ascending run and we develop an algorithm to compute it. This problem comes from the analysis of several self organizing protocols designed for large scale wireless sensor networks, and we show how our results apply to this domain.

Toward self-stabilizing large-scale systems.; Vers l'auto-stabilisation des systèmes à grande échelle.

When a distributed system is subject to transient failures that arbitrarily modify its state, it is crucial to recover a correct behavior within finite time. Self-stabilization offers such a guarantee, but usually uses large resources. In this thesis, we focus on minimizing these resources when such solutions exist.We introduced the concept of transient failure detectors, oracles that are called by processors, which notify if transient failures occurred within constant time. Our implementation enables classifying classic problems according to the specific resources dedicated to error detection.A natural extension was to show that a local property on the local code executed by each processor is sufficient to guarantee self-stabilization of the whole system, whatever the computation assumptions and communication graph may be. Since the original algorithm is not modified, it is overhead-free. Similarly, we developed two synchronizers that enable dynamic tasks to be solved self-stabilizingly, whose memory overhead is constant. Moreover, one of them is snap-stabilizing. Finally, we presented a general technique to systematically reduce the communicationcost, assuming a bounded retransmission delay, and we gave a general framework and tools to design self-stabilizing algorithms in this context.; Quand un système réparti est sujet à des défaillances transitoires qui modifient arbitrairement son état, il est crucial de pouvoir retrouver un comportement correct au bout d'un temps fini. L'auto-stabilisation présente une telle garantie, mais en général au prix de ressources importantes. Dans cette thèse, notre démarche a consisté à minimiser ces ressources lorsque cela était possible. Nous avons développé le concept de détecteur de défaillances transitoires, des oracles appelés par les processeurs du système, qui indiquent si des défaillances transitoires sont survenues, en un temps constant. Notre implantation permet de classifier les problèmes classiques suivant les ressources spécifiques nécessaires à la détection d'une erreur. Pour les tâches statiques, une suite naturelle a été de montrer qu'une condition sur le code localement exécuté par chaque processeur pouvait être suffisante pour garantir l'auto-stabilisation du système tout entier, indépendamment des hypothèses d'exécution et de la topologie du graphe de communication. Du fait que l'algorithme n'est pas modifié, il est forcément sans surcoût. De manière duale, nous avons développé des outils de synchronisation permettant de construire des algorithmes auto-stabilisants pour des spécifications dynamiques avec un surcoût en mémoire constant, c'est à dire indépendant de la taille du réseau. En outre, l'un des algorithmes présentés est instantanément stabilisant. Enfin, nous avons présenté une technique générale pour réduire systématiquement le coût des communications, en garantissant un délai de retransmission borné, et nous avons donné un cadre général ainsi que des outils d'implantation pour écrire des algorithmes auto-stabilisants dans ce contexte.

When a distributed system is subject to transient failures that arbitrarily modify its state, it is crucial to recover a correct behavior within finite time. Self-stabilization offers such a guarantee, but usually uses large resources. In this thesis, we focus on minimizing these resources when such solutions exist.We introduced the concept of transient failure detectors, oracles that are called by processors, which notify if transient failures occurred within constant time. Our implementation enables classifying classic problems according to the specific resources dedicated to error detection.A natural extension was to show that a local property on the local code executed by each processor is sufficient to guarantee self-stabilization of the whole system, whatever the computation assumptions and communication graph may be. Since the original algorithm is not modified, it is overhead-free. Similarly, we developed two synchronizers that enable dynamic tasks to be solved self-stabilizingly, whose memory overhead is constant. Moreover, one of them is snap-stabilizing. Finally, we presented a general technique to systematically reduce the communicationcost, assuming a bounded retransmission delay, and we gave a general framework and tools to design self-stabilizing algorithms in this context.; Quand un système réparti est sujet à des défaillances transitoires qui modifient arbitrairement son état, il est crucial de pouvoir retrouver un comportement correct au bout d'un temps fini. L'auto-stabilisation présente une telle garantie, mais en général au prix de ressources importantes. Dans cette thèse, notre démarche a consisté à minimiser ces ressources lorsque cela était possible. Nous avons développé le concept de détecteur de défaillances transitoires, des oracles appelés par les processeurs du système, qui indiquent si des défaillances transitoires sont survenues, en un temps constant. Notre implantation permet de classifier les problèmes classiques suivant les ressources spécifiques nécessaires à la détection d'une erreur. Pour les tâches statiques, une suite naturelle a été de montrer qu'une condition sur le code localement exécuté par chaque processeur pouvait être suffisante pour garantir l'auto-stabilisation du système tout entier, indépendamment des hypothèses d'exécution et de la topologie du graphe de communication. Du fait que l'algorithme n'est pas modifié, il est forcément sans surcoût. De manière duale, nous avons développé des outils de synchronisation permettant de construire des algorithmes auto-stabilisants pour des spécifications dynamiques avec un surcoût en mémoire constant, c'est à dire indépendant de la taille du réseau. En outre, l'un des algorithmes présentés est instantanément stabilisant. Enfin, nous avons présenté une technique générale pour réduire systématiquement le coût des communications, en garantissant un délai de retransmission borné, et nous avons donné un cadre général ainsi que des outils d'implantation pour écrire des algorithmes auto-stabilisants dans ce contexte.

In this work, we consider adversarial crash faults of nodes in the network constructors model $[$Michail and Spirakis, 2016$]$. We first show that, without further assumptions, the class of graph languages that can be (stably) constructed under crash faults is non-empty but small. In particular, if an unbounded number of crash faults may occur, we prove that (i) the only constructible graph language is that of spanning cliques and (ii) a strong impossibility result holds even if the size of the graphs that the protocol outputs in populations of size $n$ need only grow with $n$ (the remaining nodes being waste). When there is a finite upper bound $f$ on the number of faults, we show that it is impossible to construct any non-hereditary graph language. On the positive side, by relaxing our requirements we prove that: (i) permitting linear waste enables to construct on $n/(2f)-f$ nodes, any graph language that is constructible in the fault-free case, (ii) partial constructibility (i.e. not having to generate all graphs in the language) allows the construction of a large class of graph languages. We then extend the original model with a minimal form of fault notifications. Our main result here is a fault-tolerant universal constructor: We develop a fault-tolerant protocol for spanning line and use it to simulate a linear-space Turing Machine $M$. This allows a fault-tolerant construction of any graph accepted by $M$ in linear space, with waste $min\{n/2+f(n),\; n\}$, where $f(n)$ is the number of faults in the execution. We then prove that increasing the permissible waste to $min\{2n/3+f(n),\; n\}$ allows the construction of graphs accepted by an $O(n^2)$-space Turing Machine, which is asymptotically the maximum simulation space that we can hope for in this model. Finally, we show that logarithmic local memories can be exploited for a no-waste fault-tolerant simulation of any such protocol.

International audience; We present a new self-stabilizing 1-maximal matching algorithm that works under the distributed unfair daemon for arbitrarily shaped networks. The 1-maximal matching is a 2/3-approximation of a maximum matching, a significant improvement over the 1/2-approximation that is guaranteed by a maximal matching. Our algorithm is efficient (its stabilization time is $O(e)$ moves, where $e$ denotes the number of edges in the network). Besides, our algorithm is optimal with respect to identifiers locality (we assume node identifiers are distinct up to distance three, a necessary condition to withstand arbitrary networks). The proposed algorithm closes the complexity gap between two recent works: Inoue et al. presented a 1-maximal matching algorithm that is $O(e)$ moves but requires the network topology not to contain a cycle of size of multiple of three ; Cohen et al. consider arbitrary topology networks but requires $O(n^3)$ moves to stabilize (where $n$ denotes the number of nodes in the network). Our solution preserves the better complexity of $O(e)$ moves, yet considers arbitrary networks, demonstrating that previous restrictions were unnecessary to preserve complexity results.

50 pages; The final version of this book chapter appears in: Sébastien Tixeuil. Algorithms and Theory of Computation Handbook, Second Edition, chapter Self-stabilizing Algorithms, pages 26.1–26.45. Chapman & Hall/CRC Applied Algorithms and Data Structures. CRC Press, Taylor & Francis Group, November 2009.