Peer-to-Peer Systems

Attendees were welcomed to the Workshop by Frans Kaashoek and Peter Druschel who reported that although the original plan had been to invite 35 people to a 1 1/2 day event, 99 papers had been submitted. The workshop had therefore been scaled up to 50 authors with 32 position papers, 26 of which would be presented over a two day program.

A fundamental theoretical challenge in peer-to-peer systems is proving statements about the evolution of the system while nodes are continuously joining and leaving. Because the system will operate for an infinite time, performance measures based on runtime are uninformative; instead, we must study the rate at which nodes consume resources in order to maintain the system state.This “maintenance bandwidth” depends on the rate at which nodes tend to enter and leave the system. In this paper, we formalize this dependence. Having done so, we analyze the Chord peer-to-peer protocol. We show that Chord’s maintenance bandwidth to handle concurrent node arrivals and departures is near optimal, exceeding the lower bound by only a logarithmic factor. We also outline and analyze an algorithm that converges to a correct routing state from an arbitrary initial condition.

Recent work such as Tapestry, Pastry, Chord and CAN provide efficient location utilities in the form of overlay infrastructures. These systems treat nodes as if they possessed uniform resources, such as network bandwidth and connectivity. In this paper, we propose a systemic design for a secondaryoverlay of super-nodes which can be used to deliver messages directly to the destination’s local network, thus improving route efficiency. We demonstrate the potential performance benefits by proposing a name mapping scheme for a Tapestry-Tapestry secondary overlay, and show preliminary simulation results demonstrating significant routing performance improvement.

Even though they were introduced only a few years ago, peer-to-peer (P2P) filesharing systems are now one of the most popular Internet applications and have become a major source of Internet traffic. Thus, it is extremely important that these systems be scalable. Unfortunately, the initial designs for P2P systems have significant scaling problems; for example, Napster has a centralized directory service, and Gnutella employs a flooding based search mechanism that is not suitable for large systems.

We describe a peer-to-peer distributed hash table with provable consistency and performance in a fault-prone environment. Our system routes queries and locates nodes using a novel XOR-based metric topology that simplifies the algorithm and facilitates our proof. The topology has the property that every message exchanged conveys or reinforces useful contact information. The system exploits this information to send parallel, asynchronous query messages that tolerate node failures without imposing timeout delays on users.

Two main approaches have been taken for distributed keyvalue lookup operations in peer-to-peer systems: broadcast searches [1], [2] and location-deterministic algorithms [5], [6], [7], [9]. We describe a third alternative based on a distributed trie. This algorithm functions well in a very dynamic, hostile environment, offering security benefits over prior proposals. Our approach takes advantage of working-set temporal locality and global key/value distribution skews due to content popularity. Peers gradually learn system state during lookups, receiving the sought values and/or internal information used by the trie. The distributed trie converges to an accurate network map over time. We describe several modes of information piggybacking, and conservative and liberal variants of the basic algorithm for adversarial settings. Simulations show efficient lookups and low failure rates.

The key principles behind current peer-to-peer research include fully distributing service functionality among all nodes participating in the system and routing individual requests based on a small amount of locally maintained state. The goals extend much further than just improving rawsy stem performance: such systems must survive massive concurrent failures, denial of service attacks, etc. These efforts are uncovering fundamental issues in the design and deployment of distributed services. However, the work ignores a number of practical issues with the deployment of general peer-to-peer systems, including i) the overhead of maintaining consistency among peers replicating mutable data and ii) the resource waste incurred by the replication necessary to counteract the loss in locality that results from random content distribution. We argue that the key challenge in peer-to-peer research is not to distribute service functions among all participants, but rather to distribute functions to meet target levels of availability, survivability, and performance. In many cases, only a subset of participating hosts should take on server roles. The benefit of peer-to-peer architectures then comes from massive diversity rather than massive decentralization: with high probability, there is always some node available to provide the required functionality should the need arise.

Despite recent excitement generated by the peer-to-peer (P2P) paradigm and the surprisingly rapid deployment of some P2P applications, there are few quantitative evaluations of P2P systems behavior. The open architecture, achieved scale, and self-organizing structure of the Gnutella network make it an interesting P2P architecture to study. Like most other P2P applications, Gnutella builds, at the application level, a virtual network with its own routing mechanisms. The topology of this overlay network and the routing mechanisms used have a significant influence on application properties such as performance, reliability, and scalability. We describe techniques to discover and analyze the Gnutella’s overlay network topology and evaluate generated network traffic. Our major findings are: (1) although Gnutella is not a pure power-law network, its current configuration has the benefits and drawbacks of a power-law structure, (2) we estimate the aggregated volume of generated traffic, and (3) the Gnutella virtual network topology does not match well the underlying Internet topology, hence leading to ineffective use of the physical networking infrastructure. We believe that our findings as well as our measurement and analysis techniques have broad applicability to P2P systems and provide useful insights into P2P system design tradeoffs.

Even though recent research has identified many different uses for peer-to-peer (P2P) architectures, file sharing remains the dominant (by far) P2P application on the Internet. Despite various legal problems, the number of users participating in these file-sharing systems, and number of files transferred, continues to grow at a remarkable pace. Filesharing applications are thus becoming an increasingly important feature of the Internet landscape and, as such, the scalability of these P2P systems is of paramount concern. While the peer-to-peer nature of data storage and data transfer in these systems is inherently scalable, the scalability of file location and query resolution is much more problematic.

“Mojo Nation” was a network for robust, decentralized file storage and transfer. It was first released to the public in July, 2000, and remained in continuous operation until February, 2002. Over 100,000 people downloaded and used the Mojo Nation software. We observe some surprising and problematic behavior of the users as a group. We describe several specific problems in the design of Mojo Nation, some of which appear to be soluble with simple practical improvements, and others of which are not yet addressed in the literature, suggesting opportunities for further research.

In this paper we propose a new Peer-to-Peer architecture for a censorship resistant system with user, server and active-server document anonymity as well as efficient document retrieval. The retrieval service is layered on top of an existing Peer-to-Peer infrastructure, which should facilitate its implementation. The key idea is to separate the role of document storers from the machines visible to the users, which makes each individual part of the system less prone to attacks, and therefore to censorship.

We introduce Tarzan, a peer-to-peer anonymous network layer that provides generic IP forwarding. Unlike prior anonymizing layers, Tarzan is flexible, transparent, decentralized, and highly scalable. Tarzan achieves these properties by building anonymous IP tunnels between an open-ended set of peers. Tarzan can provide anonymity to existing applications, such as web browsing and file sharing, without change to those applications. Performance tests show that Tarzan imposes minimal overhead over a corresponding non-anonymous overlay route.

We present the design of Mnemosyne1, a peer-to-peer steganographic storage service. Mnemosyne provides a high level of privacy and plausible deniability by using a large amount of shared distributed storage to hide data. Blocks are dispersed by secure hashing, and loss codes used for resiliency. We discuss the design of the system, and the challenges posed by traffic analysis.

We present ConChord, a large-scale certificate distribution system built on a peer-to-peer distributed hash table. ConChord provides load-balanced storage while eliminating many of the administrative difficulties of traditional, hierarchical server architectures. ConChord is specifically designed to support SDSI, a fully-decentralized public key infrastructure that allows principals to define local names and link their namespaces to delegate trust. We discuss the particular challenges ConChord must address to support SDSI efficiently, and we present novel algorithms and distributed data structures to address them. Experiments show that our techniques are effiective and practical for large SDSI name hierarchies.

The current domain name system (DNS) couples ownership of domains with the responsibility of serving data for them. The DNS security extensions (DNSSEC) allow verificaton of records obtained by alternate means, opening exploration of alternative storage systems for DNS records. We explore one such alternative using DHash, a peer-to- peer distributed hash table built on top of Chord. Our system inherits Chord’s fault-tolerance and load balance properties, at the same time eliminating many administrative problems with the current DNS. Still, our system has significantly higher latencies and other disadvantages in comparison with conventional DNS. We use this comparison to draw conclusions about general issues that still need to be addressed in peer- to-peer systems and distributed hash tables in particular.

Real-time network measurements can be used to improve performance of existing Internet services and support the deployment of new services dependent on performance information (e.g., topologicallyaware overlay networks). Internet-wide measurement faces numerous scaling-related challenges, including the problem of deploying enough measurement endpoints for wide-spread coverage. We observe that peerto- peer networks, made up of “volunteer” hosts around the Internet world, have the potential to provide a level of coverage that greatly exceeds that made possible with the tedious human process of negotiating endpoint locations. We therefore propose a distributed peer-to-peer system that can be queried for network performance information. We sketch the architecture and operation of such a system and briefly relate it to alternative proposals for measurement infrastructures. Finally, we list open problems related to the design and realization of such a system.

In this paper, we make the case for Cooperative Networking (CoopNet) where end-hosts cooperate to improve network performance perceived by all. In CoopNet, cooperation among peers complements traditional client-server communication rather than replacing it.W e focus on the Web flash crowd problem and argue that CoopNet offers an effective solution. We present an evaluation of the CoopNet approach using simulations driven by traffic traces gathered at the MSNBC website during the flash crowd that occurred on September 11, 2001.

This paper argues for an Internet Indirection Infrastructure that replaces the point-to-point communication abstraction of today’s Internet with a rendezvous-based communication abstraction: instead of explicitly sending a packet to a destination, each packet is associated an identifier, which is then used by the receiver to get the packet. This level of indirection decouples the sender and the receiver behaviors, and allows us to efficiently support basic communication services such as multicast, anycast and mobility in the Internet. To demonstrate the feasibility of this approach, we are currently designing and building an overlay network solution based on the Chord lookup system.

Flash crowds can cripple a webs ite’s performance. Since they are infrequent and unpredictable, these floods do not justify the cost of traditional commercial solutions. We describe Backslash, a collaborative webmirroring system run by a collective of websites that wish to protect themselves from flash crowds. Backslash is built on a distributed hash table overlay and uses the structure of the overlay to cache aggressively a resource that experiences an uncharacteristically high request load. By redirecting requests for that resource uniformly to the created caches, Backslash helps alleviate the effects of flash crowds. We explore cache diffusion techniques for use in such a system and find that probabilistic forwarding improves load distribution albeit not dramatically.

Despite the existence of many peer-to-peer systems, some of their design choices and implications are not well understood. This paper compares several distributed and peer-to-peer systems by evaluating a key set of architectural decisions: naming, addressing, routing, topology, and name lookup. Using the World Wide Web, Triad, and Chord/CFS as examples, we illustrate how different architectural choices impact availability, redundancy, security, and fault-tolerance.

The majority of recent high-profile work in peer-to-peer networks has approached the problem of location by abstracting over object lookup services. Namespace virtualization in the overlay layer provides load balance and provable bounds on latency at low costs.We contend that namespace virtualization comes at a significant cost for applications that naturally describe their data sets in a hierarchical manner. Opportunities for enhancing browsing, prefetching and efficient attribute-based searches are lost. A hierarchy exposes relationships between items near to each other in the topology; virtualization of the namespace discards this information even if present at client, higherlevel protocols.We advocate encoding application hierarchies directly into the structure of the overlay network, and revisit this argument through a newly proposed distributed directory service.

Data-sharing scientific collaborations have particular characteristics, potentially different from the current peer-to-peer environments. In this paper we advocate the benefits of exploiting emergent patterns in self-configuring networks specialized for scientific data-sharing collaborations. We speculate that a peer-to-peer scientific collaboration network will exhibit small-world topology, as do a large number of social networks for which the same pattern has been documented. We propose a solution for locating data in decentralized, scientific, data-sharing environments that exploits the small-worlds topology. The research challenge we raise is: what protocols should be used to allow a self-configuring peer-to-peer network to form small worlds similar to the way in which the humans that use the network do in their social interactions?

Recently a new generation of P2P systems, offering distributed hash table (DHT) functionality, have been proposed. These systems greatly improve the scalability and exact-match accuracy of P2P systems, but offer only the exact-match query facility. This paper outlines a research agenda for building complex query facilities on top of these DHT-based P2P systems. We describe the issues involved and outline our research plan and current status.

Large-scale peer-to-peer systems face security threats from faulty or hostile remote computing elements. To resist these threats, many such systems employ redundancy. However, if a single faulty entity can present multiple identities, it can control a substantial fraction of the system, thereby undermining this redundancy. One approach to preventing these “Sybil attacks” is to have a trusted agency certify identities. This paper shows that, without a logically centralized authority, Sybil attacks are always possible except under extreme and unrealistic assumptions of resource parity and coordination among entities.

Recent peer-to-peer research has focused on providing efficient hash lookup systems that can be used to build more complex systems. These systems hav good properties when their algorithms are executed correctly but have not generally considered how to handle misbehaving nodes. This paper looks at what sorts of security problems are inherent in large peer-to-peer systems based on distributed hash lookup systems. We examin the types of problems that such systems might face, drawing examples from existing systems, and propose some design principles for detecting and preventing these problems.

We describe a content addressable network which is robust in the face of massive adversarial attacks and in a highly dynamic environment. Our network is robust in the sense that at any time, an arbitrarily large fraction of the peers can reach an arbitrarily large fraction of the data items. The network can be created and maintained in a completely distributed fashion.

Astrolabe is a new kind of peer-to-peer system implementing a hierarchical distributed database abstraction. Although deigned for scalable management and data mining, the system can also support wide-area multicast and offers powerful aggregation mechanisms that permit applications to build customized virtual databases by extracting and summarizing data located throughout a large network. In contrast to other peer-to-peer systems, the Astrolabe hierarchy is purely an abstraction constructed by running our protocol on the participating hosts - there are no servers, and the system doesn’t superimpose a specialized routing infrastructure or employ a DHT. This paper focuses on wide-area implementation challenges.

While recent proposals for distributed hashtables address the crucial issues of communication efficiency and load balancing in dynamic networks,they do not guarantee strong semantic on concurrent data accesses. While it is well known that guaranteeing availability and consistency in an asynchronou and failure prone network is impossible, we believe that guaranteeing atomic semantics is crucial for establishing DHT a a robust middleware service. In this paper, we describe a simple DHT algorithm that maintain the atomicity property regardless of timing, failures, or concurrency in the system. The livene of the algorithm, while not dependent on the order of operation in the system, requires that node failures do not occur and that the network eventually delivers all messages to intended recipients. We outline how state machine replication technique can be used to approximate these requirements even in failure-prone network,and examine the merit of placing the responsibility for fault-tolerance and reliable delivery below the level of the DHT algorithm.

In this paper, we propose the dissemination tree, a dynamic content distribution system built on top of a peer-to-peer location service. We present a replica placement protocol that builds the tree while meeting QoS and server capacity constraints. The number of replicas as well as the delay and bandwidth consumption for update propagation are significantly reduced. Simulation results show that the dissemination tree has close to the optimal number of replicas, good load distribution, small delay and bandwidth penalties for update multicast compared with the ideal case: static replica placement on IP multicast.

Peer-to-peer architectures can be used to build a robust, fault tolerant infrastructure for important services. One example is a peer-to-peer data replication system, in which digital collections are protected from failure by being replicated at multiple peers. We argue that such community-based redundancy, in which multiple sites contribute resources to build a fault-tolerant system, is an important application of peer-to-peer networking. In such a system, there must be flexible, effective techniques for managing resource allocation. We propose data trading, a mechanism where a site acquires remote resources in the community by trading away its own local resources. We discuss the application of data trading to the data replication problem, and examine other applications of trading. A general trading infrastructure is a valuable part of a peer-to-peer, community-based redundancy system.

Peer-to-peer systems are positioned to take advantage of gains in network bandwidth, storage capacity, and computational resources to provide long-term durable storage infrastructures. In this paper, we quantitatively compare building a distributed storage infrastructure that is self-repairing and resilient to faults using either a replicated system or an erasure-resilient system. We show that systems employing erasure codes have mean time to failures many orders of magnitude higher than replicated systems with similar storage and bandwidth requirements. More importantly, erasure-resilient systems use an order of magnitude less bandwidth and storage to provide similar system durability as replicated systems.