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]

Routing protocols are at the core of distributed systems performances, especially in the presence of faults. A classical approach to this problem is to build a spanning tree of the distributed system. Numerous spanning tree construction algorithms depending on the optimized metric exist (total weight, height, distance with respect to a particular process, …) both in fault-free and faulty environments. In this paper, we aim at optimizing the diameter of the spanning tree by constructing a minimum diameter spanning tree. We target environments subject to transient faults ( i.e. faults of finite duration). Hence, we present a self-stabilizing algorithm for the minimum diameter spanning tree construction problem in the state model. Our protocol has the following attractive features. It is the first algorithm for this problem that operates under the unfair and distributed adversary (or daemon ). In other words, no restriction is made on the asynchronous behavior of the system. Second, our algorithm needs only O ( log n ) bits of memory per process (where n is the number of processes), that improves the previous result by a factor n . These features are not achieved to the detriment of the convergence time, which stays polynomial. [ABSTRACT FROM AUTHOR]

The minimum spanning tree (MST) construction is a classical problem in Distributed Computing for creating a globally minimized structure distributedly. Self-stabilization is versatile technique for forward recovery that permits to handle any kind of transient faults in a unified manner. The loop-free property provides interesting safety assurance in dynamic networks where edge-cost changes during operation of the protocol.We present a new self-stabilizing MST protocol that improves on previous known approaches in several ways. First, it makes fewer system hypotheses as the size of the network (or an upper bound on the size) need not be known to the participants. Secondly, it is loop-free in the sense that it guarantees that a spanning tree structure is always preserved while edge costs change dynamically and the protocol adjusts to a new MST. Finally, time complexity matches the best known results, while space complexity results show that this protocol is the most efficient to date. [ABSTRACT FROM AUTHOR]

Abstract: This paper proposes a fully dynamic self-stabilizing algorithm for the dynamic Steiner tree problem. The Steiner tree problem aims at constructing a Minimum Spanning Tree (MST) over a subset of nodes called Steiner members, or Steiner group usually denoted S. Steiner trees are good candidates to efficiently implement communication primitives such as publish/subscribe or multicast, essential building blocks in the design of middleware architectures for the new emergent networks (e.g., P2P, sensor or adhoc networks). Our algorithm returns a -approximation of the optimal Steiner tree. It improves over existing solutions in several ways. First, it is fully dynamic, in other words it withstands the dynamism when both the group members and ordinary nodes can join or leave the network. Next, our algorithm is self-stabilizing, that is, it copes with nodes memory corruption. Last but not least, our algorithm is super-stabilizing. That is, while converging to a correct configuration (i.e., a Steiner tree) after a modification of the network, it keeps offering the Steiner tree service during the stabilization time to all members that have not been affected by this modification. [Copyright &y& Elsevier]

Abstract: We propose a self-stabilizing algorithm for constructing a Minimum Degree Spanning Tree (MDST) in undirected networks. Starting from an arbitrary state, our algorithm is guaranteed to converge to a legitimate state describing a spanning tree whose maximum node degree is at most , where is the minimum possible maximum degree of a spanning tree of the network. To the best of our knowledge, our algorithm is the first self-stabilizing solution for the construction of a minimum degree spanning tree in undirected graphs. The algorithm uses only local communications (nodes interact only with the neighbors at one hop distance). Moreover, the algorithm is designed to work in any asynchronous message passing network with reliable FIFO channels. Additionally, we use a fine grained atomicity model (i.e., the send/receive atomicity). The time complexity of our solution is where is the number of edges and is the number of nodes. The memory complexity is in the send–receive atomicity model ( is the maximal degree of the network). [ABSTRACT FROM AUTHOR]

In this paper we present the first distributed algorithm on general graphs for the Minimum Degree Spanning Tree problem. The problem is NP-hard in sequential. Our algorithm give a Spanning Tree of a degree at most 1 from the optimal. The resulting distributed algorithm is asynchronous, it works for named asynchronous arbitrary networks and achieves O(|V|) time complexity and O(|V||E|) message complexity. [ABSTRACT FROM AUTHOR]