Fast, Robust, Quantizable Approximate Consensus *

Bernadette Charron-Bost (1) , Matthias Függer (2) , Thomas Nowak (3)

1 LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
2 MPII - Max-Planck-Institut für Informatik
3 ParSys - LRI - Systèmes parallèles (LRI)

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. 1 Introduction This paper studies the problem of approximate consensus: given a set of processes, each of them with an initial real value, for any positive real number ε, every process has to achieve ε-consensus, i.e., decides on one value that lies in the range of the initial values and that differs from the other decision values by at most ε. This problem, which is a weakening of exact (ε = 0) consensus, has a large variety of applications in distributed computing or multi-agent control (e.g., clock synchronization or geometric coordination tasks) and often has to be solved in the context of dynamic networks, using local information, and under adverse constraints. In recent work [8], we proved that approximate consensus is solvable in a dynamic network model if and only if the directed time-varying communication graph is always rooted, i.e., *

Mots clés: approximate consensus; dynamic networks; averaging algorithms

Domaines: Calcul parallèle, distribué et partagé [cs.DC]

Bernadette Charron-Bost, Matthias Függer, Thomas Nowak. Fast, Robust, Quantizable Approximate Consensus *. 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), Jul 2016, Rome, Italy. ⟨10.4230/LIPIcs.ICALP.2016.137⟩. ⟨hal-01395576⟩