Many problems in distributed control reduce to the distributed computation of the average of initial values in a networked system of autonomous agents, known as the average consensus problem. We present a randomized algorithm that solves this problem in networks with directed, time-varying communication topologies, in linear time in the size of the network. 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.
We investigate the approximate consensus problem in highly dynamic networks in which topology may change continually and unpredictably. We prove that in both synchronous and partially synchronous networks, approximate consensus is solvable if and only if the communication graph in each round has a rooted spanning tree. Interestingly, the class of averaging algorithms, which have the benefit of being memoryless and requiring no process identifiers, entirely captures the solvability issue of approximate consensus in that the problem is solvable if and only if it can be solved using any averaging algorithm. We develop a proof strategy which for each positive result consists in a reduction to the nonsplit networks. It dramatically improves the best known upper bound on the decision times of averaging algorithms and yields a quadratic time non-averaging algorithm for approximate consensus in non-anonymous networks. We also prove that a general upper bound on the decision times of averaging algorithms have to be exponential, shedding light on the price of anonymity. Finally we apply our results to networked systems with a fixed topology and benign fault models to show that with n processes, up to @math of link faults per round can be tolerated for approximate consensus, increasing by a factor 2 the bound of Santoro and Widmayer for exact consensus. Motivated by applications to sensor, peer-to-peer, and ad-hoc networks, we study the problem of computing functions of values at the nodes in a network in a totally distributed manner. In particular, we consider separable functions, which can be written as linear combinations of functions of individual variables. Known iterative algorithms for averaging can be used to compute the normalized values of such functions, but these algorithms do not extend in general to the computation of the actual values of separable functions.The main contribution of this paper is the design of a distributed randomized algorithm for computing separable functions based on properties of exponential random variables. We bound the running time of our algorithm in terms of the running time of an information spreading algorithm used as a subroutine by the algorithm. Since we are interested in totally distributed algorithms, we consider a randomized gossip mechanism for information spreading as the subroutine. Combining these algorithms yields a complete and simple distributed algorithm for computing separable functions.The second contribution of this paper is an analysis of the information spreading time of the gossip algorithm. This analysis yields an upper bound on the information spreading time, and therefore a corresponding upper bound on the running time of the algorithm for computing separable functions, in terms of the conductance of an appropriate stochastic matrix. These bounds imply that, for a class of graphs with small spectral gap (such as grid graphs), the time used by our algorithm to compute averages is of a smaller order than the time required for the computation of averages by a known iterative gossip scheme [5].