Mike Rabbat pointed out his new preprint on ArXiv:

Broadcast Gossip Algorithms for Consensus on Strongly Connected Digraphs
Wu Shaochuan, Michael G. Rabbat

The basic starting point is the unidirectional Broadcast Gossip algorithm — we have nodes in a graph and each node starts with a value . At each time, a random node broadcasts its value to its neighbors in the graph and they each update their value with the weighted average of their current value and the received value. Eventually, this process converges almost surely and all nodes will have a common value . However, in general , where , but . So this process achieves consensus but only computes the average in expectation.

The reason broadcast gossip does’t compute the average is pretty clear — since the communication and updates are unidirectional, the average of the nodes’ values changes over time. One way around this is to use companion variables to track the effect of the broadcast. These have been studied before, but in this paper they set the initial values and perform updates as follows : if node broadcasts at time and node is a neighbor, then

So what’s going on here? Each time a node transmits it resets its companion variable to . Each time it receives a broadcast it accumulates an offset in . The actual value estimate at the nodes is weighted average of the current and received value plus some of the local offset.

The parameters of the algorithm are matrices and and per-node matrices . Let

When node broadcasts) we can write a matrix

such that

where if node broadcasts at time $t$.

The main results are:

1. If we choose small enough, then and under more conditions.
2. A sufficient condition for the second moment of the error to go to 0.
3. Rules on how to pick the parameters, especially .

There are also some nice simulations. Broadcast gossip is nice because of its simplicity, and adding a little monitoring/control variable seems to buy a lot in terms of controlling bad sample paths for the process.