DISTANCE-TWO INFORMATION IN SELF-STABILIZING ALGORITHMS
Authors:
- 1 September 2004
- journal article
- research article
- Published by World Scientific Pub Co Pte Ltd in Parallel Processing Letters
- Vol. 14 (03n04) , 387-398
Abstract
In the state-based self-stabilizing algorithmic paradigm for distributed computing, each node has only a local view of the system (seeing its neighbors' states), yet in a finite amount of time the system converges to a global state satisfying some desired property. In this paper we introduce a general mechanism that allows a node to act only on correct distance-two knowledge, provided there are IDs. We then apply the mechanism to graph problems in the areas of coloring and domination. For example, we obtain an algorithm for maximal 2-packing which is guaranteed to stabilize in polynomial moves under a central daemon.Keywords
This publication has 8 references indexed in Scilit:
- Self-stabilizing algorithms for minimal dominating sets and maximal independent setsComputers & Mathematics with Applications, 2003
- Maximal matching stabilizes in time O(m)Information Processing Letters, 2001
- Introduction to Distributed Algorithms2000
- Self-Stabilization2000
- Maximal matching stabilizes in quadratic timeInformation Processing Letters, 1994
- Labelling Graphs with a Condition at Distance 2SIAM Journal on Discrete Mathematics, 1992
- A self-stabilizing algorithm for maximal matchingInformation Processing Letters, 1992
- Self-stabilizing systems in spite of distributed controlCommunications of the ACM, 1974