Jonathan Ledlie, Jacob M. Taylor, Laura Serban, Margo
Seltzer
Division of Engineering and Applied Science
Harvard University
In Proceedings of SIGOPS 2002
This paper addresses the problem of forming groups in
peer-to-peer (P2P) systems and examines what dependability means in
decentralized distributed systems. Much of the literature in this
field assumes that the participants form a local picture of global
state, yet little research has been done discussing how this state
remains stable as nodes enter and leave the system. We assume that
nodes remain in the system long enough to benefit from retaining
state, but not sufficiently long that the dynamic nature of the
problem can be ignored.
We look at the components that describe a system's dependability and
argue that next-generation decentralized systems must explicitly
delineate the information dispersal mechanisms (
e.g., probe,
event-driven, broadcast), the capabilities assumed about constituent
nodes (bandwidth, uptime, re-entry distributions), and distribution of
information demands (needles in a haystack
vs. hay in a haystack
[
13]).
We evaluate two systems based on these criteria: Chord
[
22] and a heterogeneous-node hierarchical grouping
scheme [
11]. The former gives a
failed
request rate under normal P2P conditions and a prototype of the latter
a similar rate under more strenuous conditions with an order of magnitude more organizational messages. This analysis suggests several methods to greatly improve the prototype.
