2026-07-19T18:23:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6281 2024-03-06T10:37:56Z ddc:004 open_access

Fast, Robust, Quantizable Approximate Consensus Charron-Bost, Bernadette Függer, Matthias Nowak, Thomas approximate consensus dynamic networks averaging algorithms 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Bernadette Charron-Bost and Matthias Függer and Thomas Nowak 2016 Is Part Of LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2016.137 urn:nbn:de:0030-drops-62812 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.137 eng https://creativecommons.org/licenses/by/3.0/legalcode