Computing Aggregate Funtions on Large-Scale Distributed Systems

Aggregation refers to a set of functions that provide global information about a distributed system. These functions operate on numeric values distributed over the system and can be used to determine extremal values and compute averages, products or sums. Aggregation is an important basic functionality for peer-to-peer systems: for example, distributed storage systems may need to know the total free space available; load-balancing protocols may benefit from knowing the target average load so as to minimize the transfered load.
Building on the simple but efficient idea of anti-entropy aggregation we introduce practically applicable robust and adaptive protocols for proactive average aggregation. We show how the averaging protocol can be applied to compute further aggregates like sum, variance and the network size.
We present theoretical and empirical evidence supporting the robustness of the averaging protocol under different scenarios.