We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
DISTANCE-TWO INFORMATION IN SELF-STABILIZING ALGORITHMS.
- Authors
Gairing, Martin; Goddard, Wayne; Hedetniemi, Stephen T.; Kristiansen, Petter; McRae, Alice A.
- 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 dáemon.
- Subjects
PARALLEL processing; PACKING (Mechanical engineering); MULTIPROCESSORS; PARALLEL programming; ELECTRONIC data processing; COMPUTER programming
- Publication
Parallel Processing Letters, 2004, Vol 14, Issue 3/4, p387
- ISSN
0129-6264
- Publication type
Article
- DOI
10.1142/S0129626404001970