A New Self-stabilizing Algorithm for Maximal 2-packing

In the self-stabilizing algorithmic paradigm, each node has a local view of the system, in a finite amount of time the system converges to a global state with desired property. In a graph G = (V, E), a subset S C V is a 2-packing if Vi c V: IN[i] n SI <1. In this paper, an ID-based, constant space, self-stabilizing algorithm that stabilizes to a maximal 2-packing in an arbitrary graph is proposed. It is shown that the algorithm stabilizes in 0(n3) moves under any scheduler (daemon). Specifically, it is shown that the algorithm stabilizes in linear time-steps under a synchronous daemon where every privileged node moves at each time-step.

Authors:

• Zhengnan Shi

Keywords:

• self-stabilization
• 2-packing
• distributed computing
• fault tolerance
• graph algorithms

References:

[1] Y. Afek and S. Dolev. Local stabilizer. J. Parallel Distrib. Comput.,
62(5):745-765, 2002.
[2] J. Beauquier, A. K. Datta, M. Gradinariu, and F. Magniette. Selfstabilizing
local mutual exclusion and daemon refinement. In International
Symposium on Distributed Computing, pages 223-237, 2000.
[3] E. W. Dijkstra. Self-stabilizing systems in spite of distributed control.
Comm. ACM, 17(11):643-644, Jan. 1974.
[4] S. Dolev. Self-Stabilization. MIT Press, 2000.
[5] S. Dolev, A. Israeli, and S. Moran. Uniform dynamic self-stabilizing
leader election. IEEE Trans. on Parallel and Distributed Systems, 8(4),
1995.
[6] W. Goddard, S. T. Hedetniemi, D. P. Jacobs, and P. K. Srimani. Selfstabilizing
algorithms for orderings and colorings. International Journal
of Foundations of Computer Science, 16:19-36, 2005.
[7] S. M. Hedetniemi, S. T. Hedetniemi, D. P. Jacobs, and P. K. Srimani.
Self-stabilizing algorithms for minimal dominating sets and maximal
independent sets. Comput. Math. Appl., 46(5-6):805-811, 2003.
[8] D. S. Hochbaum and D. B. Schmoys. A best possible heuristic for the
k-center problem. Mathematics of Operations Research, 10(2):180-184,
1985.
[9] S.-C. Hsu and S.-T. Huang. A self-stabilizing algorithm for maximal
matching. Inform. Process. Lett., 43:77-81, 1992.
[10] A. Meir and J. W. Moon. Relations between packing and covering
numbers of a tree. Pacific Journal of Mathematics, 61(1):225-233, 1975.
[11] A. Panconesi and A. Srinivasan. The local nature of -coloring and its
algorithmic applications. Combinatorica, 15:225-280, 1995.
[12] S. Rajagopalan and V. Vazirani. Primal-dual RNC approximation
algorithms for set cover and covering integer programs. SIAM J.
Comput., 28:525-540, 1998.
[13] Z. Shi, W. Goddard, and S. T. Hedetniemi. an anonymous selfstabilizing
algorithm for 1-maximal independent set in trees. Information
Processing Letters, 91(2):77-83, 2004.
[14] S. Shukla, D. Rosenkrantz, and S. Ravi. Observations on self-stabilizing
graph algorithms for anonymous networks. In Proceedings of the Second
Workshop on Self-Stabilizing Systems, pages 7.1-7.15, 1995.
[15] G. Tel. Introduction to Distributed Algorithms, Second Edition. Cambridge
University Press, Cambridge UK, 2000.