Search

Given a boolean predicate $\Pi$ on labeled networks (e.g., proper coloring, leader election, etc.), a self-stabilizing algorithm for $\Pi$ is a distributed algorithm that can start from any initial configuration of the network (i.e., every node has an arbitrary value assigned to each of its variables), and eventually converge to a configuration satisfying $\Pi$. It is known that leader election does not have a deterministic self-stabilizing algorithm using a constant-size register at each node, i.e., for some networks, some of their nodes must have registers whose sizes grow with the size $n$ of the networks. On the other hand, it is also known that leader election can be solved by a deterministic self-stabilizing algorithm using registers of $O(\log \log n)$ bits per node in any $n$-node bounded-degree network. We show that this latter space complexity is optimal. Specifically, we prove that every deterministic self-stabilizing algorithm solving leader election must use $\Omega(\log \log n)$-bit per node registers in some $n$-node networks. In addition, we show that our lower bounds go beyond leader election, and apply to all problems that cannot be solved by anonymous algorithms., Comment: Final journal version for DMTCS (Conference version at OPODIS 2021)

In the population protocol model, many problems cannot be solved in a self-stabilizing manner. However, global knowledge, such as the number of nodes in a network, sometimes enables the design of a self-stabilizing protocol for such problems. For example, it is known that we can solve the self-stabilizing leader election in complete graphs if and only if every node knows the exact number of nodes. In this article, we investigate the effect of global knowledge on the possibility of self-stabilizing population protocols in arbitrary graphs. Specifically, we clarify the solvability of the leader election problem, the ranking problem, the degree recognition problem, and the neighbor recognition problem by self-stabilizing population protocols with knowledge of the number of nodes and/or the number of edges in a network.

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.

Self-stabilization is a property of a distributed system such that, regardless of the legitimacy of its current state, the system behavior shall eventually reach a legitimate state and shall remain legitimate thereafter. The elegance of self-stabilization stems from the fact that it distinguishes distributed systems by a strong fault tolerance property against arbitrary state perturbations. The difficulty of designing and reasoning about self-stabilization has been witnessed by many researchers; most of the existing techniques for the verification and design of self-stabilization are either brute-force, or adopt manual approaches non-amenable to automation. In this dissertation, we first investigate the possibility of automatically designing self-stabilization through global state space exploration. In particular, we develop a set of heuristics for automating the addition of recovery actions to distributed protocols on various network topologies. Our heuristics equally exploit the computational power of a single workstation and the available parallelism on computer clusters. We obtain existing and new stabilizing solutions for classical protocols like maximal matching, ring coloring, mutual exclusion, leader election and agreement. Second, we consider a foundation for local reasoning about self-stabilization; i.e., study the global behavior of the distributed system by exploring the state space of just one of its components. It turns out that local reasoning about deadlocks and livelocks is possible for an interesting class of protocols whose proof of stabilization is otherwise complex. In particular, we provide necessary and sufficient conditions — verifiable in the local state space of every process — for global deadlock- and livelock-freedom of protocols on ring topologies. Local reasoning potentially circumvents two fundamental problems that complicate the automated design and verification of distributed protocols: (1) state explosion and (2) partial state information. Moreover, local proofs of convergence are independent of the number of processes in the network, thereby enabling our assertions about deadlocks and livelocks to apply on rings of arbitrary sizes without worrying about state explosion.

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.

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.

We characterize self-stabilizing functions in population protocols for complete interaction graphs. In particular, we investigate self-stabilization in systems of n finite state agents in which a malicious scheduler selects an arbitrary sequence of pairwise interactions under a global fairness condition. We show a necessary and sufficient condition for self-stabilization. Specifically we show that functions without certain set-theoretic conditions are impossible to compute in a self-stabilizing manner. Our main contribution is in the converse, where we construct a self-stabilizing protocol for all other functions that meet this characterization. Our positive construction uses Dickson’s Lemma to develop the notion of the root set, a concept that turns out to fundamentally characterize self-stabilization in this model. We believe it may lend to characterizing self-stabilization in more general models as well.

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.

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.

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.

We argue that grid structures are a very promising alternative to the standard approach for distributing a clock signal throughout VLSI circuits and other hardware devices. Traditionally, this is accomplished by a delay-balanced clock tree, which distributes the signal supplied by a single clock source via carefully engineered and buffered signal paths.Our approach, termed HEX, is based on a hexagonal grid with simple intermediate nodes, which both control the forwarding of clock ticks in the grid and supply them to nearby functional units. HEX is Byzantine fault-tolerant, in a way that scales with the grid size, self-stabilizing, and seamlessly integrates with multiple synchronized clock sources, as used in multi-synchronous Globally Synchronous Locally Asynchronous (GALS) architectures. Moreover, HEX guarantees a small clock skew between neighbors even for wire delays that are only moderately balanced. We provide both a theoretical analysis of the worst-case skew and simulation results that demonstrate very small typical skew in realistic runs.

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.

International audience

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.

Multi-agent stigmergy forms the basis of explanatory theories for various self-organized biological phenomena, and also serves as an implementation strategy for several important artificial applications. While a number of sophisticated techniques have been used in the modeling and analysis of stigmergic processes, none of them, yet, seem to be drawn from the toolbox of classical distributed computing. Our goals are to investigate and lay the groundwork for the use of classical distributed computing ideas in reasoning about stigmergic computation. Specifically, we investigate case studies that are drawn from the domain of binary matrix pattern sorting. Here, a ‘swarm’ of memory-less and non-communicating agents follow a set of local stigmergic rules to asynchronously sort the binary states of cells in a 2-D grid so as to satisfy some global pattern specification. This domain is attractive as a test-bed because it serves as an abstraction for instances of biological pattern sorting and also because of its stigmergic expressiveness. We demonstrate the application of the following four distributed computing concepts: (1) execution serializability, (2) local checking, (3) variant functions, and (4) indistinguishability (the last as an impossibility proof technique) in the modeling and analysis of our case studies. Based on our preliminary experience with this particular domain, it seems to us that classical distributed computing techniques could be applied further in reasoning about stigmergic systems, perhaps leading to the formulation of a generalized stigmergic computational paradigm based on the principles of distributed computing.

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.

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.

A self-stabilizing system is one that guarantees reaching a set of legitimate states from any arbitrary initial state. Designing distributed self-stabilizing protocols is often a complex task and developing their proof of correctness is known to be significantly more tedious. In this article, we propose an SMT-based method that automatically synthesizes a self-stabilizing protocol, given the network topology of distributed processes and description of the set of legitimate states. Our method can synthesize synchronous, asynchronous, symmetric, and asymmetric protocols for two types of stabilization, namely weak and strong . We also report on successful automated synthesis of a set of well-known distributed stabilizing protocols such as Dijkstra’s token ring, distributed maximal matching, graph coloring, and mutual exclusion in anonymous networks.

Given two functions f and g mapping nodes to non-negative integers, we give a silent self-stabilizing algorithm that computes a minimal ( f , g ) -alliance in an asynchronous network with unique node IDs, assuming that every node p has a degree at least g ( p ) and satisfies f ( p ) ? g ( p ) . Our algorithm is safely converging in the sense that starting from any configuration, it first converges to a (not necessarily minimal) ( f , g ) -alliance in at most four rounds, and then continues to converge to a minimal one in at most 5 n + 4 additional rounds, where n is the size of the network. Our algorithm is written in the shared memory model. It is proven assuming an unfair (distributed) daemon. Its memory requirement is ? ( log n ) bits per process, and it takes O ( n ? Δ 3 ) steps to stabilize, where Δ is the degree of the network. We give an algorithm for the ( f , g ) -alliance, a generalization of several problems.Our algorithm is distributed, self-stabilizing, silent, and safe converging.The complexity analysis shows that it is better than many other related solutions.

Local mutual inclusion is a process synchronization problem where, for each process, at least one of its processes and neighbors must be in the critical section. We propose a self-stabilizing distributed solution to the local mutual inclusion problem. Convergence time of the proposed algorithm is one round under the weakly fair distributed daemon. A self-stabilizing distributed algorithm for the local mutual inclusion problem is presented.The local mutual inclusion is a problem such that for each process P, at least one of P and its neighbors is in critical section.Convergence time of the proposed algorithm is 1 round under weakly fair distributed daemon.

We consider the problem of resource discovery in distributed systems. In particular we give an algorithm, such that each node in a network discovers the address of any other node in the network. We model the knowledge of the nodes as a virtual overlay network given by a directed graph such that complete knowledge of all nodes corresponds to a complete graph in the overlay network. Although there are several solutions for resource discovery, our solution is the first that achieves worst-case optimal work for each node, i.e. the number of addresses ( O ( n ) ) or bits ( O ( n log ? n ) ) a node receives or sends coincides with the lower bound, while ensuring only a linear runtime ( O ( n ) ) on the number of rounds.

We present a new shared memory model, SF shared memory model. In this model, the actions of each node are partitioned into slow actions and fast actions. By contrast, the traditional shared memory model only includes fast actions. Intuitively, slow actions can utilize slightly stale state information to execute successfully. However, fast actions require that the state information they use is most recent.We show that the use of slow actions can substantially benefit in improving performance of programs from the shared memory model to WAC model that has been designed for sensor networks. To illustrate this, we use three protocols concerning problems that need to be solved in sensor networks. We show that under various message loss probabilities, densities, etc., slow actions can improve the performance substantially, since slow actions reduce the performance penalty of fast actions under heavy message loss environments. Moreover, the effectiveness of the slow action increases when there is a higher probability of message loss. None of the existing computational models consider message loss/collision in the distributed systems.WAC model is a model that considers message loss in distributed systems. However, it reduces the performance.Our work is a variation of the shared memory model, namely SF shared memory model.It can improve the performance in the presence of message loss.We present an analytical proof (and evaluations for three protocols) for our SF model.

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.

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.

We present the first implementation of a distributed clock generation scheme for Systems-on-Chip that recovers from an unbounded number of arbitrary transient faults despite a large number of arbitrary permanent faults. We devise self-stabilizing hardware building blocks and a hybrid synchronous/asynchronous state machine enabling metastability-free transitions of the algorithm's states. We provide a comprehensive modeling approach that permits to prove, given correctness of the constructed low-level building blocks, the high-level properties of the synchronization algorithm (which have been established in a more abstract model). We believe this approach to be of interest in its own right, since this is the first technique permitting to mathematically verify, at manageable complexity, high-level properties of a fault-prone system in terms of its very basic components. We evaluate a prototype implementation, which has been designed in VHDL, using the Petrify tool in conjunction with some extensions, and synthesized for an Altera Cyclone FPGA.

Overlay networks are expected to operate in hostile environments, where node and link failures are commonplace. One way to make overlay networks robust is to design self-stabilizing overlay networks, i.e., overlay networks that can handle node and link failures without any external supervision. In this paper, we first describe a simple framework, which we call the Transitive Closure Framework (TCF), for the selfstabilizing construction of an extensive class of overlay networks. Like previous self-stabilizing overlay networks, TCF permits node degrees to grow to Ω(n), independent of the maximum degree of the target overlay network. However, TCF has several advantages over previous work in this area: (i) it is a "framework" and can be used for the construction of a variety of overlay networks, not just a particular network, (ii) it runs in an optimal number of rounds for a variety of overlay networks, and (iii) it can easily be composed with other non-self-stabilizing protocols that can recover from specific bad initial states in a memory-efficient fashion. We demonstrate the power of our framework by deriving from TCF a simple self-stabilizing protocol for constructing Skip+ graphs (Jacob et al., PODC 2009) which presents optimal convergence time from any configuration, and requires only a O(1) factor of extra memory for handling node Joins.

Fault tolerance measures of distributed systems can be calculated precisely by state space analysis of the Markov chain corresponding to the product of the system components. The power of such an approach is inherently confined by the state space explosion, i.e. the exponential growth of the Markov chain in the size of the underlying system. We propose a decompositional method to alleviate this limitation. Lumping is a well-known reduction technique facilitating computation of the relevant measures on the quotient of the Markov chain under lumping equivalence. In order to avoid computation of lumping equivalences on intractably large Markov chains, we propose a system decomposition supporting local lumping on the considerably smaller Markov chains of the subsystems. Recomposing the lumped Markov chains of the subsystems constructs a lumped transition model of the whole system, thus avoiding the construction of the full product chain. An example demonstrates how the limiting window availability (i.e. a particular fault tolerance measure) can be computed for a self-stabilizing system exploiting lumping and decomposition.

We present Corona, a deterministic self-stabilizing algorithm for skip list construction in structured overlay networks. Corona operates in the low-atomicity message-passing asynchronous system model. Corona requires constant process memory space for its operation and, therefore, scales well. We prove the general necessary conditions limiting the initial states from which a self-stabilizing structured overlay network in a message-passing system can be constructed. The conditions require that initial state information has to form a weakly connected graph and it should only contain identifiers that are present in the system. We formally describe Corona and rigorously prove that it stabilizes from an arbitrary initial state subject to the necessary conditions. We extend Corona to construct a skip graph.

Topological self-stabilization is an important concept to build robust open distributed systems (such as peer-to-peer systems) where nodes can organize themselves into meaningful network topologies. The goal is to devise distributed algorithms where nodes forward, insert, and delete links to neighboring nodes, and that converge quickly to such a desirable topology, independently of the initial network configuration. This article proposes a new model to study the parallel convergence time. Our model sheds light on the achievable parallelism by avoiding bottlenecks of existing models that can yield a distorted picture. As a case study, we consider local graph linearization--i.e., how to build a sorted list of the nodes of a connected graph in a distributed and self-stabilizing manner. In order to study the main structure and properties of our model, we propose two variants of a most simple local linearization algorithm. For each of these variants, we present analyses of the worst-case and best-case parallel time complexities, as well as the performance under a greedy selection of the actions to be executed. It turns out that the analysis is non-trivial despite the simple setting, and to complement our formal insights we report on our experiments which indicate that the runtimes may be better in the average case.

Existing approaches for verifying self-stabilization with a symbolic model checker have relied on the use of weak fairness. We point out that this approach has limited scalability. To overcome this limitation, first, we show that if self-stabilization is possible without fairness then the cost of verifying self-stabilization is substantially lower. In fact, we observe from several case studies that the cost of verification under weak fairness is more than 1000 times that of the cost without fairness. For the case where weak fairness is essential for self-stabilization, we demonstrate the feasibility of two approaches for improving scalability: (1) decomposition and (2) utilizing the weaker version of self-stabilization, namely weak stabilization. In the first approach, the designer partitions the program into components where each component satisfies its property without fairness. We show that the first approach enables us to verify Huang's mutual exclusion program for uniform rings with 31 processes (state space 10^1^3^8) whereas without this approach, it was not possible to verify the same program with 5 processes (state space 10^1^0). In the second approach, a weaker version of self-stabilization is verified. For Hoepman's ring-orientation program on odd-length ring, we show that it is possible to verify weak stabilization for 301 processes (state space 10^1^8^1) whereas self-stabilization could not be verified for 9 processes (state space 10^5) under weak fairness. Furthermore, one can utilize transformation algorithms to convert weak stabilizing programs to probabilistically stabilizing programs. Hence, for the case where it is not possible to verify deterministic self-stabilization, one can obtain the assurance provided by probabilistic self-stabilization at a significantly reduced cost. Finally, we also present 5 case studies to illustrate the scalability of stabilization with techniques suggested in this paper.

A key problem when coordinating the behaviour of spatially situated networks, like those typically found in the Internet of Things (IoT), is adaptation to changes impacting network topology, density, and heterogeneity. Computational goals for such systems, however, are often dependent on geometric properties of the continuous environment in which the devices are situated rather than the particulars of how devices happen to be distributed through it. In this article, we identify a new property of distributed algorithms, eventual consistency , which guarantees that computation converges to a final state that approximates a predictable limit, based on the continuous environment, as the density and speed of devices increases. We then identify a large class of programs that are eventually consistent, building on prior results on the field calculus computational model (Beal et al. 2015; Viroli et al. 2015a) that identify a class of self-stabilizing programs. Finally, we confirm through simulation of IoT application scenarios that eventually consistent programs from this class can provide resilient behavior where programs that are only converging fail badly.

We consider a population of n agents which communicate with each other in a decentralized manner, through random pairwise interactions. One or more agents in the population may act as authoritative sources of information, and the objective of the remaining agents is to obtain information from or about these source agents. We study two basic tasks: broadcasting, in which the agents are to learn the bit-state of an authoritative source which is present in the population, and source detection, in which the agents are required to decide if at least one source agent is present in the population or not. We focus on designing protocols which meet two natural conditions: (1) universality, i.e., independence of population size, and (2) rapid convergence to a correct global state after a reconfiguration, such as a change in the state of a source agent. Our main positive result is to show that both of these constraints can be met. For both the broadcasting problem and the source detection problem, we obtain solutions with an expected convergence time of O(logn), from any starting configuration. The solution to broadcasting is exact, which means that all agents reach the state broadcast by the source, while the solution to source detection admits one-sided error on a e-fraction of the population (which is unavoidable for this problem). Both protocols are easy to implement in practice and are self-stabilizing, in the sense that the stated bounds on convergence time hold starting from any possible initial configuration of the system. Our protocols exploit the properties of self-organizing oscillatory dynamics. On the hardness side, our main structural insight is to prove that any protocol which meets the constraints of universality and of rapid convergence after reconfiguration must display a form of non-stationary behavior (of which oscillatory dynamics are an example). We also observe that the periodicity of the oscillatory behavior of the protocol, when present, must necessarily depend on the number #X of source agents present in the population. For instance, our protocols inherently rely on the emergence of a signal passing through the population, whose period is Θ(log(n/#X)) rounds for most starting configurations. The design of phase clocks with tunable frequency may be of independent interest, notably in modeling biological networks.

We investigate self-stabilizing rendezvous algorithms for two synchronous mobile agents. The rendezvous algorithms make two mobile agents meet at a single node, starting from arbitrary initial locations and arbitrary initial states. We study deterministic algorithms for two synchronous mobile agents with different labels but without using any whiteboard in the graph. First, we show the existence of a self-stabilizing rendezvous algorithm for arbitrary graphs by providing a scheme to transform a non-stabilizing algorithm to a self-stabilizing one. However, the time complexity of the resultant algorithm is not bounded by any function of the graph size and labels. This raises the question whether there exist polynomial-time self-stabilizing rendezvous algorithms. We give partial answers to this question. We give polynomial-time self-stabilizing rendezvous algorithms for trees and rings.

The Meeting problem for $k\geq 2$ searchers in a polygon $P$ (possibly with holes) consists in making the searchers move within $P$, according to a distributed algorithm, in such a way that at least two of them eventually come to see each other, regardless of their initial positions. The polygon is initially unknown to the searchers, and its edges obstruct both movement and vision. Depending on the shape of $P$, we minimize the number of searchers $k$ for which the Meeting problem is solvable. Specifically, if $P$ has a rotational symmetry of order $\sigma$ (where $\sigma=1$ corresponds to no rotational symmetry), we prove that $k=\sigma+1$ searchers are sufficient, and the bound is tight. Furthermore, we give an improved algorithm that optimally solves the Meeting problem with $k=2$ searchers in all polygons whose barycenter is not in a hole (which includes the polygons with no holes). Our algorithms can be implemented in a variety of standard models of mobile robots operating in Look-Compute-Move cycles. For instance, if the searchers have memory but are anonymous, asynchronous, and have no agreement on a coordinate system or a notion of clockwise direction, then our algorithms work even if the initial memory contents of the searchers are arbitrary and possibly misleading. Moreover, oblivious searchers can execute our algorithms as well, encoding information by carefully positioning themselves within the polygon. This code is computable with basic arithmetic operations, and each searcher can geometrically construct its own destination point at each cycle using only a compass. We stress that such memoryless searchers may be located anywhere in the polygon when the execution begins, and hence the information they initially encode is arbitrary. Our algorithms use a self-stabilizing map construction subroutine which is of independent interest., Comment: 37 pages, 9 figures

We propose a self-stabilizing algorithm for computing a maximal matching in an anonymous network. The complexity is O(2) moves with high probability, under the adversarial distributed daemon. Among all adversarial distributed daemons and with the anonymous assumption, our algorithm provides the best known complexity. Moreover, the previous best known algorithm working under the same daemon and using identity has a O(m) complexity leading to the same order of growth than our anonymous algorithm. Finally, we do not make the common assumption that a node can determine whether one of its neighbors points to it or to another node, and still we present a solution with the same asymptotic behavior.

International audience; In this paper, we revisit two fundamental results of the self-stabilizing literature about silent BFS spanning tree constructions: the Dolev etźal. algorithm and the Huang and Chen's algorithm. More precisely, we propose in the composite atomicity model three straightforward adaptations inspired from those algorithms. We then present a deep study of these three algorithms. Our results are related to both correctness (convergence and closure, assuming a distributed unfair daemon) and complexity (analysis of the stabilization time in terms of rounds and steps). We show that the bounded-memory version of the Dolev et al's BFS is round-optimal.We show that the stabilization time of the Huang and Chen's BFS is Omega(n) rounds.We show that these two algorithms have exponential stabilization times in steps.

International audience; —The Theory of Belief Functions is a formal framework for reasoning with uncertainty that is well suited for representing unreliable information and weak states of knowledge. In a previous work, a distributed algorithm for computing data fusion on-the-fly has been introduced, avoiding gathering the data on a single node before computation. In this paper, we present an experimental study of its properties. This algorithm is self-stabilizing and runs on unreliable message passing networks. It converges in finite time whatever is the initialization of the system and for any unknown topology. First we explain the algorithm implementation on an unreliable message passing environment and we implement a simple use-case. Then, by experimenting with this distributed application on a realistic network emulator, we show its interest for enforcing local confidence using close nodes, saving bandwidth and warning dangers. Moreover, we focus on the interesting connections between the data fusion operator and the self-stabilizing properties and we highlight the importance of the discounting.