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]

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]

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]

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]