The distributed daemon model introduced by Burns in 1987 is a natural generalization of the central daemon model introduced by Dijkstra in 1974. In this paper, we show that a well-known shortest path algorithm is self...
详细信息
The distributed daemon model introduced by Burns in 1987 is a natural generalization of the central daemon model introduced by Dijkstra in 1974. In this paper, we show that a well-known shortest path algorithm is self-stabilizing under the distributed daemon model. Although this result has been proven only recently, the correctness proof provided here is from a different point of view and is much more concise. We also show that Bruell et al.'s center-finding algorithm is actually self-stabilizing under the distributed daemon model. Finally, we compute the worst-case stabilization times of the two algorithms under the distributed daemon model. (c) 2008 Elsevier B.V. All rights reserved.
The matching problem asks for a large set of disjoint edges in a graph. It is a problem that has received considerable attention in both the sequential and self-stabilizing literature. Previous work has resulted in se...
详细信息
ISBN:
(纸本)9783540893349
The matching problem asks for a large set of disjoint edges in a graph. It is a problem that has received considerable attention in both the sequential and self-stabilizing literature. Previous work has resulted in self-stabilizing algorithms for computing a maximal (1/2-approximation) matching in a general graph, as well is computing a 2/3-approximation on more specific graph types. In the following we present the first self-stabilizing algorithm for finding a 2/3-approximation to the maximum matching problem in a general graph. We show that our new algorithm stabilizes in at most exponential time under a distributed adversarial daemon, and O(n(2)) rounds under a distributed fair daemon, where n is the number of nodes in the graph.
Shortest path finding has a variety of applications in the areas of transportation and communication in distributed systems. In this paper, we design and prove the correctness of a self-stabilizing algorithm that solv...
详细信息
Shortest path finding has a variety of applications in the areas of transportation and communication in distributed systems. In this paper, we design and prove the correctness of a self-stabilizing algorithm that solves the single-source shortest path problem for a distributed system. Unlike all previous works on this topic, the model of computation employed by the system in this paper assumes the separate read/write atomicity introduced by Dolev et al. instead of the commonly used composite read/write atomicity introduced by Dijkstra. (C) 2005 Elsevier Inc. All rights reserved.
Shortest path finding has a variety of applications in transportation and communication. In this paper, we study a well-known self-stabilizing algorithm for the shortest path problem for the distributed systems. The p...
详细信息
Shortest path finding has a variety of applications in transportation and communication. In this paper, we study a well-known self-stabilizing algorithm for the shortest path problem for the distributed systems. The previous works on this topic had two assumptions that can be relaxed in this paper. First, in the previous works, the systems were assumed to be integral-weighted, whereas in this paper, the systems are real-weighted. Second, and more importantly, the previous works have shown that the algorithm is self-stabilizing under the more restricted central demon model, whereas in this paper, we give a rigorous proof showing that the algorithm is actually self-stabilizing under the more general distributed demon model. The work in this paper is of significance because in the existing literature on self-stabilizing systems, most of the papers regarding the distributed demon are for the ring networks only;there are very few papers that discuss the self-stabilizing algorithms for the general distributed systems assuming the distributed demon model. (c) 2005 Elsevier Ltd. All rights reserved.
The problem of locating centers of graphs has a variety of applications in the areas of transportation and communication in distributed systems. In this paper, we design and prove the correctness of a self-stabilizing...
详细信息
The problem of locating centers of graphs has a variety of applications in the areas of transportation and communication in distributed systems. In this paper, we design and prove the correctness of a self-stabilizing algorithm which finds the center(s) for a distributed system with a tree topology. The computational model employed in this paper was introduced by Dolev et al., which assumes the read/write separate atomicity. (C) 2004 Elsevier Ltd. All rights reserved.
The cutting number of a node i in a connected graph G is the number of pairs of nodes in different components of G-{i}. The cutting center consists of the set of nodes of G with maximal cutting number. This article pr...
详细信息
The cutting number of a node i in a connected graph G is the number of pairs of nodes in different components of G-{i}. The cutting center consists of the set of nodes of G with maximal cutting number. This article presents a self-stabilizing algorithm for finding the cutting numbers for all nodes of a tree T= (V-T, E-T) and hence the cutting center of T . It is shown that the proposed self-stabilizing algorithm requires O(n(2)) moves. The algorithm complexity can also be expressed as O(n) rounds.
self-stabilization is a theoretical framework of non-masking fault-tolerant distributed algorithms. In this paper, we investigate the Steiner tree problem in distributed systems, and propose a self-stabilizing heurist...
详细信息
self-stabilization is a theoretical framework of non-masking fault-tolerant distributed algorithms. In this paper, we investigate the Steiner tree problem in distributed systems, and propose a self-stabilizing heuristic solution to the problem. Our algorithm is constructed by four layered modules (sub-algorithms): construction of a shortest path forest, transformation of the network, construction of a minimum spanning tree, and pruning unnecessary links and processes. Competitiveness is 2(1 - 1/l), where l is the number of leaves of optimal solution.
The cutting number of a node i in a connected graph G is the number of pairs of nodes in different components of G - {i}. The cutting center consists of the set of nodes of G with maximal cutting number. This paper pr...
详细信息
ISBN:
(纸本)1892512459
The cutting number of a node i in a connected graph G is the number of pairs of nodes in different components of G - {i}. The cutting center consists of the set of nodes of G with maximal cutting number. This paper presents a self-stabilizing algorithm for finding the cutting numbers for all nodes of a tree T = < V-T;E-T> and hence the cutting center of T It is shown that the proposed self-stabilizing algorithm requires O(n(2)) moves. The algorithm complexity can also be expressed as O(n) rounds.
Given a graph G and some property p(g), a p-ranking (ordering) of the nodes of G can be defined as a one-to-one function from V to {1, 2, 3, ..., n} such that property p(G) holds for each node i is an element of V. In...
详细信息
Given a graph G and some property p(g), a p-ranking (ordering) of the nodes of G can be defined as a one-to-one function from V to {1, 2, 3, ..., n} such that property p(G) holds for each node i is an element of V. In this paper we present an O(n(2)) self-stabilizing algorithm which, when given a rooted tree T, will provide p-rankings consistent with the following standard graph traversal properties: (i) pre-order traversal;(ii) postorder traversal;(iii) reverse-postorder traversal;(iv) breadth-first traversal;(v) breadth-depth traversal.
In this paper, we propose a self-stabilizing algorithm for finding shortest paths in a distributed system in which a central daemon is assumed. The correctness of the proposed algorithm is proved by using the bounded ...
详细信息
In this paper, we propose a self-stabilizing algorithm for finding shortest paths in a distributed system in which a central daemon is assumed. The correctness of the proposed algorithm is proved by using the bounded function technique. (C) 2001 Elsevier Science Ltd. All rights reserved.
暂无评论