This paper presents an algorithm which solves exponentially fast the average consensus problem on strongly connected network of digital links. The algorithm is based on an efficient zooming-in zooming-out quantization scheme.
@cite_4: We consider distributed iterative algorithms for the averaging problem over time-varying topologies. Our focus is on the convergence time of such algorithms when complete (unquantized) information is available, and on the degradation of performance when only quantized information is available. We study a large and natural class of averaging algorithms, which includes the vast majority of algorithms proposed to date, and provide tight polynomial bounds on their convergence time. We also describe an algorithm within this class whose convergence time is the best among currently available averaging algorithms for time-varying topologies. We then propose and analyze distributed averaging algorithms under the additional constraint that agents can only store and communicate quantized information, so that they can only converge to the average of the initial values of the agents within some error. We establish bounds on the error and tight bounds on the convergence time, as a function of the number of quantization levels.
@cite_8: We consider a network of distributed sensors, where where each sensor takes a linear measurement of some unknown parameters, corrupted by independent Gaussian noises. We propose a simple distributed iterative scheme, based on distributed average consensus in the network, to compute the maximum-likelihood estimate of the parameters. This scheme doesn't involve explicit point-to-point message passing or routing; instead, it diffuses information across the network by updating each node's data with a weighted average of its neighbors' data (they maintain the same data structure). At each step, every node can compute a local weighted least-squares estimate, which converges to the global maximum-likelihood solution. This scheme is robust to unreliable communication links. We show that it works in a network with dynamically changing topology, provided that the infinitely occurring communication graphs are jointly connected.
@cite_9: This work presents a contribution to the solution of the average agreement problem on a network with quantized links. Starting from the well-known linear diffusion algorithm, we propose a simple and effective adaptation that is able to preserve the average of states and to drive the system near to the consensus value, when a uniform quantization is applied to communication between agents. The properties of this algorithm are investigated both by a worst-case analysis and by a probabilistic analysis, and are shown to depend on the spectral properties of the evolution matrix. A special attention is devoted to the issue of the dependence of the performance on the number of agents, and several examples are given. Copyright © 2008 John Wiley & Sons, Ltd.
@cite_17: 
@cite_3: In this work we present a new algorithm to solve the average-consensus problem. The main goal of this algorithm is to obtain exact convergence despite the existence of quantized communication channels between the agents. Starting from the Zoom-in Zoom-out strategy already presented in [5], we introduce the equations describing the behaviour of the algorithm and we formally prove the asymptotic agreement. We will also show that, under a reasonable hypothesis, the algorithm parameters ensuring convergence, can be chosen regardless the number of agents.
@cite_0: In this paper, we develop algorithms for distributed computation of averages of the node data over networks with bandwidth power constraints or large volumes of data. Distributed averaging algorithms fail to achieve consensus when deterministic uniform quantization is adopted. We propose a distributed algorithm in which the nodes utilize probabilistically quantized information, i.e., dithered quantization, to communicate with each other. The algorithm we develop is a dynamical system that generates sequences achieving a consensus at one of the quantization values almost surely. In addition, we show that the expected value of the consensus is equal to the average of the original sensor data. We derive an upper bound on the mean-square-error performance of the probabilistically quantized distributed averaging (PQDA). Moreover, we show that the convergence of the PQDA is monotonic by studying the evolution of the minimum-length interval containing the node values. We reveal that the length of this interval is a monotonically nonincreasing function with limit zero. We also demonstrate that all the node values, in the worst case, converge to the final two quantization bins at the same rate as standard unquantized consensus. Finally, we report the results of simulations conducted to evaluate the behavior and the effectiveness of the proposed algorithm in various scenarios.
@cite_2: This thesis addresses problems of optimization to be solved collectively (distributely, we say) by groups of networked agents having limited communication and computation capabilities. The focus is on two paradigmatic problems, average consensus and coverage control. The former consists in computing the average of values which are priory known to the agents, while the latter consists in optimally deploying robotic agents in a given environment. Their solution is possible thanks to iterative algorithms which exploit the available communications among agents, described by a graph. Research has been very intense in latest years on these problems, due to strong applicative motivations: these algorithms are crucial for the design of networks of sensors, and for the coordinated motion of groups of unmanned vehicles. Namely, the ultimate goal of these algorithms is to make such artificial networks able to self-organize and perform specific tasks without a centralized supervision. In the thesis networks have been considered, which allow only communication in pairs, or limited to messages belonging to a discrete alphabet. Several novel algorithms for the solution of the above optimization problems are proposed: they are proved to lead the agents to the desired solution, and their performance is studied. The mathematical tools required for the analysis are novel, or need to be used in a non-standard way. They are drawn from very different branches of pure and applied mathematics: spectral graph theory, Markov chains, combinatorics, linear algebra, set-valued analysis, convex and discrete geometry, topology of hyper-spaces of sets.
@cite_5: A method for manufacturing billets intended to be subsequently machined into a desired shape by plastic deformation, as by rolling, includes the heating to a predetermined bonding temperature of powder grains enclosed in a capsule, and subjecting the capsule at the bonding temperature to a high pressure sufficient to bond the powder grains together to form a substantially solid body. The capsule is inserted at the bonding temperature into an over-sized forming cavity of a press which includes relatively movable punches, the capsule being completely surrounded within the press by a layer of heat-insulating and pressure-transmitting solid material, such as talc or the like. Thus, when the capsule is subjected to the high pressure upon operation of the press, such material serves as a pressure-transmitting medium through which pressure is applied completely against all sides of the capsule.
@cite_15: The task of balancing dynamically generated work load occurs in a wide range of parallel and distributed applications. Diffusion based schemes, which belong to the class of nearest neighbor load balancing algorithms, are a popular way to address this problem. Originally created to equalize the amount of arbitrarily divisible load among the nodes of a static and homogeneous network, they have been generalized to heterogeneous topologies. Additionally, some simple diffusion algorithms have been adapted to work in dynamic networks as well. However, if the load is not divisible arbitrarily but consists of indivisible unit size tokens, diffusion schemes are not able to balance the load properly. In this paper we consider the problem of balancing indivisible unit size tokens on heterogeneous systems. By modifying a randomized strategy invented for homogeneous systems, we can achieve an asymptotically minimal expected overload in l1, l2 and l1 norm while only slightly increasing the run-time by a logarithmic factor. Our experiments show that this additional factor is usually not required in applications.
@cite_16: In the average consensus a set of linear systems has to be driven to the same final state, which corresponds to the average of their initial states. This mathematical problem can be seen as the simplest example of coordination task. In fact it can be used to model both the control of multiple autonomous vehicles which all have to be driven to the centroid of the initial positions, and to model the decentralized estimation of a quantity from multiple measure coming from distributed sensors. This contribution presents a consensus strategy in which the systems can exchange information among themselves according to a fixed strongly connected digital communication network. Beside the decentralized computational aspects induced by the choice of the communication network, we here have also to face the quantization effects due to the digital links. We here present and discuss two different encoding decoding strategies with theoretical and simulation results on their performance. Copyright © 2009 John Wiley & Sons, Ltd.
@cite_10: In this note we study the average consensus algorithm in a distributed system of agents which are allowed to communicate according to a directed graph. Moreover, the communication between connected agents is not perfect, but affected by some error, which can be either a random additive noise or produced by a quantization. We investigate the effects of these constraints on the performance of the average consensus algorithms.
@cite_11: 
The constraint of quantization of messages, or of states, has been considered in several recent papers @cite_8 @cite_15 @cite_10 @cite_9 @cite_11 @cite_5 @cite_4 @cite_0 . However, existing algorithms in the literature are not able to achieve average consensus with arbitrary precision, with the notable exception of @cite_16 , which uses logarithmic quantizers, together with a coding scheme similar to the one in the present paper. The zooming-in zooming-out algorithm and the main convergence result of this paper appeared, in slightly different version, in @cite_17 and in the thesis @cite_2 . Note that recently @cite_3 a modification of the present algorithm has been proved to converge under a different condition.