Algorithm for Networked Peer-to-Peer Systems

点击翻译按钮获取中文摘要

A Peer-to-peer networked system is a collaborating group of Internet nodes which overlay their own special-purpose network on top of the Internet. Such a system performs its own application-level routing on top of IP routing. These systems share some of the same characteristics as the Internet in that they can grow to be quite large, need to utilize distributed control and configuration, employ a naming scheme that allows them to address a node without knowing its exact whereabouts, and possess a routing mechanism that allows each node to meaningfully communicate with the rest of the system. Typically a peer-to-peer network performs a very specific purpose such as distributed data storage, cache replication, multicasting etc. and uses normal Internet functionality for all other purposes. These systems are diverse enough that it would not be desirable to make modifications to the IP routing/naming protocols to support each instance of such a system.Peer-to-peer systems such as Napster and Gnutella have, of late, received a fair amount ofattention in the non-technical literature. More importantly, several research groups have recentlydesigned a variety of peer-to-peer systems as infrastructure for flexibly evolving the Internet, forlarge-scale network storage, for anonymous publishing, and for application-level multicasting. Atthe core of many of these systems lie innovative and novel distributed algorithms for disseminatingcontent. The principal investigators classify these systems into structured systems where there isglobal consensus on where a document is stored, and unstructured systems where no such consensus exists.Peer-to-peer systems have a rich theoretical structure, and sophisticated algorithmic techniqueshave been employed in the systems currently under development. In preliminary work, the princi-pal investigators use the small-world model to improve the performance of a specific unstructuredsystem called Freenet. Motivated by their preliminary work, this proposal plans to take a principledlook at the properties of various algorithms proposed in the peer-to-peer literature. Some of thespecific questions that the principal investigators intend to address are understanding the funda-mental bounds on the performance of peer-to-peer systems, designing algorithms that allow thesesystems to perform at peak availability and minimum latency, studying the impact of topology andcaching on latency, and understanding the role that the small-world model might play in improvingthe performance of these systems.The overall attention that the peer-to-peer technology has garnered in the recent past, and thevarious proposed businesses based on this model, point to the potential broad impact that this work can have. The principal investigators hope that this work will provide the systems community with the theoretical tools necessary to rigorously understand the behavior of some of their designs as well as rules of thumb to choose between alternative architectures, protocols, and algorithms.The principal investigators intend to integrate some of this material into a graduate courseon \Algorithmic Issues in Communication Networks". Their classroom treatment of these topicswill be formal, but with clearly indicated motivations from and applications to real systems. Thelecture notes and course projects developed by the principal investigators will be made publiclyavailable.