SCIENCE@home

Fast, Robust, Quantizable Approximate Consensus

Bernadette Charron-Bost,Matthias Függer,Thomas Nowak

Published 2016 in International Colloquium on Automata, Languages and Programming

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.

PUBLICATION RECORD

  • Publication year

    2016

  • Venue

    International Colloquium on Automata, Languages and Programming

  • Publication date

    2016-07-12

  • Fields of study

    Mathematics, Computer Science

  • Identifiers
    DOI 10.4230/LIPIcs.ICALP.2016.137
  • External record

    Open on Semantic Scholar

  • Source metadata

    Semantic Scholar

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-27 of 27 references · Page 1 of 1

CITED BY

Showing 1-9 of 9 citing papers · Page 1 of 1