Estimating Aggregates on a Peer-to-Peer Network

Abstract

As Peer-to-Peer (P2P) networks become popular, there is an emerging need to collect a variety of statistical summary information about the participating nodes. The P2P networks of today lack mechanisms to compute even such basic aggregates as min, max, sum, count or avg. In this paper, we define and study the NodeAggregation problem that is concerned with aggregating data stored at nodes in the network. We present generic schemes that can be used to compute any of the basic aggregation functions accurately and robustly. Our schemes can be used as building blocks for tools to collect statistics on network topology, user behavior and other node characteristics.