Gossiping in groups: Distributed averaging over the wireless medium

We present an approach to gossip algorithms tailored to the practical considerations of wireless communications. Traditional gossip algorithms operate via the pairwise exchange of estimates, which fails to capture the broadcast and superposition nature of the wireless medium. Adapting the virtual full-duplex framework of Guo and Zhang, we construct a communications scheme in which each node can broadcast its estimate to its neighbors while simultaneously receiving its neighbors' estimates. This full-duplex scheme gives rise to group gossip, a more flexible family of gossip algorithms built on multilateral, rather than pairwise, exchanges. Our approach obviates the need for orthogonalization or medium access; only local information and synchronization are necessary. Additionally, group gossip has better convergence properties than does randomized gossip. Group gossip permits a tighter bound on the convergence speed than randomized gossip, and in general the upper bound on the convergence time is at most one-third that of randomized gossip.