A self-stabilizing algorithm to maximal 2-packing with improved complexity |
| |
Authors: | Zhengnan Shi |
| |
Affiliation: | Department of Mathematical and Computer Sciences, University of Wisconsin, Whitewater, WI 53190, United States |
| |
Abstract: | 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) to represent the network, a subset S⊆V is a 2-packing if ∀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) moves under any scheduler (such as a distributed daemon). Secondly, we show that the algorithm stabilizes in O(n2) rounds under a synchronous daemon where every privileged node moves at each round. |
| |
Keywords: | Self-stabilization 2-packing Distributed computing Fault tolerance Graph algorithms |
本文献已被 ScienceDirect 等数据库收录! |
|