Name
Abstract | ||
|---|---|---|
We introduce a new class of distributed algorithms for the approximate consensus problem in dynamic rooted networks, which we call amortized averaging algorithms. They are deduced from ordinary averaging algorithms by adding a value-gathering phase before each value update. This results in a drastic drop in decision times, from being exponential in the number n of processes to being polynomial under the assumption that each process knows n. In particular, the amortized midpoint algorithm is the first algorithm that achieves a linear decision time in dynamic rooted networks with an optimal contraction rate of 1/2 at each update step.We then show robustness of the amortized midpoint algorithm under violation of network assumptions: it gracefully degrades if communication graphs from time to time are non rooted, or under a wrong estimate of the number of processes. Finally, we prove that the amortized midpoint algorithm behaves well if processes can store and send only quantized values, rendering it well-suited for the design of dynamic networked systems. As a corollary we obtain that the 2-set consensus problem is solvable in linear time in any dynamic rooted network model. |
Year | Venue | Field |
|---|---|---|
2016 | ICALP | Consensus,Discrete mathematics,Mathematical optimization,Combinatorics,Polynomial,Midpoint,Computer science,Amortized analysis,Robustness (computer science),Distributed algorithm,Time complexity,Network model |
DocType | Citations | PageRank |
Conference | 2 | 0.38 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Bernadette Charron-bost | 1 | 785 | 67.22 |
| Matthias Függer | 2 | 167 | 21.14 |
| Thomas Nowak | 3 | 32 | 9.18 |