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.
Our algorithm leverages the fact that the minimum function can be easily computed in this general setting. By individually sampling exponential random distributions with adequate rates and then by computing the minimum of the so-generated random numbers, agents can estimate the sum of initial values and the size of the network, yielding an estimate of the average. This approach was first introduced in @cite_16 for a gossip communication model, and later applied in @cite_31 to the design of distributed counting algorithms in networked systems equipped with a global clock that delivers synchronous start signals to the agents. The main features of some of the average consensus algorithms discussed above, including our own randomized algorithm, denoted @math , are summarized in Table 1.
@cite_31 @cite_16
2134252677 2148330908 2140637933 2493170922
Various randomized consensus algorithms have been proposed in the literature. In some case randomness is due to the choice of a randomized network communication protocol. In other cases, randomness is simply caused by the potential unpredictability of the environment in which the distributed consensus algorithm is implemented. Conditions ensuring the convergence of these algorithms have already been proposed in the literature. As far as the rate of convergence of such algorithms, two approaches can be proposed. One is based on a mean square analysis, while a second is based on the concept of Lyapunov exponent. In this paper, by some concentration results, we prove that the mean square convergence analysis is the right approach when the number of agents is large. Differently from the existing literature, in this paper we do not stick to average preserving algorithms. Instead, we allow to reach consensus at a point which may differ from the average of the initial states. The advantage of such algorithms is that they do not require bidirectional communication among agents and thus they apply to more general contexts. Moreover, in many important contexts it is possible to prove that the displacement from the initial average tends to zero, when the number of agents goes to infinity. Motivated by applications to wireless sensor, peer-to-peer, and ad hoc networks, we study distributed broadcasting algorithms for exchanging information and for computing in an arbitrarily connected network of nodes. Specifically, we propose a broadcasting-based gossiping algorithm to compute the (possibly weighted) average of the initial measurements of the nodes at every node in the network. We show that the broadcast gossip algorithms almost surely converge to a consensus. In addition, the random consensus value is, in expectation, equal to the desired value, i.e., the average of initial node measurements. However, the broadcast gossip algorithms do not converge to the initial average in absolute sense because of the fact that the sum is not preserved at every iteration. We provide theoretical results on the mean square error performance of the broadcast gossip algorithms. The results indicate that the mean square error strictly decreases through iterations until the consensus is achieved. Finally, we assess and compare the communication cost of the broadcast gossip algorithms required to achieve a given distance to consensus through numerical simulations. Motivated by applications to wireless sensor, peer-to-peer, and ad hoc networks, we have recently proposed a broadcasting-based gossiping protocol to compute the (possibly weighted) average of the initial measurements of the nodes at every node in the network. The class of broadcast gossip algorithms achieve consensus almost surely at a value that is in the neighborhood of the initial node measurements? average. In this paper, we further study the broadcast gossip algorithms: we derive and analyze the optimal mixing parameter of the algorithm when approached from worst-case convergence rate, present theoretical results on limiting mean square error performance of the algorithm, and find the convergence rate order of the proposed protocol. This paper considers the basic PULL model of communication, in which in each round, each agent extracts information from few randomly chosen agents. We seek to identify the smallest amount of information revealed in each interaction (message size) that nevertheless allows for efficient and robust computations of fundamental information dissemination tasks. We focus on the Majority Bit Dissemination problem that considers a population of n agents, with a designated subset of source agents. Each source agent holds an input bit and each agent holds an output bit. The goal is to let all agents converge their output bits on the most frequent input bit of the sources (the majority bit). Note that the particular case of a single source agent corresponds to the classical problem of Broadcast (also termed Rumor Spreading). We concentrate on the severe fault-tolerant context of self-stabilization, in which a correct configuration must be reached eventually, despite all agents starting the execution with arbitrary initial states. In particular, the specification of who is a source and what is its initial input bit may be set by an adversary. We first design a general compiler which can essentially transform any self-stabilizing algorithm with a certain property (called "the bitwise-independence property") that uses l-bits messages to one that uses only log l-bits messages, while paying only a small penalty in the running time. By applying this compiler recursively we then obtain a self-stabilizing Clock Synchronization protocol, in which agents synchronize their clocks modulo some given integer T, within O(log n log T) rounds w.h.p., and using messages that contain 3 bits only. We then employ the new Clock Synchronization tool to obtain a self-stabilizing Majority Bit Dissemination protocol which converges in O(log n) time, w.h.p., on every initial configuration, provided that the ratio of sources supporting the minority opinion is bounded away from half. Moreover, this protocol also uses only 3 bits per interaction.