Polynomial Silent Self-Stabilizing p-Star Decomposition (Short Paper)

摘要

We present a silent self-stabilizing distributed algorithm computing a maximal p-star decomposition of the underlying communication network. Under the unfair distributed scheduler, the most general scheduler model, the algorithm converges in at most 12Δm + O(m + n) moves, where m is the number of edges, n is the number of nodes, and Δ is the maximum node degree. Regarding the move complexity, our algorithm outperforms the previously known best algorithm by a factor of Δ. While the round complexity for the previous algorithm was unknown, we show a 5 (「n/(p+1)」) + 5 bound for our algorithm.