HOME / PUBLICATIONS /

Self-Organization in Peer-to-Peer Systems

Citation:

Ledlie, Jonathan, Jacob M. Taylor, Laura Serban, and Margo Seltzer. 2002. “Self-Organization in Peer-to-Peer Systems.” Tenth ACM SIGOPS European Workshop. Copy at http://www.tinyurl.com/y4fqtdlt

Date Presented:

September 2002

Abstract:

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 [lv02gnutella]. We evaluate two systems based on these criteria: Chord [stoica01chord] and a heterogeneous-node hierarchical grouping scheme [ledlie02namequeries]. The former gives a greater than 1 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.

  • [lv02gnutella] Qin Lv, Sylvia Ratnasamy, Scott Shenker: Can Heterogeneity Make Gnutella Scalable?, Proceedings of the First International Workshop on Peer-to-Peer Systems (IPTPS 2002), Cambridge, MA, March 2002.
  • [stoica01chord] Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, Hari Balakrishnan: Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications, Proceedings of the ACM SIGCOMM 2001 Conference, August 2001.
  • [ledlie02namequeries] Jonathan Ledlie, Laura Serban, and Dafina Toncheva: Scaling Filename Queries in a Large-Scale Distributed File System, Harvard University Technical Report TR-03-02, January 2002.

Website