Search

Computing over large platforms calls for the ability to maintain distributed structures at large scale. Among the many different structures proposed in this context, the prefix tree structure has been identified as an adequate one for indexing and retrieving information. One weakness of using such a distributed structure stands in its poor native fault tolerance, leading to the use of preventive costly mechanisms such as replication. Self-stabilization is a suitable approach to design reliable solutions for dynamic systems, and was recently enhanced with new models to be able to deal with large scale dynamic platforms. A self-stabilizing system is guaranteed to reach a correct configuration, whatever its initial state is. Following this path, it is becoming possible to make distributed structures self-stabilizing at large scale. In this paper, we focus on making tries self-stabilizing over such platforms, and propose a self-stabilizing maintenance algorithm for a prefix tree using a message passing model. The proof of self-stabilization is provided, and simulation results are given, to better capture its performances. Still based on simulations, we provide evidences that the protocol, beyond its capacity to repair the structure, can significantly improve the system's availability, even when the system is not yet stabilized. [ABSTRACT FROM AUTHOR]

In computer networks area, the minimal dominating sets (MDS) and maximal independent sets (MIS) structures are very useful for creating virtual network overlays. Often, these set structures are used for designing efficient protocols in wireless sensor and ad-hoc networks. In this paper, we give a particular interest to one kind of these sets, called Independent Strong Dominating Set (ISD-set). In addition to its domination and independence properties, the ISD-set considers also node's degrees that make it very useful in practical applications where nodes with larger degrees play important role in the networks. For example, some network clustering protocols chose nodes with large degrees to be cluster-heads, which is exactly the result obtained by an ISD-set algorithm. Thence, we propose the first distributed self-stabilizing algorithm for computing an ISD-set of an arbitrary graph (called ISDS). Then, we prove that ISDS algorithm operates under the unfair distributed scheduler and converges after at most rounds requiring only space memory per node where Δ is the maximum node degree. The complexity of ISDS algorithm in rounds has the same order as the best known self-stabilizing algorithms for finding MDS and MIS. Moreover, performed simulations and comparisons with well-known self-stabilizing algorithms for MDS and MIS problems showed the efficiency of ISDS, especially for reducing the cardinality of dominating sets founded by the algorithms. [ABSTRACT FROM AUTHOR]

Self-stabilization is a strong property, which guarantees that a distributed system always resumes a correct behavior starting from an arbitrary initial state. Since it is a strong property, some problems cannot have self-stabilizing solutions. Weaker guarantees hence have been later introduced to cope with impossibility results, e.g., probabilistic self-stabilization only guarantees probabilistic convergence to a correct behavior, and weak stabilization only guarantees the possibility of convergence. In this paper, we investigate the relative power of self, probabilistic, and weak stabilization, with respect to the set of problems that can be solved. Weak stabilization is by definition stronger than self-stabilization and probabilistic self-stabilization in that precise sense. We first show that weak stabilization allows to solve problems having no self-stabilizing solution. We then show that any finite state deterministic weak stabilizing algorithm to solve a problem under the strongly fair scheduler is always a probabilistic self-stabilizing algorithm to solve the same problem under the randomized scheduler. Unfortunately, this good property does not hold in general for infinite state algorithms. We however show that for some classes of infinite state algorithms, this property holds. These results hint at more practical use of weak stabilizing algorithms, as they are easier to design and prove their correctness than their self-stabilizing and probabilistic self-stabilizing counterparts. [ABSTRACT FROM AUTHOR]

In this paper, we propose two new self-stabilizing algorithms, MWCDS-C and MWCDS-D, for minimal weakly connected dominating sets in an arbitrary connected graph. Algorithm MWCDS-C stabilizes in O(n4) steps using an unfair central daemon and space requirement at each node is O(log n) bits at each node for an arbitrary connected graph with n nodes; it uses a designated node while other nodes are identical and anonymous. Algorithm MWCDS-D stabilizes using an unfair distributed daemon with identical time and space complexities, but it assumes unique node IDs. In the literature, the best reported stabilization time for a minimal weakly connected dominating set algorithm is O(nmA) under a distributed daemon [1], where m is the number of edges and A is the number of moves to construct a breadth-first tree. [ABSTRACT FROM AUTHOR]

Self-stabilizing algorithms represent an extension of distributed algorithms in which nodes of the network have neither coordination, synchronization, nor initialization. We consider the model where there is one designated master node and all other nodes are anonymous and have constant space. Recently, Lee et al. obtained such an algorithm for determining the size of a unidirectional ring. We provide a new algorithm that converges much quicker. This algorithm exploits a token-circulation idea due to Afek and Brown. Disregarding the time for stabilization, our algorithm computes the size of the ring at the master node in O(n log n) time compared to O(n3) steps used in the algorithm by Lee et al. We have also shown that the master node, after determining the size of the ring, can compute the average of observations made at each node in O(n) rounds or O(n2) steps. It seems likely that one should be able to obtain master-slave algorithms for other problems in networks. [ABSTRACT FROM AUTHOR]

The performance of processors in a distributed system can be measured by parameters such as bandwidth, storage capacity, work capability, reliability, power limitations, years of usage, among others. Each processor defines its preference based on these parameters. The preference represents an indicator of the quality of service that a processor can provide. An algorithm that follows a preference-based approach uses the preference of the processors to make decisions. In this paper we introduce a randomized self-stabilizing leader election algorithm for preference-based anonymous trees. Our algorithm assures that the processor with the highest preference in the system is always selected as the leader; moreover, it is able to solve symmetric configurations where each preference is the same. We prove that our algorithm has an optimal average time complexity and we also performed simulations to illustrate the average performance of the algorithm. [ABSTRACT FROM AUTHOR]

Topology embedding enables one to execute a protocol designed for a specific (virtual) topology on another (real) topology by embedding the virtual topology on the real topology. In this paper, we propose a self-stabilizing emulation technique that provides reliable communication on a virtual topology in the presence of transient faults in real topology. The proposed protocol improves the execution slowdown of previous two protocols [19, 20] and provides adaptive message delivery delay on the emulated channels, which is a new type of adaptability against transient faults. [ABSTRACT FROM AUTHOR]

A self-stabilizing algorithm is a distributed algorithm that can start from any initial (legitimate or illegitimate) state and eventually converge to a legitimate state in finite time without being assisted by any external agent. In this paper, we propose a self-stabilizing algorithm for finding the 3-edge-connected components of an asynchronous distributed computer network. The algorithm stabilizes in O(dnΔ) rounds and every processor requires O(nlogΔ) bits, where Δ(≤ n) is an upper bound on the degree of a node, d(≤ n) is the diameter of the network, and n is the total number of nodes in the network. These time and space complexity are at least a factor of n better than those of the previously best-known self-stabilizing algorithm for 3-edge-connectivity. The result of the computation is kept in a distributed fashion by assigning, upon stabilization of the algorithm, a component identifier to each processor which uniquely identifies the 3-edge-connected component to which the processor belongs. Furthermore, the algorithm is designed in such a way that its time complexity is dominated by that of the self-stabilizing depth-first search spanning tree construction in the sense that any improvement made in the latter automatically implies improvement in the time complexity of the algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we address the problem of k-out-of-ℓ exclusion, a generalization of the mutual exclusion problem, in which there are ℓ units of a shared resource, and any process can request up to k units (1 ≤ k ≤ ℓ). A protocol is self-stabilizing if, starting from an arbitrary configuration, be it initial state or after a corrupted state, the protocol can start behaving normally within a finite time. We propose the first deterministic self-stabilizing distributed k-out-of-ℓ exclusion protocol in message-passing systems for asynchronous oriented tree networks which assumes bounded local memory for each process. [ABSTRACT FROM AUTHOR]

This paper focuses on the self-stabilizing leader election algorithm of Xu and Srimani [10] that finds a leader in a tree graph. The worst case execution time for this algorithm is O(N4), where N is the number of nodes in the tree. We show that the average execution time for this algorithm, assuming two different scenarios, is much lower than O(N4). In the first scenario, the algorithm assumes an equiprobable daemon and it only privileges a single node at a time. The average execution time for this case is O(N2). For the second case, the algorithm can privilege multiple nodes at a time. We eliminate the daemon from this algorithm by making random choices to avoid interference between neighboring nodes. The execution time for this case is O(N). We also show that for specific tree graphs, these results reduce even more. [ABSTRACT FROM AUTHOR]