Push-Sum

Kempe-Dobra-Gehrke gossip primitive: each node forwards half its (sum, weight) pair to a random peer; ratios converge exponentially to the network average while conserving mass.

In this vault

Backlinks

Summary

The paper presents a proactive, gossip-based protocol for continuously computing aggregate functions (averages, sums, counts, variances, network size, extremal values) over huge dynamic networks such as P2P and grid systems. Each node periodically picks a random neighbor and performs a push-pull exchange; pairwise averaging drives the variance of estimates to zero at a geometric rate while preserving the global mean (“mass conservation”). All nodes thus converge to the correct aggregate and adaptively track changes over time.

Beyond core averaging, the authors show how to compute more complex aggregates (variance, network size via a single seed) and evaluate robustness under node churn and message loss, including a PlanetLab deployment. The protocol is attractive because it is simple, scalable, lightweight, and requires no centralized infrastructure — only a peer-sampling service.

Key Ideas

Push-pull averaging: w_p, w_q ← (w_p + w_q)/2 drives variance to zero exponentially.

Mass conservation preserves global sum so global average remains unchanged.

Reactive vs. proactive aggregation; this work targets proactive, always-on aggregates.

Robustness to dynamism, churn, and message loss.

Underlying assumption: a peer-sampling service supplies uniform random neighbors.

Conceptual Contribution

Claim: A simple push-pull averaging gossip protocol — paired with a peer-sampling service — provides proactive, continuously-updated aggregates (average, sum, count, variance, network size, extrema) at large scale with geometric-rate convergence and robustness to churn and message loss.

Mechanism: Each node periodically picks a random neighbour via getNeighbor(), exchanges local estimate, and replaces both with their average; variance analysis as iterative reduction gives convergence factor independent of network size; adaptive restart mechanism handles dynamism; PlanetLab deployment validates the theory.

Concepts introduced/used: Push-Pull Gossip, Proactive Aggregation, Peer Sampling Service, Variance Reduction, Mass Conservation, Convergence Factor, Adaptive Protocols

Stance: engineering / empirical with formal analysis

Relates to: Practical complement to the theoretical Gossip-Based Computation of Aggregate Information (Push-Sum); cited as a canonical aggregation example in Gossiping in Distributed Systems; the peer-sampling substrate it assumes is the same used by Myconet Fungi Inspired Superpeer Overlay and other bio-inspired overlays.

Summary

This paper analyzes simple gossip protocols (epidemic-style, randomized pairwise exchanges) for computing aggregate functions — sums, averages, quantiles, random samples — over values held by nodes in highly dynamic distributed systems like P2P networks and sensor networks. The key contribution is the Push-Sum protocol, which distributes weight alongside value so that the ratio stored at each node converges exponentially fast to the true average, even in the face of node failures and message loss.

The second contribution is a precise diffusion speed formalism linking protocol convergence to random walk / Markov chain mixing times, letting the authors analyze uniform gossip, flooding, and other mechanisms uniformly. Push-Sum converges in O(log n + log 1/ε + log 1/δ) rounds with exponentially small message sizes, making it suitable for massive, volatile networks.

Key Ideas

Push-Sum: maintain (value, weight) pairs, exchange halves with random peer; ratio converges to global average.

Mass conservation invariant underlies correctness.

Diffusion speed = convergence rate, mapped to Markov chain mixing times.

Robust to node/link failures — degraded guarantee scales with 1/(1-µ)^2.

Extends to sums, quantiles, random samples, and arbitrary linear syntactic aggregates.

Conceptual Contribution

Claim: Aggregates (sums, averages, quantiles, random samples) over a massive, volatile network can be computed by simple gossip protocols that converge exponentially fast; a mass-conservation trick (Push-Sum) gives precise averages with only local pairwise exchange.

Mechanism: Introduces Push-Sum (each node maintains a (value, weight) pair and halves on exchange; ratio = average), generalises it to Push-Vector and Push-Synopses for linear synopses; defines diffusion speed connecting protocol convergence to random-walk mixing times on the communication graph; proves O(log n + log 1/ε + log 1/δ) convergence with robustness under message loss and node failure.

Concepts introduced/used: Push-Sum, Mass Conservation, Diffusion Speed, Uniform Gossip, Flooding, Push-Synopses, Random Walks on Graphs, Aggregate Functions

Stance: formal-semantic / foundational (for gossip-based distributed algorithms)

Relates to: Theoretical foundation for Gossip-based Aggregation in Large Dynamic Networks (which re-derives Push-Sum empirically as averaging) and underpins the aggregation primitives surveyed in Gossiping in Distributed Systems and Gossip Protocols; gossip training in Edge Intelligence Survey inherits this analysis.