Threshold phenomenon for average consensus

In this paper, our main concern is to study the influence of the number of edges on the convergence rate and the total communication cost in distributed average consensus problems. We begin with the case of regular networks, i.e. networks for which the associated graph (vertices corresponding to sensors and edges being defined by communicating sensor pairs) has the same vertex degree for all vertices. In regular graphs, the number of edges is effectively determined by the common vertex degree. Therefore the problem is converted to one of analyzing the influence of the common vertex degree on the convergence rate and total communication cost. To evaluate the convergence rate we use the ratio of two eigenvalues of the Laplacian matrix of the graph, for which we obtain lower and upper bounds in terms of the common vertex degree. Using the bounds, we can illustrate the intuitively reasonable property that the convergence rate will increase with increase in the common vertex degree. However the increment in the convergence rate drops dramatically as the common vertex degree becomes progressively large. At the same time the total communication cost of the consensus process will become large. Based on these two observations we define a type of 'Magic Number' to help analyze the value or otherwise of adding more links to the network. The Monte Carlo simulation results are consistent with the theoretical analysis and demonstrate the existence of the magic number. Further we present the simulation results on irregular graphs in which the degree distribution is subject to a Poisson distribution. From the simulation results we observe that the magic number also exists in the irregular graphs. In general the magic number for irregular graphs is larger than the one for regular graphs.