Search

Unlike qualitative properties such as correctness (safety and liveness), quantitative properties of distributed algorithms have only been certified in very few works. This work is the first attempt to certify time complexity bounds of fault-tolerant distributed algorithms. Our case study consists in formally proving, using the Coq proof assistant, the time complexity of the first Dijkstra’s self-stabilizing token ring algorithm. In more detail, we formally prove both the self-stabilization and exact worst-case stabilization time of this algorithm assuming fully asynchronous settings. This latter result is obtained in two main steps. First, we certify a non-trivial upper bound on the stabilization time, i.e., every execution contains at most steps, where N is the number of nodes. Then, we exhibit, for every ring of at least four nodes, a possible execution whose complexity exactly matches that upper bound. Notice that this tight bound was unknown until now, even among self-stabilization researchers.

This article poses a question about a simple localization problem. The question is if an oblivious walker on a line segment can localize the midpoint of the line segment in a finite number of steps observing the direction (i.e., Left or Right) and the distance to the nearest end point. This problem arises from self-stabilizing location problems by autonomous mobile robots with limited visibility , which is an abstract model attracting a wide interest in distributed computing. Contrary to appearances, it is far from trivial whether this simple problem is solvable, and it is not settled yet. This article is concerned with three variants of the problem with a minimal relaxation and presents self-stabilizing algorithms for them. We also show an easy impossibility theorem for bilaterally symmetric algorithms.

Self-stabilizing and silent distributed algorithms for token distribution in rooted tree networks are given. Initially, each process of a graph holds at most l tokens. Our goal is to distribute the tokens uniformly in the whole network so that every process holds exactly k tokens. In the initial configuration, the total number of tokens in the network may not be n k where n is the number of processes in the network. The root process is given the ability to create a new token or remove a token from the network. We aim to minimize the convergence time, the number of token moves, and the space complexity. First, a self-stabilizing token distribution algorithm that converges within O ( n l ) asynchronous rounds and needs Θ ( n h ϵ ) redundant (or unnecessary) token moves is given, where ϵ = min ( k , l − k ) and h is the height of the tree network. Next, two novel mechanisms to reduce the number of redundant token moves are presented. One reduces the number of redundant token moves to O ( n h ) without any additional costs while the other reduces the number of redundant token moves to O ( n ) , but increases the convergence time to O ( n h l ) . All given algorithms have constant memory at each process and each link register.

The maintenance of efficient and robust overlay networks is one of the most fundamental and reoccurring themes in networking. This article presents a survey of state-of-the-art algorithms to design and repair overlay networks in a distributed manner. In particular, we discuss basic algorithmic primitives to preserve connectivity, review algorithms for the fundamental problem of graph linearization, and then survey self-stabilizing algorithms for metric and scalable topologies. We also identify open problems and avenues for future research.

This article investigates the verification of livelock-freedom and self-stabilization on parameterized rings consisting of symmetric, constant space, deterministic, and self-disabling processes. The results of this article have a significant impact on several fields, including scalable distributed systems, resilient and self- * systems, and verification of parameterized systems. First, we identify necessary and sufficient local conditions for the existence of global livelocks in parameterized unidirectional rings with unbounded (but finite) number of processes under the interleaving semantics. Using a reduction from the periodic domino problem, we show that, in general, verifying livelock-freedom of parameterized unidirectional rings is undecidable (specifically, Π 1 0 -complete) even for constant space, deterministic, and self-disabling processes. This result implies that verifying self-stabilization for parameterized rings of self-disabling processes is also undecidable. We also show that verifying livelock-freedom and self-stabilization remain undecidable under (1) synchronous execution semantics, (2) the FIFO consistency model, and (3) any scheduling policy. We then present a new scope-based method for detecting and constructing livelocks in parameterized rings. The proposed semi-algorithm behind our scope-based verification is based on a novel paradigm for the detection of livelocks that totally circumvents state space exploration. Our experimental results on an implementation of the proposed semi-algorithm are very promising as we have found livelocks in parameterized rings in a few microseconds on a regular laptop. The results of this article have significant implications for scalable distributed systems with cyclic topologies.

Guerraoui proposed an indulgent solution for the binary consensus problem. Namely, he showed that an arbitrary behavior of the failure detector never violates safety requirements even if it compromises liveness. Consensus implementations are often used in a repeated manner. Dutta and Guerraoui proposed a zero-degrading solution, \ie during system runs in which the failure detector behaves perfectly, a node failure during one consensus instance has no impact on the performance of future instances. Our study, which focuses on indulgent zero-degrading binary consensus, aims at the design of an even more robust communication abstraction. We do so through the lenses of self-stabilization - a very strong notion of fault-tolerance. In addition to node and communication failures, self-stabilizing algorithms can recover after the occurrence of arbitrary transient faults; these faults represent any violation of the assumptions according to which the system was designed to operate (as long as the algorithm code stays intact). This work proposes the first, to the best of our knowledge, self-stabilizing algorithm for indulgent zero-degrading binary consensus for time-free message-passing systems prone to detectable process failures. The proposed algorithm has an O(1) stabilization time (in terms of asynchronous cycles) from arbitrary transient faults. Since the proposed solution uses an {\Omega} failure detector, we also present the first, to the best of our knowledge, self-stabilizing asynchronous {\Omega} failure detector, which is a variation on the one by Most\'efaoui, Mourgaya, and Raynal.

We propose a self-stabilizing algorithm to construct a minimal weakly $\mathcal{ST}$-reachable directed acyclic graph (DAG), which is suited for routing messages on wireless networks. Given an arbitrary, simple, connected, and undirected graph $G=(V, E)$ and two sets of nodes, senders $\mathcal{S} (\subset V)$ and targets $\mathcal{T} (\subset V)$, a directed subgraph $\vec{G}$ of $G$ is a weakly $\mathcal{ST}$-reachable DAG on $G$, if $\vec{G}$ is a DAG and every sender can reach at least one target, and every target is reachable from at least one sender in $\vec{G}$. We say that a weakly $\mathcal{ST}$-reachable DAG $\vec{G}$ on $G$ is minimal if any proper subgraph of $\vec{G}$ is no longer a weakly $\mathcal{ST}$-reachable DAG. This DAG is a relaxed version of the original (or strongly) $\mathcal{ST}$-reachable DAG, where every target is reachable from every sender. This is because a strongly $\mathcal{ST}$-reachable DAG $G$ does not always exist; some graph has no strongly $\mathcal{ST}$-reachable DAG even in the case $|\mathcal{S}|=|\mathcal{T}|=2$. On the other hand, the proposed algorithm always constructs a weakly $\mathcal{ST}$-reachable DAG for any $|\mathcal{S}|$ and $|\mathcal{T}|$. Furthermore, the proposed algorithm is self-stabilizing; even if the constructed DAG deviates from the reachability requirement by a breakdown or exhausting the battery of a node having an arc in the DAG, this algorithm automatically reconstructs the DAG to satisfy the requirement again. The convergence time of the algorithm is $O(D)$ asynchronous rounds, where $D$ is the diameter of a given graph. We conduct small simulations to evaluate the performance of the proposed algorithm. The simulation result indicates that its execution time decreases when the number of sender nodes or target nodes is large.

In this paper, we evaluate and compare the performance of two approaches, namely self-stabilization and rollback, to handling consistency violating faults (cυf) that occur when a self-stabilizing distributed graph-based program is executed on an eventually consistent key-value store. Consistency violating faults are caused by reading wrong values due to weaker level of consistency provided by the key-value store. One way to deal with these faults is to utilize rollback whereas another way is to rely on the property of self-stabilization that is expected to provide recovery from arbitrary states. We evaluate both these approaches in different case studies -planar graph coloring, arbitrary graph coloring, and maximal matching-as well as for different problem dimensions such as input data characteristics, workload partition, and network latency. We also consider the effect of executing non-stabilizing algorithm with rollback with a similar stabilizing algorithm that does not utilize rollback.

International audience; We initiate research on self-stabilization in highly dynamic identified message-passing systems where dynamics is modeled using time-varying graphs (TVGs). More precisely, we address the self-stabilizing leader election problem in three wide classes of TVGs: the class $TC^B(∆)$ of TVGs with temporal diameter bounded by $∆$, the class $TC^Q(∆)$ of TVGs with temporal diameter quasi-bounded by $∆$, and the class $TC^R$ of TVGs with recurrent connectivity only, where TC^B(∆) ⊆ $TC^Q(∆) ⊆ TC^R$. We first study conditions under which our problem can be solved. Precisely, we introduce the notion of size-ambiguity to show that the assumption on the knowledge of the number n of processes is central. Our results reveal that, despite the existence of unique process identifiers, any deterministic self-stabilizing leader election algorithm working in the TVG class $TC^Q(∆)$ or $TC^R$ cannot be size-ambiguous, justifying why our solutions for those classes assume the exact knowledge of n. We then present three self-stabilizing leader election algorithms for the TVG classes $TC^B(∆)$, $TC^Q(∆)$, and $TC^R$, respectively.

We consider the clock synchronization problem in the (discrete) beeping model: Given a network of n nodes with each node having a clock value δ(v) ∈ {0,... T-1}, the goal is to synchronize the clock values of all nodes such that they have the same value in any round. As is standard in clock synchronization, we assume arbitrary activations for all nodes, i.e., the nodes start their protocol at an arbitrary round (not limited to {0,...,T-1}). We give an asymptotically optimal algorithm that runs in 4D + ⌊ D/⌊ T/4 ⌋ ⌋ · (T mod 4) = O(D) rounds, where D is the diameter of the network. Once all nodes are in sync, they beep at the same round every T rounds. The algorithm drastically improves on the O(T D)-bound of [2] (where T is required to be at least 4n, so the bound is no better than O(nD)). Our algorithm is very simple as nodes only have to maintain 3 bits in addition to the ⌈ log T ⌉ bits needed to maintain the clock. Furthermore we investigate the complexity of self-stabilizing solutions for the clock synchronization problem: We first show lower bounds of Ω(max{T,n}) rounds on the runtime and Ω(log(max{T,n})) bits of memory required for any such protocol. Afterwards we present a protocol that runs in O(max{T,n}) rounds using at most O(log(max{T,n})) bits at each node, which is asymptotically optimal with regards to both, runtime and memory requirements.

We give a silent self-stabilizing algorithm for the generalized minimal k-dominating set problem in a connected distributed network G. Given a positive integer k and two sets of processes R ⁎ ⊆ D ⁎ , the problem is to find a set D which is minimal subject to the conditions that R ⁎ ⊆ D ⊆ D ⁎ and that D is k-dominating relative to D ⁎ , meaning that every process within distance k of D ⁎ is also within distance k of D. The algorithm is order-invariant, requires O ( log ⁡ N + log ⁡ k ) space per process, works under the distributed unfair scheduler, and converges in O ( N + k ) rounds, where N is a given upper bound on the number of processes.

International audience; We consider snap-stabilizing algorithms in anonymous networks. Self-stabilizing algorithms are well known fault tolerant algorithms : a self-stabilizing algorithm will eventually recover from arbitrary transient faults. On the other hand, an algorithm is snap-stabilizing if it can withstand arbitrary initial values and immediately satisfy its safety requirement. It is a subset of self-stabilizing algorithms. Distributed tasks that are solvable with self-stabilizing algorithms in anonymous networks have already been characterized by Boldi and Vigna in [BV02b]. In this paper, we show how the more demanding snap-stabilizing algorithms can be handled with standard tools for (not stabilizing) algorithms in anonymous networks. We give a characterization of which tasks are solvable by snap-stabilizing algorithms in anonymous networks. We also present a snap-stabilizing version of Mazurkiewicz' enumeration algorithm. This work exposes, from a task-equivalence point of view, the complete correspondence in anonymous networks between self or snap-stabilizing tasks and distributed tasks with various termination detection requirements.

Airborne sensor platforms are becoming increasingly significant for both civilian and military operations; yet, at present, their sensors are typically idle for much of their flight time, e.g., while the sensor-equipped platform is in transit to and from the locations of sensing tasks. The sensing needs of many other potential information consumers might thus be served by sharing such sensors, thereby allowing other information consumers to opportunistically task them during their otherwise unscheduled time, as well as enabling other improvements, such as decreasing the number of platforms needed to achieve a goal and increasing the resilience of sensor tasks through duplication. We have implemented a prototype system realizing these goals in Mission-Driven Tasking of Information Producers (MTIP), which leverages an agent-based representation of tasks and sensors to enable fast, effective, and adaptive opportunistic sharing of airborne sensors. Using a simulated large-scale disaster-response scenario populated with publicly available Geographic Information System (GIS) datasets, we demonstrate that correlations in task location are likely to lead to a high degree of potential for sensor-sharing. We then validate that our implementation of MTIP can successfully carry out such sharing, showing that it increases the number of sensor tasks served, reduces the number of platforms required to serve a given set of sensor tasks, and adapts well to radical changes in flight path.

A fundamental problem for overlay networks is to safely exclude leaving nodes, i.e., the nodes requesting to leave the overlay network are excluded from it without affecting its connectivity. There are a number of studies for safe node exclusion if the overlay is in a well-defined state, but almost no formal results are known for the case in which the overlay network is in an arbitrary initial state, i.e., when looking for a self-stabilizing solution for excluding leaving nodes. We study this problem in two variants: the Finite Departure Problem$$\mathcal {FDP}$$ and the Finite Sleep Problem$$\mathcal {FSP}$$. In the $$\mathcal {FDP}$$ the leaving nodes have to irrevocably decide when it is safe to leave the network, whereas in the $$\mathcal {FSP}$$, this leaving decision does not have to be final: the nodes may resume computation when woken up by an incoming message. We are the first to present a self-stabilizing protocol for the $$\mathcal {FDP}$$ and the $$\mathcal {FSP}$$ that can be combined with a large class of overlay maintenance protocols so that these are then guaranteed to safely exclude leaving nodes from the system from any initial state while operating as specified for the staying nodes. In order to formally define the properties these overlay maintenance protocols have to satisfy, we identify four basic primitives for manipulating edges in an overlay network that might be of independent interest.

We consider the population protocol (PP) model used to represent a collection of finite-state mobile agents that interact with each other to accomplish a common task. Motivated by the well-known BZ reaction, we address the problem of autonomously generating an oscillatory execution from any initial configuration (i.e., in a self-stabilizing manner). For deterministic PPs under a deterministic scheduler, we show that the self-stabilizing leader election (SS-LE) problem and the self-stabilizing oscillation (SS-OS) problem are equivalent, in the sense that an SS-OS protocol is constructible from a given SS-LE protocol, and vice versa, which unfortunately implies that (1) resorting to a leader is inevitable (although we seek a decentralized solution), (2) n states are necessary to create oscillations of amplitude n, where n is the number of agents (although we seek a memory-efficient solution). Aiming at reducing the space complexity, we present some deterministic oscillatory PPs under a uniform random scheduler.

Two silent self-stabilizing asynchronous distributed algorithms are given for the leader election problem in a dynamic network with unique IDs. A leader is elected for each connected component of the network. A BFS DAG, rooted at the leader, is constructed in each component. The construction takes O(Diam) rounds, where Diam is the maximum diameter of any component. Both algorithms are self-stabilizing, silent, and work under the unfair daemon, but use one unbounded integer variable. Algorithm DLE selects an arbitrary process to be the leader of each component. Algorithm DLEND (Distributed Leader Election No Dithering) has the incumbency property and the no dithering property. If the configuration is legitimate and a topological fault occurs, each component will elect, if possible, an incumbent to be its leader, i.e., a process which was a leader before the fault. Furthermore, during this computation, no process will change its choice of leader more than once.

The purpose of the paper is to present the first self-stabilizing algorithm for finding \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n-1$$\end{document} one-to-many node-disjoint paths in message passing model. Two paths in a network are said to be node disjoint if they do not share any nodes except for the endpoints. Our proposed algorithm works on n-dimensional star networks \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$S_n$$\end{document}. Given a source node s and a set of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$D = \{d_1, d_2, ...,d_{n-1} \}$$\end{document} of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n-1$$\end{document} destination nodes in the n-dimensional star network, our algorithm constructs \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n-1$$\end{document} node-disjoints paths \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P_1, P_2,...,P_{n-1}$$\end{document}, where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P_i$$\end{document} is a path from s to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$d_i$$\end{document}, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1 \le i \le n-1$$\end{document}. Since the proposed solution is self-stabilizing [7], it does not require initialization and withstands transient faults. The stabilization time of our algorithm is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n^2)$$\end{document} rounds.

International audience; We present SASA, an open-source SimulAtor of Self-stabilizing Algorithms. Self-stabilization defines the ability of a distributed algorithm to recover after transient failures. SASA is implemented as a faithful representation of the atomic-state model. This model is the most commonly used in the self-stabilizing area to prove both the correct operation and complexity bounds of self-stabilizing algorithms. SASA encompasses all features necessary to debug, test, and analyze self-stabilizing algorithms. Algorithm's properties can be checked using formal test oracles. Asynchrony is modeled by programmable stochastic daemons playing the role of input sequence generators.

We present preliminary results on the last topic we collaborate with our late friend, Professor Ajoy Kumar Datta (1958–2019), who prematurely left us a few months ago. In this work, we shed new light on a self-stabilizing wave algorithm proposed by Colette Johnen in 1997 [12]. This algorithm constructs a BFS spanning tree in any connected rooted network. Nowadays, it is still the best existing self-stabilizing BFS spanning tree construction in terms of memory requirement, i.e., it only requires \(\varTheta (1)\) bits per edge. However, it has been proven assuming a weakly fair daemon. Moreover, its stabilization time was unknown. Here, we study the slightly modified version of this algorithm, still keeping the same memory requirement. We prove the self-stabilization of this variant under the distributed unfair daemon and show a stabilization time in \(O({\mathcal {D}}\cdot n^2)\) rounds, where \({\mathcal {D}}\) is the network diameter and n the number of processes.

This paper considers the Byzantine consensus problem for nodes with binary inputs. The nodes are interconnected by a network represented as an undirected graph, and the system is assumed to be synchronous. Under the classical point-to-point communication model, it is well-known [7] that the following two conditions are both necessary and sufficient to achieve Byzantine consensus among $n$ nodes in the presence of up to $f$ Byzantine faulty nodes: $n \ge 3f+1$ and vertex connectivity at least $2f+1$. In the classical point-to-point communication model, it is possible for a faulty node to equivocate, i.e., transmit conflicting information to different neighbors. Such equivocation is possible because messages sent by a node to one of its neighbors are not overheard by other neighbors. This paper considers the local broadcast model. In contrast to the point-to-point communication model, in the local broadcast model, messages sent by a node are received identically by all of its neighbors. Thus, under the local broadcast model, attempts by a node to send conflicting information can be detected by its neighbors. Under this model, we show that the following two conditions are both necessary and sufficient for Byzantine consensus: vertex connectivity at least $\lfloor 3f/2 \rfloor + 1$ and minimum node degree at least $2f$. Observe that the local broadcast model results in a lower requirement for connectivity and the number of nodes $n$, as compared to the point-to-point communication model. We extend the above results to a hybrid model that allows some of the Byzantine faulty nodes to equivocate. The hybrid model bridges the gap between the point-to-point and local broadcast models, and helps to precisely characterize the trade-off between equivocation and network requirements.

Self-stabilization is a versatile fault-tolerance approach that characterizes the ability of a system to eventually resume a correct behavior after any finite number of transient faults. In this paper, we propose a self-stabilizing reset algorithm working in anonymous networks. This algorithm resets the network in a distributed non-centralized manner, i.e., it is multi-initiator, as each process detecting an inconsistency may initiate a reset. It is also cooperative in the sense that it coordinates concurrent reset executions in order to gain efficiency. Our approach is general since our reset algorithm allows to build self-stabilizing solutions for various problems and settings. As a matter of facts, we show that it applies to both static and dynamic specifications since we propose efficient self-stabilizing reset-based algorithms for the (1-minimal) $f,g)-alliance (a generalization of the dominating set problem) in identified networks and the unison problem in anonymous networks. Notice that these two latter instantiations enhance the state of the art. Indeed, in the former case, our solution is more general than the previous ones; while in the latter case, the complexity of the proposed unison algorithm is better than that of previous solutions of the literature.

We study the following synchronous process that we call repeated balls-into-bins. The process is started by assigning n balls to n bins in an arbitrary way. Then, in every subsequent round, one ball is chosen according to some fixed strategy (random, FIFO, etc) from each non-empty bin, and re-assigned to one of the n bins uniformly at random. This process corresponds to a non-reversible Markov chain and our aim is to study its self-stabilization properties with respect to the maximum(bin) load and some related performance measures. We define a configuration (i.e., a state) legitimate if its maximum load is O(log n). We first prove that, starting from any legitimate configuration, the process will only take on legitimate configurations over a period of length bounded by any polynomial in n, with high probability (w.h.p.). Further we prove that, starting from any configuration, the process converges to a legitimate configuration in linear time, w.h.p. This implies that the process is self-stabilizing w.h.p. and, moreover, that every ball traverses all bins in O(n log2n) rounds, w.h.p. The latter result can also be interpreted as an almost tight bound on the cover time for the problem of parallel resource assignment in the complete graph.

Consider a complete communication network of $n$ nodes, where the nodes receive a common clock pulse. We study the synchronous $c$-counting problem: given any starting state and up to $f$ faulty nodes with arbitrary behaviour, the task is to eventually have all correct nodes labeling the pulses with increasing values modulo $c$ in agreement. Thus, we are considering algorithms that are self-stabilising despite Byzantine failures. In this work, we give new algorithms for the synchronous counting problem that (1) are deterministic, (2) have optimal resilience, (3) have a linear stabilisation time in $f$ (asymptotically optimal), (4) use a small number of states, and consequently, (5) communicate a small number of bits per round. Prior algorithms either resort to randomisation, use a large number of states and need high communication bandwidth, or have suboptimal resilience. In particular, we achieve an exponential improvement in both state complexity and message size for deterministic algorithms. Moreover, we present two complementary approaches for reducing the number of bits communicated during and after stabilisation., 25 pages, 1 figure. Extended and revised version of two conference reports

This paper presents a novel two-step method for automated design of self-stabilization. The first step enables the specification of legitimate states and an intuitive (but imprecise) specification of the desired functional behaviors in the set of legitimate states (hence the term “shadow”). After creating the shadow specifications, we systematically introduce the main variables and the topology of the desired self-stabilizing system. Subsequently, we devise a parallel and complete backtracking search towards finding a self-stabilizing solution that implements a precise version of the shadow behaviors, and guarantees recovery to legitimate states from any state. To the best of our knowledge, the shadow/puppet synthesis is the first sound and complete method that exploits parallelism and randomization along with the expansion of the state space towards generating self-stabilizing systems that cannot be synthesized with existing methods. We have validated the proposed method by creating both a sequential and a parallel implementation in the context of a software tool, called Protocon. Moreover, we have used Protocon to automatically design three new self-stabilizing protocols that we conjecture to require the minimal number of states per process to achieve stabilization (when processes are deterministic): 2-state maximal matching on bidirectional rings, 5-state token passing on unidirectional rings, and 3-state token passing on bidirectional chains.

Self-stabilizing systems tolerate transient faults by always returning to a legitimate system state within a finite time. This goal is challenged by several system features such as arbitrary system states after faults, various process execution models, and constrained process communication means. This work designs self-stabilizing distributed algorithms from the perspective of game theory, achieving an intended system goal through private goals of processes. We propose a generic game design for identifying a maximal independent set (MIS) or a maximal weighted independent set (MWIS) among all processes in a distributed system. From the generic game several specific games can be defined which differ in whether and how neighboring players influence each other. Turning the game designs into self-stabilizing algorithms, we obtain the first algorithms for the MWIS problem and also the first self-stabilizing MIS algorithm that considers node degree (including an analysis of its performance ratio). We also show how to handle simultaneous moves of processes in some process execution models. Simulation results indicate that, for various representative network topologies, the new algorithm outperforms existing methods in terms of MIS size and convergence rate. For the MWIS problem, the new algorithms performed only slightly worse than centralized greedy counterparts.

A connected dominating set (CDS) is useful in forming a virtual backbone in wireless ad hoc or sensor networks because these networks lack a fixed infrastructure and centralized management. Self-stabilization guarantees that the system tolerates any finite number of transient faults and does not need any initialization. The safe convergence property guarantees that the system quickly converges to a feasible safe configuration, and subsequently converges to a legitimate configuration without violating safety. A previous publication on a safely converging algorithm for the minimum CDS assumed a phase clock synchronizer, which is a very strong assumption. In this paper, we propose the first asynchronous self-stabilizing ( 6 + ? ) -approximation algorithm with safe convergence for the minimum CDS in networks modeled by unit disk graphs (UDGs). We assume that the feasible safe configuration satisfies the condition that a dominating set is constructed. The convergence time to a feasible safe configuration is one round, and the convergence time to a legitimate configuration in which an approximated minimum CDS is constructed is O ( max ? { d 2 , n } ) rounds, and O ( n 6 ) steps.

We consider the standard population protocol model, where (a priori) indistinguishable and anonymous agents interact in pairs according to uniformly random scheduling. The self-stabilizing leader election problem requires the protocol to converge on a single leader agent from any possible initial configuration. We initiate the study of time complexity of population protocols solving this problem in its original setting: with probability 1, in a complete communication graph. The only previously known protocol by Cai, Izumi, and Wada [Theor. Comput. Syst. 50] runs in expected parallel time $\Theta(n^2)$ and has the optimal number of $n$ states in a population of $n$ agents. The existing protocol has the additional property that it becomes silent, i.e., the agents' states eventually stop changing. Observing that any silent protocol solving self-stabilizing leader election requires $\Omega(n)$ expected parallel time, we introduce a silent protocol that uses optimal $O(n)$ parallel time and states. Without any silence constraints, we show that it is possible to solve self-stabilizing leader election in asymptotically optimal expected parallel time of $O(\log n)$, but using at least exponential states (a quasi-polynomial number of bits). All of our protocols (and also that of Cai et al.) work by solving the more difficult ranking problem: assigning agents the ranks $1,\ldots,n$., Comment: fixed typo in Figure 2

International audience

EgeUn###, A self-stabilizing distributed system can initially start at any state and regain a legal state in a finite time without any external intervention. Self-stabilizing systems can automatically recover from faults and they are popular fault tolerant systems. Simulating self-stabilizing systems is a vital task in case of fault-tolerant distributed networks where node and edge updates can be frequent. A discrete-event simulation is a method of simulating the behavior and performance of an algorithm running on a distributed system. To the best of our knowledge, there are few simulators for self-stabilizing distributed algorithms in literature where these simulators are generally outdated and hard to use. In this paper we propose a novel distributed self-stabilizing discrete-event simulator (SELFSIM). SELFSIM is written in C# programming language on.NET Framework and supports up-to-date principles of software development techniques such as separation of concerns. We give the design and implementation of the proposed simulator and compare SELFSIM with its counterparts by considering various parameters such as supported node count (scalability), topological features, daemon (scheduler) types, etc., and show the superiority of our simulator. © 2018 IEEE., National Council for Scientific Research: 215E115, ACKNOWLEDGMENT The authors would like to thank the TUBITAK (Scientific and Technical Research Council of Turkey) for financial support of the project 215E115 which this work belongs to it.

A new phase of evolution of Machine-to-Machine (M2M) communication has started where vertical Internet of Things (IoT) deployments dedicated to a single application domain gradually change to multi-purpose IoT infrastructures that service different applications across multiple industries. New networking technologies are being deployed operating over sub-GHz frequency bands that enable multi-tenant connectivity over long distances and increase network capacity by enforcing low transmission rates to increase network capacity. Such networking technologies allow cloud-based platforms to be connected with large numbers of IoT devices deployed several kilometres from the edges of the network. Despite the rapid uptake of Long-power Wide-area Networks (LPWANs), it remains unclear how to organize the wireless sensor network in a scaleable and adaptive way. This paper introduces a hierarchical communication scheme that utilizes the new capabilities of Long-Range Wireless Sensor Networking technologies by combining them with broadly used 802.11.4-based low-range low-power technologies. The design of the hierarchical scheme is presented in detail along with the technical details on the implementation in real-world hardware platforms. A platform-agnostic software firmware is produced that is evaluated in real-world large-scale testbeds. The performance of the networking scheme is evaluated through a series of experimental scenarios that generate environments with varying channel quality, failing nodes, and mobile nodes. The performance is evaluated in terms of the overall time required to organize the network and setup a hierarchy, the energy consumption and the overall lifetime of the network, as well as the ability to adapt to channel failures. The experimental analysis indicate that the combination of long-range and short-range networking technologies can lead to scalable solutions that can service concurrently multiple applications.

We analyse the impact of transient and Byzantine faults on the construction of a maximal matching in a general network. We consider the self-stabilizing algorithm called AnonyMatch presented by Cohen et al. [3] for computing such a matching. Since self-stabilization is transient fault tolerant, we prove that this algorithm still works under the more difficult context of arbitrary Byzantine faults. Byzantine nodes can prevent nodes close to them from taking part in the matching for an arbitrarily long time. We give bounds on their impact depending on the distance between a non-Byzantine node and the closest Byzantine, called the containment radius. We present the first algorithm tolerating both transient and Byzantine faults under the fair distributed daemon while keeping the best known containment radius. We prove this algorithm converges in \(O(\max (\varDelta n, \varDelta ^2 \log n))\) rounds w.h.p., where n and \(\varDelta \) are the size and the maximum degree of the network, resp.. Additionally, we improve the best known complexity as well as the best containment radius for this problem under the fair central daemon.

International audience; In this paper, we propose a general scheme, called Algorithm $\mathsf{STlC}$, to compute spanning-tree-like data structures on arbitrary networks. $\mathsf{STlC}$ is self-stabilizing and silent and, despite its generality, is also efficient. It is written in the locally shared memory model with composite atomicity assuming the distributed unfair daemon, the weakest scheduling assumption of the model.Its stabilization time is in $n_{\texttt{maxCC}}$ rounds, where $n_{\texttt{maxCC}}$ is the maximum number of processes in a connected component. We also exhibit polynomial upper bounds on its stabilization time in steps and process moves holding for large classes of instantiations of Algorithm $\mathsf{STlC}$.We illustrate the versatility of our approach by proposing several such instantiations that efficiently solve classical problems such as leader election, as well as, unconstrained and shortest-path spanning tree constructions.

Let t a and t b be a pair of relatively prime positive integers. We work on chains of n ( t a + t b ) agents which form together an upper and rightward directed path of the grid Z 2 from O = ( 0 , 0 ) to M = ( n t a , n t b ) . We are interested on evolution rules such that, at each time step, an agent is randomly chosen on the chain and is allowed to jump to another site of the grid preserving the connectivity of the chain and the endpoints. The rules must be local, i.e., the decision of jumping or not only depends on the neighborhood of fixed size s of the randomly chosen agent, and not on the parameters t a , t b , n . Moreover, the parameter s only depends on t a + t b and not on n. In this paper, we design a rule such that, starting from any chain which does not cross the continuous line segment [ O , M ] , this rule reorganizes this chain into one of the best possible approximations of [ O , M ] . The stabilization is reached after O ( ( n ( t a + t b ) ) 4 ) iterations, in average. The work presented here is at the crossroad of many different domains such as modeling a stabilizing process in crystallography, stochastic cellular automata, organizing a line of robots in distributed algorithms (the robot chain problem) and Christoffel words in language theory.

This paper gives a brief presentation of a comprehensive study on the necessary and sufficient state space conditions for the deterministic naming task in the population protocol model. This problem is studied under various combinations of model assumptions: weak or global fairness, arbitrary or uniform initialization of agents, existence or absence of a distinguishable agent (arbitrarily initialized or not), possibility of breaking symmetry in pair-wise interactions (symmetric or asymmetric transitions). For each possible combination of these assumptions, either an impossibility is proven or the necessary exact number of states (per mobile agent) is determined and an appropriate space-optimal naming protocol is given.

The tutorial provides an overview of the principles and "pearls'' of constructing, maintaining and optimizing network topologies, such as peer-to-peer overlays or datacenter interconnects. The tutorial consists of two parts: Self-stabilization: In the first part, we start simple by discussing basic mechanisms to reconfigure networks while maintaining connectivity. You will then learn how to design and analyze self-stabilizing algorithms for line topologies as well as more sophisticated networks such as hypercubes. A self-stabilizing algorithm guarantees that the network will automatically reconfigure to a "good topology" from an arbitrary initial state. Self-optimization: After we have learned how to design self-stabilizing networks, we will consider algorithms to design self-adjusting resp. "self-optimizing" networks: networks which not only "repair" themselves but also optimize themselves towards the demand. The study of such self-adjusting networks is motivated by emerging technologies in the context of datacenters and wide-area networks, allowing to reconfigure networks at runtime.

By introducing programmability, automated verification, and innovative debugging tools, Software-Defined Networks (SDNs) are poised to meet the increasingly stringent dependability requirements of today's communication networks. However, the design of fault-tolerant SDNs remains an open challenge. This paper considers the design of dependable SDNs through the lenses of self-stabilization – a very strong notion of fault-tolerance. In particular, we develop algorithms for an in-band and distributed control plane for SDNs, called Renaissance, which tolerates a wide range of (concurrent) controller, link, and communication failures. Our self-stabilizing algorithms ensure that after the occurrence of an arbitrary combination of failures, (i) every non-faulty SDN controller can eventually reach any switch in the network within a bounded communication delay (in the presence of a bounded number of concurrent failures) and (ii) every switch is managed by at least one non-faulty controller. We evaluate Renaissance through a rigorous worst-case analysis as well as a prototype implementation (based on OVS and Floodlight), and we report on our experiments using Mininet.

In this paper, we formalize design patterns, commonly used in the self-stabilizing area, to obtain general statements regarding both correctness and time complexity guarantees. Precisely, we study a general class of algorithms designed for networks endowed with a sense of direction describing a spanning forest (e.g., a directed tree or a network where a directed spanning tree is available) whose characterization is a simple (i.e., quasi-syntactic) condition. We show that any algorithm of this class is (1) silent and self-stabilizing under the distributed unfair daemon, and (2) has a stabilization time which is polynomial in moves and asymptotically optimal in rounds. To illustrate the versatility of our method, we review several existing works where our results apply.

In 1974 Dijkstra introduced the seminal concept of self-stabilization that turned out to be one of the main approaches to fault-tolerant computing. We show here how his three solutions can be formalized and reasoned about using the concepts of game theory. We also determine the precise number of steps needed to reach self-stabilization in his first solution.

Research in system stabilization has traditionally relied on the availability of a complete system implementation. As such, it would appear that the scalability and reusability of stabilization is limited in practice. To redress this perception, in this paper, we show for the first time that system stabilization may be designed knowing only the system specification but not the system implementation. We refer to stabilization designed thus as specification-based design of stabilization and identify “local everywhere specifications” and “convergence refinements” as being amenable to the specification-based design of stabilization. Using our approach, we present the design of Dijkstra’s four-state stabilizing token-ring system starting from an abstract fault-intolerant token-ring system. We also present an illustration of automated design of specification-based stabilization on a three-state token-ring system.

Self stabilization is an important paradigm for the autonomous recovery of a distributed system from transient failures such as energy depletion of nodes and disrupted connections. It has been used in wireless sensor networks (WSN) as these networks are expected to automatically recover from a transient fault without human intervention. Graph matching is fundamental a graph theory problem which has a broad application range in WSNs and it has been studied extensively in self-stabilizing settings. In this work, we build a simulation model and perform tests to evaluate the fault tolerance properties of self-stabilizing matching algorithms. To the best of our knowledge, this is the first practical evaluation of these algorithms. Considering WSNs, we assume distributed fair and synchronous schedulers. Simulation results have shown that there is a tradeoff between stabilization time of algorithms and the quality of their results. The improvement algorithms which has better lower bounds give better matchings at the cost of longer durations of instability.

Byzantine Fault Tolerant (BFT) replication leverages highly available cloud services and can facilitate the implementation of distributed ledgers, e.g., the blockchain. Systems providing BFT State Machine Replication (SMR) work under severe system assumptions, for example, that less than a third of replicas may suffer a Byzantine failure. Infrequent arbitrary violations of such design assumptions, may lead the system to an unintended state, and render it unavailable thereafter, requiring human intervention. Self-stabilization is a highly desirable system property that can complement Byzantine fault tolerant systems, and allow them to both tolerate Byzantine-failures and automatically recovery from any unintended state that assumption violations may lead to.This paper contributes the first self-stabilizing State Machine Replication service that is based on failure detectors. We suggest an implementable self-stabilizing failure detector to monitor both responsiveness and the replication progress. We thus encapsulate weaker synchronization guarantees than the previous self-stabilizing BFT SMR solution. We follow the seminal paper by Castro and Liskov of Practical Byzantine Fault Tolerance and focus on the self-stabilizing perspective. This work can aid towards building distributed blockchain system infrastructure enhanced with the self-stabilization design criteria. 84 100

In this paper, we focus on the implementation of distributed programs in using a key-value store where the state of the nodes is stored in a replicated and partitioned data store to improve performance and reliability. Applications of such algorithms occur in weather monitoring, social media, etc. We argue that these applications should be designed to be stabilizing so that they recover from an arbitrary state to a legitimate state. Specifically, if we use a stabilizing algorithm then we can work with more efficient implementations that provide eventual consistency rather than sequential consistency where the data store behaves as if there is just one copy of the data. We find that, although the use of eventual consistency results in consistency violation faults (cvf) where some node executes its action incorrectly because it relies on an older version of the data, the overall performance of the resulting protocol is better. We use experimental analysis to evaluate the expected improvement. We also identify other variations of stabilization that can provide additional guarantees in the presence of eventual consistency.Finally, we note that if the underlying algorithm is not stabilizing, even a single \cvf may cause the algorithm to fail completely thereby making it impossible to benefit from this approach., Comment: submission to ICDCN 2018

Vertex cover (VC) is one of the most fundamental graph-theoretical problems and has been widely used in wireless sensor networks (WSNs), particularly for the link monitoring problem. It is well known that a solution to the independent set problem (IS), which is another fundamental graph-theoretical problem, is complement of a VC. Self- stabilization is an important concept for designing fault tolerance systems. There have been many self-stabilizing VC and IS algorithms in the field. Even though a self-stabilizing IS algorithm can provide VC solutions, it does not give a theoretical guarantee on approximation ratio. In this work, we focus on practical fault tolerance performance of self- stabilizing IS algorithms in case of a vertex cover problem, particularly link monitoring in WSNs. We implement all existing self-stabilizing VC and IS algorithms and make simulations assuming a WSN in which nodes run synchronously. Results show that self-stabilizing IS algorithms in general are able to find better covers than VC algorithms, as they provide roughly 15% smaller solution sets. Furthermore, IS algorithms that run under distributed scheduler converges to a desired configuration in considerably less number of rounds than VC algorithms.

International audience; We study theoretical and practical aspects of five of the most well-known self-stabilizing dining philosophers algorithms. We theoretically prove that three of them are incorrect. For practical evaluation, we simulate these five algorithms as well as two classic non-self-stabilizing algorithms and evaluate their fault-tolerance, latency and throughput of critical section access. We present a new combined algorithm that achieves the best throughput of the two remaining correct self-stabilizing algorithms by determining the system load and switching between these basic algorithms. We prove the combined algorithm correct, simulate it and study its performance characteristics.

Self-stabilization refers to the ability of systems to recover after temporal violations of conditions required for their correct operation. Such violations may lead the system to an arbitrary state from which it should automatically recover. Today, beyond recovering functionality, there is a need to recover security and confidentiality guarantees as well. To the best of our knowledge, there are currently no self-stabilizing protocols that also ensure recovering confidentiality, authenticity, and integrity properties. Specifically, self-stabilizing systems are designed to regain functionality which is, roughly speaking, desired input output relation, ignoring the security and confidentiality of computation and its state. Distributed (cryptographic) protocols for generic secure and privacy-preserving computation, e.g., secure Multi-Party Computation (MPC), usually ensure secrecy of inputs and outputs, and correctness of computation when the adversary is limited to compromise only a fraction of the components in the system, e.g., the computation is secure only in the presence of an honest majority of involved parties. While there are MPC protocols that are secure against a dishonest majority, in reality, the adversary may compromise all components of the system for a while; some of the corrupted components may then recover, e.g., due to security patches and software updates, or periodical code refresh and local state consistency check and enforcement based on self-stabilizing hardware and software techniques. It is currently unclear if a system and its state can be designed to always fully recover following such individual asynchronous recoveries. This paper introduces Secure Self-stabilizing Computation which answers this question in the affirmative. Secure self-stabilizing computation design ensures that secrecy of inputs and outputs, and correctness of the computation are automatically regained, even if at some point the entire system is compromised. We consider the distributed computation task as the implementation of virtual global finite satiate machine (FSM) to present commonly realized computation. The FSM is designed to regain consistency and security in the presence of a minority of Byzantine participants, e.g., one third of the parties, and following a temporary corruption of the entire system. We use this task and settings to demonstrate the definition of secure self-stabilizing computation. We show how our algorithms and system autonomously restore security and confidentiality of the computation of the FSM once the required corruption thresholds are again respected.

The Undecided-State Dynamics is a well-known protocol for distributed consensus. We analyze it in the parallel PULL communication model on the complete graph with n nodes for the binary case (every node can either support one of two possible colors, or be in the undecided state). An interesting open question is whether this dynamics is an efficient Self-Stabilizing protocol, namely, starting from an arbitrary initial configuration, it reaches consensus quickly (i.e., within a polylogarithmic number of rounds). Previous work in this setting only considers initial color configurations with no undecided nodes and a large bias (i.e., Theta(n)) towards the majority color. In this paper we present an unconditional analysis of the Undecided-State Dynamics that answers to the above question in the affirmative. We prove that, starting from any initial configuration, the process reaches a monochromatic configuration within O(log n) rounds, with high probability. This bound turns out to be tight. Our analysis also shows that, if the initial configuration has bias Omega(sqrt(n log n)), then the dynamics converges toward the initial majority color, with high probability., Leibniz International Proceedings in Informatics (LIPIcs), 117, ISSN:1868-8969, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), ISBN:978-3-95977-086-6

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.

We propose a deterministic silent self-stabilizing algorithm for the weak leader election problem in anonymous trees. Our algorithm is designed in the message passing model, and requires only O(1) bits of memory per edge. It does not necessitate the a priori knowledge of any global parameter on the network. Finally, its stabilization time is at most [Formula: see text] time units, where 𝒟 is the diameter of the network, X is an upper bound on the time to execute some recurrent code by processes, and Imax is the maximal number of messages initially in a link.

In this paper, we propose a new self-stabilizing algorithm for minimal weakly connected dominating sets (called algorithm $$\mathtt{MWCDS}$$MWCDS). For an arbitrary connected graph with $$n$$n nodes, algorithm $$\mathtt{MWCDS}$$MWCDS terminates in $$O(n)$$O(n) steps using a synchronous daemon. The space requirement at each node is $$O(\log n)$$O(logn) bits. In the literature, the best reported stabilization time for a minimal weakly connected dominating set algorithm is $$O(nmA)$$O(nmA) under a distributed daemon, where $$m$$m is the number of edges and $$A$$A is the number of moves to construct a breadth-first tree.