Algorithm for Networked Peer-to-Peer Systems

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

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.