Algorithm for Networked Peer-to-Peer Systems

对等网络系统是一组相互协作的互联网节点，它们将自己的专用网络覆盖在互联网之上。这样的系统在IP路由的基础上执行其自己的应用级路由。这些系统与互联网有一些相同的特征，因为它们可以增长到相当大，需要利用分布式控制和配置，采用允许它们在不知道节点确切位置的情况下对节点进行寻址的命名方案，并且拥有允许每个节点与系统的其余部分进行有意义通信的路由机制。通常，对等网络执行非常特定的目的，例如分布式数据存储、高速缓存复制、多播等，并将正常的互联网功能用于所有其他目的。这些系统足够多样化，不希望为了支持这种系统的每个实例而修改IP路由/命名协议。例如Napster和Gnutella的对等系统最近在非技术文献中得到了相当多的关注。更重要的是，几个研究小组最近设计了各种对等系统，作为灵活发展互联网、大规模网络存储、匿名发布和应用层多播的基础设施。其中许多系统的核心是用于传播内容的创新和新颖的分布式算法。主要研究人员将这些系统分为结构化系统和非结构化系统，在结构化系统中，对文件的存储位置存在全球共识，而在非结构化系统中，不存在这种共识。对等系统具有丰富的理论结构，目前正在开发的系统中采用了复杂的算法技术。在前期工作中，主要研究人员使用小世界模型来改进称为Freenet的特定非结构化系统的性能。在他们初步工作的激励下，该提案计划原则性地研究对等文献中提出的各种算法的特性。主要研究人员打算解决的一些具体问题是理解对等系统性能的基本界限，设计允许系统在最高可用性和最小延迟下执行的算法，研究拓扑和缓存对延迟的影响，以及了解小世界模型在改善这些系统性能方面可能扮演的角色。对等技术最近获得的总体关注，以及基于该模型的各种拟议业务，表明了这项工作可能具有的潜在广泛影响。主要研究人员希望这项工作将为系统社区提供必要的理论工具，以严格理解他们的一些设计的行为，以及在可选的体系结构、协议和算法之间进行选择的经验规则。主要研究人员打算将这些材料中的一些整合到一门研究生课程--《通信网络中的算法问题》。他们对这些主题的课堂处理将是正式的，但有明确的动机来自真实的系统和应用于实际系统。主要研究人员开发的课程笔记和课程项目将公开提供。

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.