Distance- k knowledge in self-stabilizing algorithms

Many graph problems seem to require knowledge that extends beyond the immediate neighbors of a node. The usual self-stabilizing model only allows for nodes to make decisions based on the states of their immediate neighbors. We provide a general transformation for constructing self-stabilizing algorithms which utilize distance- k knowledge. Our transformation has both a slowdown and space overhead in n O ( log k ), and might be thought of as a distance- k resource allocation algorithm. Our main application is a polynomial-time self-stabilizing algorithm for finding maximal irredundant sets, a problem which seems to require distance-4 information. These results can be generalized to efficiently find maximal P -sets, for properties P which we call local monotonic. Our techniques extend results in a recent paper by Gairing et al. for achieving distance-two information.

Authors

• Wayne Goddard
• Stephen T. Hedetniemi
• David P. Jacobs
• Vilmar Trevisan

Keywords

• Polynomial-time
• Self-stabilizing
• Algorithm
• k -packing
• Irredundant