Search

We present a self-stabilizing leader election algorithm for general networks, with space-complexity O (log Δ + log log n) bits per node in n -node networks with maximum degree Δ. This space complexity is sub-logarithmic in n as long as Δ = n o (1) . The best space-complexity known so far for general networks was O (log n) bits per node, and algorithms with sub-logarithmic space-complexities were known for the ring only. To our knowledge, our algorithm is the first algorithm for self-stabilizing leader election to break the Ω (log n) bound for silent algorithms in general networks. Breaking this bound was obtained via the design of a (non-silent) self-stabilizing algorithm using sophisticated tools such as solving the distance-2 coloring problem in a silent self-stabilizing manner, with space-complexity O (log Δ + log log n) bits per node. Solving this latter coloring problem allows us to implement a sub-logarithmic encoding of spanning trees — storing the IDs of the neighbors requires Ω (log n) bits per node, while we encode spanning trees using O (log Δ + log log n) bits per node. Moreover, we show how to construct such compactly encoded spanning trees without relying on variables encoding distances or number of nodes, as these two types of variables would also require Ω (log n) bits per node. • Self-stabilizastion • Leader election • Spanning tree construction • Compact memory [ABSTRACT FROM AUTHOR]

The contribution of this paper is threefold. First, we give tight bounds for the complexity of the problem of data aggregation in static networks. In more details, we show that the problem remains NP-complete when the graph is of degree at most three. Second, we investigate the complexity of the same problem in a dynamic network, that is, a network whose topology can evolve through time. In the case of dynamic networks, we show that the problem is NP-complete even in the case where the graph is of degree at most two. Third, we give the first lower and upper bounds for the minimum data aggregation time in a dynamic graph. We also observe that even in a well-connected evolving graphs, the optimal solution cannot be found by a distributed algorithm or by a centralized algorithm that does not know the future. [ABSTRACT FROM AUTHOR]

We consider the problem of reliably broadcasting a message in a multihop network. We assume that some nodes may be Byzantine, and behave arbitrarily. We focus on cryptography-free solutions. We propose a protocol for sparse networks (such as grids or tori) where the nodes are not aware of their position. Our protocol uses a fixed number of disjoint paths to accept and forward the message to be broadcast. It can be tuned to significantly improve the number of Byzantine nodes tolerated. We present both theoretical analysis and experimental evaluation. [ABSTRACT FROM AUTHOR]

We investigate exploration algorithms for autonomous mobile robots evolving in uniform ring-shaped networks. Unlike previous works, we consider myopia (each robot can only observe its neighboring nodes) and luminosity (each robot can use only two colors for its light) properties for the robots. As a main contribution, we prove that (i) in the FSYNC model, two (resp. three) myopic robots are necessary and sufficient to achieve perpetual (resp. terminating) exploration, and (ii) in the SSYNC and ASYNC models, three (resp. four) myopic robots are necessary and sufficient to achieve perpetual (resp. terminating) exploration. We also show that, in all execution models, our perpetual exploration algorithm is universal. That is, the algorithm solves perpetual exploration from any solvable initial configuration with two (resp. three) myopic robots and two colors in the FSYNC model (resp. the SSYNC and ASYNC models). On the other hand, we provide impossibility results for universal terminating exploration. [ABSTRACT FROM AUTHOR]

Fault tolerance is a crucial property for recent distributed systems. We propose an algorithm that solves the census problem (list all processor identifiers and their relative distance) on an arbitrary strongly connected network.This algorithm tolerates transient faults that corrupt the processors and communication links memory (it is self-stabilizing) as well as intermittent faults (fair loss, reorder, finite duplication of messages) on communication media. A formal proof establishes its correctness for the considered problem. Our algorithm leads to the construction of algorithms for any silent problems that are self-stabilizing while supporting the same communication hazards. [Copyright &y& Elsevier]

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. [ABSTRACT FROM AUTHOR]

A fault-tolerant and practically stabilizing simulation of an atomic register is presented. The simulation works in asynchronous message-passing systems, and allows a minority of processes to crash. The simulation stabilizes in a practically stabilizing manner, by reaching a long execution in which it runs correctly. A key element in the simulation is a new combinatorial construction of a bounded labeling scheme accommodating arbitrary labels, including those not generated by the scheme itself. [ABSTRACT FROM AUTHOR]

Abstract: We explore asynchronous unison in the presence of systemic transient and permanent Byzantine faults in shared memory. We observe that the problem is not solvable under a less than strongly fair scheduler or for system topologies with maximum node degree greater than two. We present then a self-stabilizing Byzantine-tolerant solution to asynchronous unison for chain and ring topologies under the central strongly fair daemon. Our algorithm has minimum possible containment radius and optimal stabilization time. [Copyright &y& Elsevier]

Abstract: In this paper, we tackle the problem of snap-stabilization in message-passing systems. Snap-stabilization allows designing protocols that withstand transient faults: indeed, any computation that is started after faults cease immediately satisfies the expected specification. Our contribution is twofold: we demonstrate that in message-passing systems (i) snap-stabilization is impossible for nontrivial problems if channels are of finite yet unbounded capacity, and (ii) snap-stabilization becomes possible in the same setting with bounded capacity channels. The latter contribution is constructive, as we propose two snap-stabilizing protocols for propagation of information with feedback and mutual exclusion. Our work opens exciting new research perspectives, as it enables the snap-stabilizing paradigm to be implemented in actual networks. [Copyright &y& Elsevier]