Back to Search
Start Over
Polynomial Silent Self-Stabilizing p-Star Decomposition.
- Source :
-
Computer Journal . Feb2020, Vol. 63 Issue 2, p253-266. 14p. - Publication Year :
- 2020
-
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. [ABSTRACT FROM AUTHOR]
- Subjects :
- *POLYNOMIALS
*TELECOMMUNICATION systems
*DISTRIBUTED algorithms
Subjects
Details
- Language :
- English
- ISSN :
- 00104620
- Volume :
- 63
- Issue :
- 2
- Database :
- Academic Search Index
- Journal :
- Computer Journal
- Publication Type :
- Academic Journal
- Accession number :
- 142721549
- Full Text :
- https://doi.org/10.1093/comjnl/bxz102