Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):
B. Charron-Bost, M Függer, T. Nowak:
"Fast, Robust, Quantizable Approximate Consensus";
Vortrag: International Colloquium on Automata, Languages and Programming (ICALP),
Rome, Italy;
12.07.2016
- 15.07.2016; in: "Proceedings 43rd International Colloquium on Automata, Languages, and Programming (ICALP'16)",
Leibniz International Proceedings in Informatics (LIPIcs),
(2016),
ISBN: 978-3-95977-013-2;
S. 1
- 14.
Kurzfassung englisch:
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.
Schlagworte:
approximate consensus, dynamic networks, averaging algorithms
"Offizielle" elektronische Version der Publikation (entsprechend ihrem Digital Object Identifier - DOI)
http://dx.doi.org/10.4230/LIPIcs.ICALP.2016.137
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.