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}
}