文章基本信息
- 标题：Self-Stabilizing Algorithms for Maximal 2-packing and General k-packing (k ≥ 2) with Safe Convergence in an Arbitrary Graph
- 本地全文：下载
- 作者：Yihua Ding ; James Wang ; Pradip K Srimani 等
- 期刊名称：International Journal of Networking and Computing
- 印刷版ISSN：2185-2847
- 出版年度：2015
- 卷号：5
- 期号：1
- 页码：105-121
- 语种：English
- 出版社：International Journal of Networking and Computing
- 摘要：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.Â
- 其他摘要：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 ( n 2 ) 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 ( kn 2 ) steps under synchronous daemon; the algorithm has space complexity of O ( kn log n ) bits at each node; existing algorithms for k -packing stabilize in exponential time under a central daemon with O (log n ) space complexity.Â
- 关键词：Self-stabilization;Maximal 2-packing;Maximal k-packing;Safe Convergence;Synchronous Daemon
