We present a self-stabilizing algorithm for the unison problem which is efficient in time, workload, and space in a weak model. Precisely, our algorithm is defined in the atomic-state model and works in anonymous asynchronous connected networks in which even local ports are unlabeled. It makes no assumption on the daemon and thus stabilizes under the weakest one: the distributed unfair daemon. In an n-node network of diameter D and assuming the knowledge B ≥ 2D+2, our algorithm only requires Θ(log(B)) bits per node and is fully polynomial as it stabilizes in at most 2D+2 rounds and O(min(n²B, n³)) moves. In particular, it is the first self-stabilizing unison for arbitrary asynchronous anonymous networks achieving an asymptotically optimal stabilization time in rounds using a bounded memory at each node. Furthermore, we show that our solution can be used to efficiently simulate synchronous self-stabilizing algorithms in asynchronous environments. For example, this simulation allows us to design a new state-of-the-art algorithm solving both the leader election and the BFS (Breadth-First Search) spanning tree construction in any identified connected network which, to the best of our knowledge, beats all existing solutions in the literature.

Distributed systems are ubiquitous, and their distributed nature make them particularly vulnerable to faults. Being able to automatically recover from these faults is of utmost importance, and self-stabilization is a general and lightweight approach to tackle this problem. However, fully asynchronous self-stabilizing algorithms (FASS) are notoriously difficult to design and prove. It thus makes sense to create and prove a transformer that turns synchronous algorithms into FASSes.

Despite the widespread usage of FIFO queues in distributed applications, designing efficient wait-free implementations of queues remains a challenge. The majority of wait-free queue implementations restrict either the number of dequeuers or the number of enqueuers that can operate on the queue, even when they use strong synchronization primitives, like the Compare&Swap. If we do not limit the number of processes that can perform enqueue and dequeue operations, the best-known upper bound on the worst case step complexity for a wait-free queue is given by [Khanchandani and Wattenhofer, 2018]. In particular, they present an implementation of a multiple dequeuer multiple enqueuer wait-free queue whose worst case step complexity is in O(√n), where n is the number of processes. In this work, we investigate whether it is possible to improve this bound. In particular, we present a wait-free FIFO queue implementation that supports n enqueuers and k dequeuers where the worst case step complexity of an Enqueue operation is in O(log n) and of a Dequeue operation is in O(k log n). Then, we show that if the semantics of the queue can be relaxed, by allowing concurrent Dequeue operations to retrieve the same element, then we can achieve O(log n) worst-case step complexity for both the Enqueue and Dequeue operations.

We address the problem of Termination Detection (TD) in asynchronous networks. It is known that TD cannot be achieved in the context of self-stabilization, except in the specific case where the TD algorithm is snap-stabilizing, i.e., it always behaves according to its specification regardless of the initial configuration. In this paper, we propose a generic, deterministic, snap-stabilizing, silent algorithm that detects whether an observed terminating silent self-stabilizing algorithm, A, has converged to a configuration that satisfies an intended predicate. Our algorithm assumes that nodes know (an upper bound on) the network diameter D. However, it requires no underlying structure, nor specific topology (arbitrary network), and works in anonymous networks, i.e., our algorithm uses no kind of assumption allowing distinguishing one or more nodes. Furthermore, it works under the weakest scheduling assumptions a.k.a, the unfair daemon. Built over any asynchronous self-stabilizing underlying unison U, our solution adds only O(log D) bits per node. Since there exists no unison algorithm with better space complexity, the extra space of our solution is negligible w.r.t. the space complexity of the underlying unison algorithm. Our algorithm provides a positive answer in O(max (k, k’, D)) time units, where k and k’ are the stabilization time complexities of A and U, respectively.

We consider self-stabilization and its weakened form called pseudo-stabilization. We study conditions under which (pseudo- and self-) stabilizing leader election is solvable in networks subject to frequent topological changes. To model such an high dynamics, we use the dynamic graph (DG) paradigm and study a taxonomy of nine important DG classes. Our results show that self-stabilizing leader election can only be achieved in the classes where all processes are sources. Furthermore, even pseudo-stabilizing leader election cannot be solved in all remaining classes, except in the class where at least one process is a timely source. We illustrate that result by proposing a pseudo-stabilizing leader election algorithm for the latter class. We also show that in this last case, the convergence time of pseudo-stabilizing leader election algorithms cannot be bounded. Nevertheless, we show that our solution is speculative since its convergence time can be bounded when the dynamics is not too erratic, precisely when all processes are timely sources.

FIFO broadcast provides application ordering semantics of messages broadcast by the same sender and have been mostly implemented on top of unreliable static networks. In this article, we propose a round-based FIFO broadcast algorithm with both termination detection and bounded message size for dynamic networks with recurrent connectivity (Class$\mathcal{TC}^{\mathcal{R}}$of Time-varying Graph formalism [1]). Initially, processes only know the number of processes$N$in the system and their identifier. Due to the dynamics of the network links, messages can be lost. Since no unbounded timestamp is used to identify a message, its size is bounded to$2N+O(log(N))+msgSize$bits where msgSize is the bound size in bits of the broadcast data. We also present a FIFO atomic broadcast algorithm for dynamic networks with recurrent connectivity that uses the proposed FIFO broadcast and deliver primitives. This algorithm provides causal total order broadcast primitives.

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 TCB (Δ) of TVGs with temporal diameter bounded by Δ, the class TCB (Δ) of TVGs with temporal diameter quasi-bounded by Δ, and the class TCR of TVGs with recurrent connectivity only, where TCB (Δ) ⊆ TCB (Δ) ⊆ TCR. 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 TCB (Δ) or TCR 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 TCB (Δ), TCB(Δ), and TCR, respectively.

Abstract We present a silent self-stabilizing distributed algorithm computing a maximal $\ p$-star decomposition of the underlying communication network. Under the unfair distributed scheduler, the most general scheduler model, the algorithm converges in at most $12\Delta m + \mathcal{O}(m+n)$ moves, where $m$ is the number of edges, $n$ is the number of nodes and $\Delta $ is the maximum node degree. Regarding the time complexity, we obtain the following results: our algorithm outperforms the previously known best algorithm by a factor of $\Delta $ with respect to the move complexity. While the round complexity for the previous algorithm was unknown, we show a $5\big \lfloor \frac{n}{p+1} \big \rfloor +5$ bound for our algorithm.

We propose a self-stabilizing reset algorithm working in anonymous networks. This algorithm resets the network in a distributed non-centralized manner, 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 fact, 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. 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 time complexity of the proposed unison algorithm is better than that of previous ones.

Highly dynamic networks are characterized by frequent changes in the availability of communication links. These networks are often partitioned into several components, which split and merge unpredictably. We present a distributed algorithm that maintains a forest of (as few as possible) spanning trees in such a network, with no restriction on the rate of change. Our algorithm is inspired by high-level graph transformations, which we adapt here in a (synchronous) message passing model for dynamic networks. The resulting algorithm has the following properties. First, every decision is purely local—in each round, a node only considers its role and that of its neighbors in the tree, with no further information propagation (in particular, no wave mechanisms). Second, whatever the rate and scale of the changes, the algorithm guarantees that, by the end of every round, the network is covered by a forest of spanning trees in which (1) no cycle occur, (2) every node belongs to exactly one tree and (3) every tree contains exactly one root. We primarily focus on the correctness of this algorithm, which is established rigorously. While performance is not the main focus, we suggest new complexity metrics for such problems, and report on preliminary experimentation results validating our algorithm in a practical scenario.

We deal with the problem of maintaining a shortest-path tree rooted at some process r in a network that may be disconnected after topological changes. The goal is then to maintain a shortest-path tree rooted at r in its connected component, V\_r, and make all processes of other components detecting that r is not part of their connected component. We propose, in the composite atomicity model, a silent self-stabilizing algorithm for this problem working in semi-anonymous networks, where edges have strictly positive weights. This algorithm does not require any a priori knowledge about global parameters of the network. We prove its correctness assuming the distributed unfair daemon, the most general daemon. Its stabilization time in rounds is at most 3nmax+D, where nmax is the maximum number of non-root processes in a connected component and D is the hop-diameter of V\_r. Furthermore, if we additionally assume that edge weights are positive integers, then it stabilizes in a polynomial number of steps: namely, we exhibit a bound in O(maxi nmax^3 n), where maxi is the maximum weight of an edge and n is the number of processes.

Consensus is one of the central distributed abstractions. By enabling a collection of processes to agree on one of the values they propose, consensus can be used to implement any generic replicated service in a consistent and fault-tolerant way. In this paper, we study uncontended complexity of anonymous consensus algorithms, counting the number of memory locations used and the number of memory updates performed in operations that encounter no contention. We assume that contention-free operations on a consensus object perform "fast" reads and writes, and resort to more expensive synchronization primitives, such as CAS, only when contention is detected. We call such concurrent implementations interval-solo-fast and derive one of the first nontrivial tight bounds on space complexity of anonymous interval-solo-fast consensus.

In a distributed system, the environment is described by the scheduler (also called adversary or demon). Through an example related to stabilization, we show that a formal proof that does not use a formal definition of a scheduler is pointless. As a matter of fact, we show that the same algorithm, according to the scheduler, can be either correct or incorrect and in the cases where it is correct, can have different complexities. The paper is an attempt to better understand the meaning of proving a probabilistic algorithm in a indeterministic environment.

Clustering means partitioning nodes into groups called clusters, providing the network with a hierarchical organization. A self-stabilizing protocol, regardless of the initial system state, automatically converges to a set of states that satisfy the problem specification without external intervention. Due to this property, self-stabilizing protocols are adapted to highly dynamic networks as ad hoc or sensors networks. In this paper, we propose a self-stabilizing clustering protocol. Our protocol guarantees a threshold (size bound) on the number of nodes that a clusterhead handle. Therefore, none of the clusterheads are overloaded at anytime. The criterion of the clusterheads election is based on their weight value, a general parameter that can be computed according to several node parameters as transmission power, battery power, ... .

No abstract available.

A goal of peer-to-peer applications is to share files between users themselves rather than downloading files from file servers. Self-downloading protocols have the property that, eventually, every user downloads only from other users. Self-downloading is problematic if users disconnect from the system upon completing file downloading, because they only share with other users while connected. Yet, if users continue to arrive at a sufficient rate, self-downloading protocols are possible. One vulnerability of file sharing between users is the possibility that files or segments could be counterfeit or corrupt. Protocols that are d -safe tolerate some number of instances of faulty segments in a file being downloaded, because each segment is downloaded d times before being shared. This article shows that d -safe self-downloading is possible for a sufficiently large arrival rate of users to the system. Upper and lower connectivity and sharing bounds are given for d = 2, and simulation results show effects of relaxing assumptions about arrival rates and bandwidth.

A distributed system is commonly modelled by a graph where nodes represent processors and there is an edge between two processors if and only if they can communicate directly. In shared-registers versions of this general description, neighbouring processors communicate by reading or writing shared registers, where each read or write is one atomic step. Variants of shared register models occur in the literature. This paper defined two models of shared registers determined by selecting the register locations. In the atomic-state model each processor has a register; in the atomic-link model, each communication link has a register. We determine under what conditions and with what robustness and/or failure-tolerance guarantees it is possible to transform a solution under the atomic-state model into a solution under the atomic-link model. The fault-tolerant models considered in this paper are wait-freedom and self-stabilization. These questions are addressed by first establishing a framework for defining correct transformations, which may be useful for similar studies of the relationship between various models of distributed computation

Summary form only given. Robustness is one of the most important requirements of modern distributed systems. Various types of faults are likely to occur at various parts of the system. The concept of self-stabilization is the most general technique to design a system to tolerate arbitrary transient faults. A self-stabilizing system, regardless of the initial states of the processors and initial messages in the links, is guaranteed to converge to the intended behavior in finite time. We present a self-stabilizing token circulation protocol on unidirectional anonymous rings. This protocol does not require processor identifiers, no distinguished processor (i.e. all processors perform the same code). The algorithm can deal with any kind of schedules even unfair ones. Our protocol is the first one having the two major advantages : the duration of a token circulation is bounded and the protocol is optimal in memory space. The memory space required by our protocol on each processor is 0(lg(M/sub N/)), M/sub N/ being the smallest non divisor of ring size. Our protocol is a randomized self-stabilizing, meaning that starting from an arbitrary configuration (in response to an arbitrary perturbation modifying the memory state), it reaches (with probability 1) a legitimate configuration (i.e. a configuration with only one token in the network). Once the system is stabilized, the circulation of the sole token is 1-fair (i.e. in every round, every processor obtains the token one time).

We present a self-stabilizing token circulation protocol on unidirectional anonymous rings. This protocol requires no processor identifiers or distinguished processor (i.e. all processors perform the same algorithm). The protocol is randomized and self-stabilizing, meaning that starting from an arbitrary configuration (in response to an arbitrary perturbation modifying the memory state), it reaches (with probability 1) a legitimate configuration (i.e. a configuration with only one token in the network). All previous randomized self-stabilizing token circulation protocols designed to work under unfair distributed schedulers have the same drawback: once stabilized, service time is slow (in the best case, it is bounded by 2N where N is the ring size). Once stabilized, our protocol provides an optimal service: after N computation steps, each processor has obtained the token once. The protocol can be used to implement fair distributed mutual exclusion in any ring topology network.

Proposes a self-stabilizing synchronization technique, called the Neighborhood Synchronizer (/spl Nscr//spl Sscr/), that synchronizes nodes with their neighbors in a tree network. The /spl Nscr//spl Sscr/ scheme has an extremely small memory requirement-only one bit per processor. Algorithm /spl Nscr//spl Sscr/ is inherently self-stabilizing. We apply our synchronizer to design a broadcasting algorithm /spl Bscr//spl Ascr/ in a tree network. Algorithm /spl Bscr//spl Ascr/ is also inherently self-stabilizing and needs only 2h+2m-1 rounds to broadcast m messages, where h is the height of the tree.

We study the memory requirements of self-stabilizing leader election (SSLE) protocols. We are mainly interested in two types of systems: anonymous systems and id-based systems. We consider two classes of protocols: deterministic ones and randomized ones. We prove that a non-constant lower bound on the memory space is required by a SSLE protocol on unidirectional, anonymous rings (even if the protocol is randomized). We show that, if there is a deterministic protocol solving a problem on id-based systems where the processor memory space is constant and the id-values are not bounded then there is a deterministic protocol on anonymous systems using constant memory space that solves the same problem. Thus impossibility results on anonymous rings (i.e. one may design a deterministic SSLE protocol, only on prime size rings, under a centralized daemon) can be extended to those kinds of id-based rings. Nevertheless, it is possible to design a silent and deterministic SSLE protocol requiring constant memory space on unidirectional, id-based rings where the id-values are bounded. We present such a protocol. We also present a randomized SSLE protocol and a token circulation protocol under an unfair, distributed daemon on anonymous and unidirectional rings of any size. We give a lower bound on memory space requirement proving that these protocols are space optimal. The memory space required is constant on average.

No abstract available.