Self-Stabilizing Algorithms for Maximal 2-packing and General k-packing (k ≥ 2) with Safe Convergence in an Arbitrary Graph

Abstract

In a graph or a network G=(V,E), a set S⊆V is a 2-packing if ∀i∈V:|N[i]∩S|≤1, where N[i] denotes the closed neighborhood of node i. A 2-packing is maximal if no proper superset of S is a 2-packing. This paper presents a safely converging self-stabilizing algorithm for maximal 2-packing problem. Under a synchronous daemon, it quickly converges to a 2- packing (a safe state, not necessarily the legitimate state) in three synchronous steps, and then terminates in a maximal one (the legitimate state) in O(n) steps without breaking safety during the convergence interval, where n is the number of nodes. Space requirement at each node is O(log n) bits. This is a significant improvement over the most recent self-stabilizing algorithm for maximal 2-packing that uses O(n2) synchronous steps with same space complexity and that does not have safe convergence property. We then generalize the technique to design a self- stabilizing algorithm for maximal k-packing, k ≥ 2, with safe convergence that stabilizes in O(kn2) steps under synchronous daemon; the algorithm has space complexity of O(knlogn) bits at each node; existing algorithms for k-packing stabilize in exponential time under a central daemon with O(log n) space complexity.