Narrow Results

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(N⁴), 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(N⁴). 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(N²). 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.

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.

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.

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.

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(n³) 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(n²) steps. It seems likely that one should be able to obtain master–slave algorithms for other problems in networks.

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.

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(n⁴) 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.

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.

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 $(n+1)$ rounds requiring only $O\left(\mathrm{\text{log}}\mathrm{\Delta }\right)$ 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.

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.

In this paper, a self-stabilizing algorithm is presented for finding the articulation points of a connected undirected graph on a distributed or network model of computation after O(n²|E|) moves. The algorithm is resilient to transient faults and does not require initialization. A correctness proof of the algorithm is also presented. The paper concludes with remarks on issues such as the time complexity of the algorithm and open problems.

In this paper, we consider arbitrary tree networks where every processor, except one, called the root, executes the same program. We show that, to design a depth-first token circulation protocol in such networks, it is necessary to have at least configurations, where n is the number of processors in the network and Δ_i is the degree of processor p_i.

We then propose a depth-first token circulation algorithm which matches the above minimal number of configurations. We show that the proposed algorithm is self-stabilizing, i.e., the system eventually recovers itself to a legitimate state after any perturbation modifying the state of the processors. Hence, the proposed algorithm is optimal in terms of the number of configurations and no extra cost is involved in making it stabilizing.

We propose a snap-stabilizing synchronization technique, called the Neighborhood Synchronizer that synchronizes nodes with their neighbors in a tree network. The scheme has optimal memory requirement — only one bit per processor. is snap-stabilizing [11], meaning that it always behaves according to its specification. The proposed synchronizer being snap-stabilizing is optimal in terms of stabilization time. We show an application of the synchronizer by designing an efficient broadcast algorithm in tree networks. is also snap-stabilizing and needs only 2h + 2m - 1 rounds to broadcast m messages, where h is the height of the tree.

For bidirectional rings, there have been proposed self-stabilizing mutual exclusion protocols, which are either time-adaptive (i.e., efficient in recovery) or 1-latent (i.e., efficient in legal execution) but not both. This paper proposes a randomized self-stabilizing mutual exclusion protocol that inherits both of the advantages from them: It is 1-latent in the sense that the privilege is circulated in a linear round (i.e., very intuitively, the privilege is transferred from a process to another by a "step"), provided that the system always stays in legitimate configurations, and is weakly time-adaptive in the sense that the system stabilizes from any configuration c in O(f) steps with a high probability, where f is the number of corrupted processes in c. It also guarantees with a high probability that there is at most one privilege even while converging to a legitimate configuration.

An alternator is an arbitrary set of interacting processes that satisfies three conditions. First, if a process executes its critical section, then no neighbor of that process can execute its critical section at the same state. Second, along any infinite sequence of system states, each process will execute its critical section, an infinite number of times. Third, along any maximally concurrent computation, the alternator will stabilize to a sequence of states in which the processes will execute their critical sections in alternation. A principal reason for interest in alternators is their ability to transform systems correct under serial execution semantics to systems that are correct under concurrent execution semantics. An earlier alternator for arbitrary topology required 2q states where q is the dependency graph circumference and after stabilization would wait 2q steps between critical section executions. In a synchronous environment, this alternator requires only 2d+1 states where d is the degree of the graph of process dependencies for the system and after stabilization will require a wait of 2d+1 steps between critical section executions. In an asynchronous environment, the synchronization properties of this alternator must be supplemented with an asynchronous unison algorithm. The asynchronous unison algorithm requires expansion of the required number of states to dt, where t is the longest chordless cycle in the dependency graph; however, the required wait between critical section executions remains O(d).

Several factors still hinder the deployment of computational grids over large scale platforms. Among them, the resource discovery is one crucial issue. New approaches, based on peer-to-peer technologies, tackle this issue. Because they efficiently allow range queries, Tries (a.k.a., Prefix Trees) appear to be among promising ways in the design of distributed data structures indexing resources. Despite their lack of robustness in dynamic settings, trie-structured approaches outperform other peer-to-peer fashioned technologies by efficiently supporting range queries. Within recent trie-based approaches, the fault-tolerance is handled by preventive mechanisms, intensively using replication. However, replication can be very costly in terms of computing and storage resources and does not ensure the recovery of the system after arbitrary failures.

Self-stabilization is an efficient approach in the design of reliable solutions for dynamic systems. It ensures a system to converge to its intended behavior, regardless of its initial state, in a finite time. A snap-stabilizing algorithm guarantees that it always behaves according to its specification, once the protocol is launched. In this paper, we provide the first snap-stabilizing protocol for trie construction. We design particular tries called Proper Greatest Common Prefix (PGCP) Tree. The proposed algorithm arranges the n label values stored in the tree, in average, in O(h + h′) rounds, where h and h′ are the initial and final heights of the tree, respectively. In the worst case, the algorithm requires an O(n) extra space on each node, O(n) rounds and O(n²) actions. However, simulations allow to state that this worst case is far from being reached and to confirm the average complexities, showing the practical efficiency of this protocol.

This paper presents a deterministic self-stabilizing algorithm that approximates a minimum vertex cover in anonymous networks with ratio 2 using the distributed scheduler and the link-register model with composite atomicity. No algorithm with a better approximation ratio can exist. The algorithm stabilizes in O(min{n, Δ², Δ log₃ n}) rounds and requires O(Δ) memory per node.

Randomization is a technique to improve efficiency and computability of distributed computing. In this paper, we investigate fault tolerance of distributed computing against faults of random number generators. We introduce an RNG (Random Number Generator)-fault as a new class of faults; a random number generator on an RNG-faulty process outputs the same number deterministically. This paper is the first work that considers faults of randomness in distributed computing.

We investigate the role of randomization by observing the impact of RNG-faults on performance of a self-stabilizing token circulation algorithm on unidirectional n-node ring networks. In the analysis, we assume there exist n_f (0 ≤ n_f ≤ n−1) RNG-faulty nodes and each RNG-faulty node always transfers a token to the next node. Our results are threefold: (1) We derive the upper bound on the expected convergence time in the case of n_f = n − 1. (2) Our simulation result shows that the expected convergence time is maximum when n_f = n − 1. (3) We derive the expected token circulation time for each n_f (0 ≤ n_f ≤ n − 1).

In a graph or a network $G=(V,E)$, a set $𝒮\subseteq V$ is a dominating set if each node in $V-𝒮$ is adjacent to at least one node in $𝒮$. A dominating set $𝒮$ is called minimal when there does not exist a node $i\in 𝒮$ such that the set $𝒮-\left\{i\right\}$ is a dominating set. In this paper, we propose a new self-stabilizing algorithm for minimal dominating set. It has safe convergence property under synchronous daemon in the sense that starting from an arbitrary state, it quickly converges to a dominating set (a safe state) in two rounds, and then stabilizes in a minimal dominating set (the legitimate state) in $O\left(n\right)$ rounds without breaking safety during the convergence interval, where n is the number of nodes. Space requirement at each node is $O\left(logn\right)$ bits.

We propose a self-stabilizing algorithm for computing a maximal matching in an anonymous network. The complexity is O(²) moves with high probability, under the adversarial distributed daemon. Among all adversarial distributed daemons and with the anonymous assumption, our algorithm provides the best known complexity. Moreover, the previous best known algorithm working under the same daemon and using identity has a O(m) complexity leading to the same order of growth than our anonymous algorithm. Finally, we do not make the common assumption that a node can determine whether one of its neighbors points to it or to another node, and still we present a solution with the same asymptotic behavior.