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 + \mathcal{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\big \lfloor \frac{n}{p+1} \big \rfloor +5$ bound for our algorithm.