Abstract
Aggregation is the process of gathering and combining information from a number of sources. In peer-to-peer systems, aggregation is a basic component of a range of applications, including monitoring and complex-query resolution. Peer-to-peer aggregation services themselves are dependent on a number of other fundamental peer-to-peer services - directories, multicasting and system-size approximation. The overall performance characteristics of an aggregation service are affected by the chosen implementation method for these underlying services. To illustrate this relationship, aggregation techniques for internet-based peer-to-peer systems are surveyed and dissected into their component parts. We further consider the problem of running one-off aggregation queries in a peer-to-peer network. A new aggregation service, Bliksum, which uses a novel combination of underlying services, is introduced. Bliksum employs unstructured peer-to-peer techniques for node sampling, multicasting and system-size approximation, in combination with a method of building a temporary tree structure for aggregation itself. Unstructured peer-to-peer techniques have been shown to be highly resilient to node churn, avoiding the problem inherent in structured systems of maintaining the desired structure when the set of nodes changes rapidly. We present experiments showing that Bliksum retains these advantages while reducing communications cost and reducing information loss compared to pure gossip-based aggregation.