| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427702 | Information Processing Letters | 2012 | 7 Pages |
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).
