Gossip Algorithms for Computing U-statistics

This manuscript studies two ‘randomized gossip’ algorithms for computing a U-statistic over a weighted, (un)directed graph. We propose algorithms U1-gossip and U2-gossip and derive exponential convergence to a global consensus. The proofs rely on a convergence result for Markov chains and on a probabilistic concentration inequality.