Self-Stabilizing Algorithm for Maximal 2-Packing with Safe Convergence in an Arbitrary Graph

In a graph or a network G = (V, E), a set S C V is a 2-packing if Vi ∈ 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.