Polynomial Silent Self-Stabilizing p-Star Decomposition. (17th November 2019) - Haddad, Mohammed; Johnen, Colette; Köhler, Sven
Abstract: 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 5np+1 floor +5 bound for our algorithm.