Bernadette Charron-Bost

Bernadette Charron-Bost, Patrick Lambein-Monette

A variety of problems in distributed control involve a networked system of autonomous agents cooperating to carry out some complex task in a decentralized fashion, e.g., orienting a flock of drones, or aggregating data from a network of sensors. Many of these complex tasks reduce to the computation of a global function of values privately held by the agents, such as the maximum or the average. Distributed algorithms implementing these functions should rely on limited assumptions on the topology of the network or the information available to the agents, reflecting the decentralized nature of the problem. We present a randomized algorithm for computing the average in networks with directed, time-varying communication topologies. With high probability, the system converges to an estimate of the average in linear time in the number of agents, provided that the communication topology remains strongly connected over time. This algorithm leverages properties of exponential random variables, which allows for approximating sums by computing minima. It is completely decentralized, in the sense that it does not rely on agent identifiers, or global information of any kind. Besides, the agents do not need to know their out-degree; hence, our algorithm demonstrates how randomization can be used to circumvent the impossibility result established in [1]. Using a logarithmic rounding rule, we show that this algorithm can be used under the additional constraints of finite memory and channel capacity. We furthermore extend the algorithm with a termination test, by which the agents can decide irrevocably in finite time - rather than simply converge - on an estimate of the average. This terminating variant works under asynchronous starts and yields linear decision times while still using quantized - albeit larger - values.

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

We study the problem of asymptotic consensus as it occurs in a wide range of applications in both man-made and natural systems. In particular, we study systems with directed communication graphs that may change over time. We recently proposed a new family of convex combination algorithms in dimension one whose weights depend on the received values and not only on the communication topology. Here, we extend this approach to arbitrarily high dimensions by introducing two new algorithms: the ExtremePoint and the Centroid algorithm. Contrary to classical convex combination algorithms, both have component-wise contraction rates that are constant in the number of agents. Paired with a speed-up technique for convex combination algorithms, we get a convergence time linear in the number of agents, which is optimal. Besides their respective contraction rates, the two algorithms differ in the fact that the Centroid algorithm's update rule is independent of any coordinate system while the ExtremePoint algorithm implicitly assumes a common agreed-upon coordinate system among agents. The latter assumption may be realistic in some man-made multi-agent systems but is highly questionable in systems designed for the modelization of natural phenomena. Finally we prove that our new algorithms also achieve asymptotic consensus under very weak connectivity assumptions, provided that agent interactions are bidirectional.

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

In this note, we give a complete proof that Hegselmann-Krause systems converge on the circle following the proof strategy developed by Hegarty, Martinsson, and Wedin.