Estimating the Size of a Chord-based P2P System at Run Time

Andreas Binzenhöfer

The Chord system is a decentralized peer-to-peer mechanism designed to store and search key/value pairs. The peers in a Chord overlay network are represented on a circle, whereas each peer has to maintain log(n) neighbors to guarantee a stable overlay structure in the presence of high churn rates. A single peer, however, does not know the current size n of the Chord ring. In this talk we introduce an estimator for the current size of the Chord ring based on local information like a peer's neighbor- and fingerlists. We also show how to calculate the corresponding confidence intervals to minimize the probability to over- or underestimate the current size of the overlay.