<div class="csl-bib-body">
<div class="csl-entry">Charron-Bost, B., Függer, M., & Nowak, T. (2016). Fast, Robust, Quantizable Approximate Consensus. In I. Chatzigiannakis, M. Mitzenmacher, Y. Rabani, & D. Sangiorgi (Eds.), <i>Proceedings 43rd International Colloquium on Automata, Languages, and Programming (ICALP’16)</i> (pp. 137:1-137:14). Leibniz International Proceedings in Informatics (LIPIcs). https://doi.org/10.4230/LIPIcs.ICALP.2016.137</div>
</div>
-
dc.identifier.isbn
978-3-95977-013-2
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/56744
-
dc.description.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.
en
dc.language.iso
en
-
dc.publisher
Leibniz International Proceedings in Informatics (LIPIcs)
-
dc.relation.ispartofseries
Leibniz International Proceedings in Informatics (LIPIcs)
-
dc.subject
dynamic networks
-
dc.subject
approximate consensus
-
dc.subject
averaging algorithms
-
dc.title
Fast, Robust, Quantizable Approximate Consensus
en
dc.type
Konferenzbeitrag
de
dc.type
Inproceedings
en
dc.relation.publication
Proceedings 43rd International Colloquium on Automata, Languages, and Programming (ICALP'16)
-
dc.relation.isbn
978-3-95977-013-2
-
dc.relation.doi
10.4230/LIPIcs.ICALP.2016.0
-
dc.relation.issn
1868-8969
-
dc.description.startpage
137:1
-
dc.description.endpage
137:14
-
dc.type.category
Full-Paper Contribution
-
tuw.booktitle
Proceedings 43rd International Colloquium on Automata, Languages, and Programming (ICALP'16)
-
tuw.container.volume
55
-
tuw.peerreviewed
true
-
tuw.relation.publisher
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
-
tuw.relation.publisherplace
Dagstuhl
-
tuw.researchTopic.id
I2
-
tuw.researchTopic.name
Computer Engineering and Software-Intensive Systems
-
tuw.researchTopic.value
100
-
tuw.publication.orgunit
E191-02 - Forschungsbereich Embedded Computing Systems
-
tuw.publisher.doi
10.4230/LIPIcs.ICALP.2016.137
-
dc.description.numberOfPages
14
-
tuw.event.name
International Colloquium on Automata, Languages and Programming (ICALP)