Broadcast Gossip Algorithms: Design and Analysis for Consensus

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.