Analysis of the Evolution of Peer-to-Peer Systems

David Liben-Nowell, Hari Balakrishnan, David Karger
21st ACM Symposium on Principles of Distributed Computing (PODC), Monterey, CA, July 2002

In this paper, we give a theoretical analysis of peer-to-peer (P2P) networks operating in the face of concurrent joins and unexpected departures. We focus on Chord, a recently developed P2P system that implements a distributed hash table abstraction, and study the process by which Chord maintains its distributed state as nodes join and leave the system. We argue that traditional performance measures based on run-time are uninformative for a continually running P2P network, and that the rate at which nodes in the network need to participate to maintain system state is a more useful metric. We give a general lower bound on this rate for a network to remain connected, and prove that an appropriately modified version of Chord's maintenance rate is within a logarithmic factor of the optimum rate.

[PDF (188KB)] [PostScript (202KB)] [Gzipped PostScript (73KB)]

Bibtex Entry:

@inproceedings{liben-nowell2002analysis,
   author =       "David Liben-Nowell and Hari Balakrishnan and David Karger",
   title =        "{Analysis of the Evolution of Peer-to-Peer Systems}",
   booktitle =    {21st ACM Symposium on Principles of Distributed Computing (PODC)},
   year =         {2002},
   month =        {July},
   address =      {Monterey, CA}
}