Polynomial Silent Self-Stabilizing p-Star Decomposition

摘要

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 time complexity, we obtain the following results: our algorithm outperforms the previously known best algorithm by a factor of Δ with respect to the move complexity. While the round complexity for the previous algorithm was unknown, we show a 5「n/p+1」+5 bound for our algorithm.