Polynomial Silent Self-Stabilizing p-Star Decomposition. (17th November 2019)

• Record Type: Journal Article
• Authors: Haddad, Mohammed; Johnen, Colette; Köhler, Sven
• Is Part Of: Computer journal. Volume 63:Number 2(2020)
• Page Start: 253
• Page End: 266
• Publication Date: 2019-11-17
• Subjects: distributed algorithm -- self-stabilization -- graph decomposition -- p-star decomposition -- move complexity -- round complexity; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxz102
• Languages: English
• ISSNs: 0010-4620

Abstract

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\Delta m + \mathcal{O}(m+n)$ moves, where $m$ is the number of edges, $n$ is the number of nodes and $\Delta $ 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 $\Delta $ 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.