Communication Complexity and Energy Efficient Consensus Algorithm

In this paper, we analyze distributed average consensus algorithms, both deterministic and gossip based, with respect to a new metric related to the energy cost of communication among agents. We first introduce a new notion of communication complexity as a metric to assess the energy efficiency properties of consensus algorithms. We provide explicit formulas to compute the communication complexity of deterministic algorithms and gossip based algorithms depending on different stopping criteria. We also show that the gossip based algorithms have less communication complexity than the deterministic counterparts under mild conditions, usually satisfied by a large number of networks. We also show that the gossip algorithm with minimum communication complexity can be effectively computed as the solution of a convex optimization problem.