An approach to massively distributed aggregate computing on peer-to-peer networks

The emergence of the Internet as a computing platform increases the demand for new classes of algorithms that combine massive distributed processing and complete de-centralization. Moreover, these algorithms should be able to execute in an environment that is heterogeneous, changes almost continuously, and consists of millions of nodes. An important class of algorithms that can play an important role in such environments is aggregate computing: comput-ing the aggregation of attributes such as extremal values, mean, and variance. These algorithms typically find their application in distributed data mining and systems manage-ment. We present novel, massively scalable and fully decen-tralized algorithms for computing aggregates, and substan-tiate our scalability claims through simulations and theo-retical analysis. 1