Commenced in January 2007
Frequency: Monthly
Edition: International
Paper Count: 30576
A New Self-stabilizing Algorithm for Maximal 2-packing

Authors: Zhengnan Shi


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.

Keywords: Distributed Computing, Fault tolerance, graph algorithms, self-stabilization

Digital Object Identifier (DOI):

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1238


[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.