Name
Abstract | ||
|---|---|---|
In network distributed computing, minimum spanning tree (MST) is one of the key problems, and silent self-stabilization one of the most demanding fault-tolerance properties. For this problem and this model, a polynomial-time algorithm with $O(\log^2\!n)$ memory is known for the state model. This is memory optimal for weights in the classic $[1,\text{poly}(n)]$ range (where $n$ is the size of the network). In this paper, we go below this $O(\log^2\!n)$ memory, using approximation and parametrized complexity. More specifically, our contributions are two-fold. We introduce a second parameter~$s$, which is the space needed to encode a weight, and we design a silent polynomial-time self-stabilizing algorithm, with space $O(\log n \cdot s)$. In turn, this allows us to get an approximation algorithm for the problem, with a trade-off between the approximation ratio of the solution and the space used. For polynomial weights, this trade-off goes smoothly from memory $O(\log n)$ for an $n$-approximation, to memory $O(\log^2\!n)$ for exact solutions, with for example memory $O(\log n\log\log n)$ for a 2-approximation. |
Year | Venue | DocType |
|---|---|---|
2019 | arXiv: Distributed, Parallel, and Cluster Computing | Journal |
Volume | Citations | PageRank |
abs/1905.08565 | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Lélia Blin | 1 | 0 | 0.68 |
| Swan Dubois | 2 | 145 | 17.21 |
| Laurent Feuilloley | 3 | 19 | 6.49 |