Talks and Poster Presentations (with Proceedings-Entry):
B. Charron-Bost, M Függer, T. Nowak:
"Fast, Robust, Quantizable Approximate Consensus";
Talk: International Colloquium on Automata, Languages and Programming (ICALP),
- 2016-07-15; in: "Proceedings 43rd International Colloquium on Automata, Languages, and Programming (ICALP'16)",
Leibniz International Proceedings in Informatics (LIPIcs),
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.
approximate consensus, dynamic networks, averaging algorithms
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
Created from the Publication Database of the Vienna University of Technology.