Sample Greedy Gossip for Distributed Network-Wide Average Computation
For distributed systems requiring efficient averaging, this work offers a flexible trade-off between communication overhead and convergence speed, but is incremental.
The paper proposes a greedy gossip algorithm for distributed network-wide averaging that balances communication cost and convergence performance via stochastic sampling, validated through simulations.
This paper investigates the problem of distributed network-wide averaging and proposes a new greedy gossip algorithm. Instead of finding the optimal path of each node in a greedy manner, the proposed approach utilises a suboptimal communication path by performing greedy selection among randomly selected active local nodes. Theoretical analysis on convergence speed is also performed to investigate the characteristics of the proposed algorithm. The main feature of the new algorithm is that it provides great flexibility and well balance between communication cost and convergence performance introduced by the stochastic sampling strategy. Extensive numerical simulations are performed to validate the analytic findings.