Robust aggregation protocols for large-scale overlay networks

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 count network size, determine extremal values and compute averages, products or sums. Aggregation allows important basic functionality to be achieved in fully distributed and peer-to-peer networks. For example, in a monitoring application, some aggregate reaching a specific value may trigger the execution of certain operations; 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 (a scheme based on the anti-entropy epidemic communication model), in this paper we introduce practically applicable robust and adaptive protocols for proactive aggregation, including the calculation of average, product ...