A New Self-stabilizing Algorithm for Maximal 2-packing

Authors: Zhengnan Shi

Abstract:

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: self-stabilization, 2-packing, distributed computing, fault tolerance, graph algorithms

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1081683

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.