This paper presents a framework for computing aggregate information in decentralized systems using gossip-based protocols. The authors analyze the convergence of simple gossip-based protocols for computing sums, averages, random samples, quantiles, and other aggregate functions. They show that these protocols converge exponentially fast to the true answer when using uniform gossip. The paper defines a precise notion of the speed with which a node's data diffuses through the network, which is central to the approximation guarantees for these problems. They analyze the diffusion speed of uniform gossip in the presence of node and link failures, as well as for flooding-based mechanisms. The latter expose interesting connections to random walks on graphs. The authors propose the Push-Sum protocol for computing sums or averages of values at the nodes of a network. This protocol maintains a sum and a weight for each node, and uses a random selection process to distribute information. They show that with high probability, the relative error in the approximation of the average drops to within ε in a logarithmic number of rounds. The paper also analyzes the diffusion speed of uniform gossip, showing that it is O(log n + log 1/ε + log 1/δ). This analysis is based on a potential function that measures the variance of the contributions. The authors show that the potential function decreases geometrically, leading to exponential convergence. The paper also considers the impact of faults on the diffusion speed of uniform gossip. They show that the diffusion speed in the presence of failures is bounded by a factor of (1 - μ)^2, where μ is the probability of message loss. The authors also consider the impact of flooding on the diffusion speed of uniform gossip. They show that the diffusion speed for flooding corresponds to the mixing time of a random walk on the network. This allows them to leverage a large body of literature on the convergence speed of Markov Chains and Random Walks for the analysis of their aggregate computation protocols. The paper also discusses practical considerations, such as the ability to stop processing a query once the approximation guarantee is good enough, and the ability to handle frequently changing data in decentralized settings. The authors show that their protocols implement the Eventual Consistency paradigm. The paper concludes that the approach of using gossip-based protocols for computing aggregate information in decentralized systems is powerful and efficient, but also has limitations. The authors suggest that future research should focus on adapting the protocols to better suit different network topologies and communication mechanisms.This paper presents a framework for computing aggregate information in decentralized systems using gossip-based protocols. The authors analyze the convergence of simple gossip-based protocols for computing sums, averages, random samples, quantiles, and other aggregate functions. They show that these protocols converge exponentially fast to the true answer when using uniform gossip. The paper defines a precise notion of the speed with which a node's data diffuses through the network, which is central to the approximation guarantees for these problems. They analyze the diffusion speed of uniform gossip in the presence of node and link failures, as well as for flooding-based mechanisms. The latter expose interesting connections to random walks on graphs. The authors propose the Push-Sum protocol for computing sums or averages of values at the nodes of a network. This protocol maintains a sum and a weight for each node, and uses a random selection process to distribute information. They show that with high probability, the relative error in the approximation of the average drops to within ε in a logarithmic number of rounds. The paper also analyzes the diffusion speed of uniform gossip, showing that it is O(log n + log 1/ε + log 1/δ). This analysis is based on a potential function that measures the variance of the contributions. The authors show that the potential function decreases geometrically, leading to exponential convergence. The paper also considers the impact of faults on the diffusion speed of uniform gossip. They show that the diffusion speed in the presence of failures is bounded by a factor of (1 - μ)^2, where μ is the probability of message loss. The authors also consider the impact of flooding on the diffusion speed of uniform gossip. They show that the diffusion speed for flooding corresponds to the mixing time of a random walk on the network. This allows them to leverage a large body of literature on the convergence speed of Markov Chains and Random Walks for the analysis of their aggregate computation protocols. The paper also discusses practical considerations, such as the ability to stop processing a query once the approximation guarantee is good enough, and the ability to handle frequently changing data in decentralized settings. The authors show that their protocols implement the Eventual Consistency paradigm. The paper concludes that the approach of using gossip-based protocols for computing aggregate information in decentralized systems is powerful and efficient, but also has limitations. The authors suggest that future research should focus on adapting the protocols to better suit different network topologies and communication mechanisms.