A self-stabilizing algorithm to maximal 2-packing with improved complexity

In self-stabilization, each node has a local view of the distributed network system, in a finite amount of time the system converges to a global setup with desired property, in this case establishing a 2-packing set. Using a graph G=(V,E)G=(V,E) to represent the network, a subset S⊆VS⊆V is a 2-packing if ∀i∈V:|N[i]∩S|⩽1∀i∈V:|N[i]∩S|⩽1. In this paper, we first propose an ID-based, constant space, self-stabilizing algorithm that stabilizes to a maximal 2-packing in an arbitrary graph. We show that the algorithm stabilizes in O(mn)O(mn) moves under any scheduler (such as a distributed daemon). Secondly, we show that the algorithm stabilizes in O(n2)O(n2) rounds under a synchronous daemon where every privileged node moves at each round.

► A self-stabilizing algorithm stabilizes to a maximal 2-packing.
► It stabilizes in O(mn)O(mn) moves under any scheduler (such as a distributed daemon).
► It stabilizes in O(n2)O(n2) rounds under a synchronous daemon.
► It improves the current best solution by a factor of Δ or O(n)O(n).