Peer-to-Peer Systems

✍ Scribed by Peter Druschel (editor), Frans Kaashoek (editor), Antony Rowstron (editor)

• Publisher: Springer
• Year: 2002
• Tongue: English
• Leaves: 348
• Category: Library

✦ Synopsis

Peer-to-peer has emerged as a promising new paradigm for large-scale distributed computing. The International Workshop on Peer-to-Peer Systems (IPTPS) aimed to provide a forum for researchers active in peer-to-peer computing to discuss the state of the art and to identify key research challenges. The goal of the workshop was to examine peer-to-peer technologies, appli- tions, and systems, and also to identify key research issues and challenges that lie ahead. In the context of this workshop, peer-to-peer systems were characterized as being decentralized, self-organizing distributed systems, in which all or most communication is symmetric. The program of the workshop was a combination of invited talks, pres- tations of position papers, and discussions covering novel peer-to-peer appli- tions and systems, peer-to-peer infrastructure, security in peer-to-peer systems, anonymity and anti-censorship, performance of peer-to-peer systems, and wo- load characterization for peer-to-peer systems. To ensure a productive workshop environment, attendance was limited to 55 participants. Each potential participant was asked to submit a position paper of 5 pages that exposed a new problem, advocated a speci?c solution, or reported on actual experience. We received 99 submissions and were able to accept 31. Participants were invited based on the originality, technical merit, and topical relevance of their submissions, as well as the likelihood that the ideas expressed in their submissions would lead to insightful technical discussions at the workshop.

✦ Table of Contents

Lecture Notes in Computer Science
Springer
Peer-to-Peer Systems
Preface
Organization
Steering Committee
Program Committee
Organizing Chairs
Sponsors
Table of Contents
Structure Overlay Routing Protocols: State of the Art and Future Directions
Deployed Peer-to-Peer Systems
Anonymous Overlays
Applications
Evaluation
Searching and Indexing
Data Management
Workshop Report for IPTPS’02 1st International Workshop on Peer-to-Peer Systems 7-8 March 2002 – MIT Faculty Club, Cambridge, MA, USA
Session 1: DHT Routing Protocols: State of the Art and Future Directions Chair: Scott Shenker
Session 2: Deployed Peer-to-Peer Systems Chair: Roger Dingledine/Steve Gribble
Session 3: Anonymous Overlays Chair: Roger Dingledine
Session 4: Applications I Chair: Frans Kaashoek
Session 5: Are We on the Right Track? Chair: John Kubiatowicz
Session 6: Searching and Indexing Chair: Robert Morris
Session 7: Security in Peer-to-Peer Systems Chair: Steve Gribble
Session 8: Applications II Chair: Ion Stoica
Session 9: Data Management Chair: David Karger
Thanks
Acknowledgements
Observations on the Dynamic Evolution of Peer-to-Peer Networks
Introduction
A Half-Life Lower Bound
A Dynamic Model for Chord
Background on Chord
The Ring-like State in Chord
Strong Stabilization
Conclusion
References
Brocade: Landmark Routing on Overlay Networks
Introduction
Tapestry Routing and Location
Routing Layer
Data Location
Brocade Base Architecture
Brocade Construction
Brocade Routing
Evaluation of Base Design
Related Work and Status
References
Routing Algorithms for DHTs: Some Open Questions
Introduction
Review of Existing Algorithms
State-Efficiency Tradeoff
Resilience to Failures
Routing Hot Spots
Incorporating Geography
Extreme Heterogeneity
References
Kademlia: A Peer-to-Peer Information System Based on the XOR Metric
Introduction
System Description
XOR Metric
Node State
Kademlia Protocol
Routing Table
Efficient Key Re-publishing
Sketch of Proof
Implementation Notes
Optimized Contact Accounting
Accelerated Lookups
Summary
References
Efficient Peer-to-Peer Lookup Based on a Distributed Trie
Introduction
System Model
Algorithms
Bounded, Unbounded, and Full Path Modes
Conservative and Liberal Modes
Preliminary Experimental Evaluation
Conclusions
References
Self-Organizing Subsets: From Each According to His Abilities, to Each According to His Needs
Introduction
Challenges to Massive Decentralization
An Overlay Peer Utility Service
Conclusions
References
Mapping the Gnutella Network: Macroscopic Properties of Large-Scale Peer-to-Peer Systems
1 Introduction
2 Gnutella Protocol Description
3 Data Collection
4 Gnutella Network Analysis
4.1 Connectivity and Reliability in Gnutella Network. Power-Law Distributions
4.2 Estimates of Generated Traffic
4.3 Internet Infrastructure and Gnutella Network
5 Summary and Future Work
Acknowledgements
References
Can Heterogeneity Make Gnutella Scalable?
Introduction
Background
Design
Evaluation
Other Related Work
Discussion
References
Experiences Deploying a Large-Scale Emergent Network
Introduction
Observed Behavior
Frequent Join / Leave
Varying Space Allocation
Varying Connection Quality
Routability
Which Parts Worked?
Which Parts Failed? (Open Problems)
Original Introduction
Data Availability
Other Open Problems
Bypassing Firewalls and NAT
Conclusion
References
Anonymizing Censorship Resistant Systems
Introduction
System Description
Publishing
Retrieval
Commentary on the Protocol
Replication
Forwarders
Encryption of Shares
Decrypters
Discussion
Related Work
Conclusion
Acknowledgements
References
Introducing Tarzan, a Peer-to-Peer Anonymizing Network Layer
Introduction
Architecture and Design
Packet Relay
Tunnel Setup
IP Packet Forwarding
Peer Selection
Policy Issues
Security and Anonymity Analysis
Implementation
Performance
Related Work
Conclusion
References
Mnemosyne: Peer-to-Peer Steganographic Storage
Introduction and Motivation
A Local Steganographic File System
Writing and Reading a Single Block
Directories, Inodes, and Files
Discussion
Distributing the Block Store
Discussion
Enhancements
Simulation
Implementation
Relation to Existing Work
References
ConChord: Cooperative SDSI Certificate Storage and Name Resolution
Introduction
SDSI Background
Design
Peer-to-Peer Architecture
Accelerating the Operations
Evaluation
DNS Traces
Mailing Lists
Related Work
Conclusion
Acknowledgments
References
Serving DNS Using a Peer-to-Peer Lookup Service
Introduction and Related Work
Design and Implementation
Evaluation
Why (Not) CooperativeDNS?
DNS Administration
Dynamically Generated Records
Denial of Service
Conclusions
References
Network Measurement as a Cooperative Enterprise
Introduction
An M-coop Design
The Service
The Architecture
Architecture Details and Operation
Routing
Measurement
Trust
AOR Assignment and Overlay Construction
Related Work
Open Questions
Acknowledgments
References
The Case for Cooperative Networking
Introduction
Cooperative Networking (CoopNet)
Where Is the Bottleneck?
Basic Operation of CoopNet
Peer Selection
Streaming Media Content
Avoiding Server-Based Redirection
Security Issues
Experimental Evaluation
Finding Content
Load on Peers
Finding Nearby Peers
Duration of Activity Period for Peers
Comparison with Alternative Approaches
Acknowledgements
References
Internet Indirection Infrastructure
Introduction
Internet Indirection Infrastructure
Rendezvous-Based Communication
Communication Primitives Provided by i3
Stack of Identifiers
i3 Implementation
Security
Anonymity
Related Work
Status
Conclusions
References
Peer-to-Peer Caching Schemes to Address Flash Crowds
Introduction
System Requirements
Design
Redirection
Resource Location
Caching and Replication
Evaluation
Related Work
Conclusions
Acknowledgments
References
Exploring the Design Space of Distributed and Peer-to-Peer Systems: Comparing the Web, TRIAD, and Chord/CFS
Introduction
The World Wide Web
TRIAD
Chord/CFS
Summary
Names and Addresses
The World Wide Web
TRIAD
Chord/CFS-style Peer-to-Peer Systems
Routing, Lookup, and Topology
The World Wide Web
TRIAD
Chord/CFS-style Peer-to-Peer Systems
Summary and Conclusions
References
Are Virtualized Overlay Networks Too Much of a Good Thing?
Introduction
Locality Is a Good Thing
Searching
Adding Information Back In
Eschewing Virtualization
Summary
References
Locating Data in (Small-World?) Peer-to-Peer Scientific Collaborations
Introduction
Small Worlds in Scientific Communities
Data Sharing in a Physics Collaboration
Locating Files in Small-World Networks
Gossiping Bloom Filters for Information Dissemination
Gossip Mechanism
Bloom Filters
Advantages of Building the System around Shared Data Interests
Creating a Small World
Summary
Acknowledgements
References
Complex Queries in DHT-based Peer-to-Peer Networks
Introduction
Background
Text Retrieval and Hash Indexes
Why Not Peer-to-Peer Databases?
P2P Query Processing
Architecture
Namespaces and Multicast
Query Processing Operators
Status
Acknowledgments
References
The Sybil Attack
1 Introduction
2 Formal Model
3 Results
3.1 Direct Identity Validation
3.2 Indirect Identity Validation
4 Related Work
5 Summary and Conclusions
Acknowledgements
References
Security Considerations for Peer-to-Peerm Distributed Hash Tables
Introduction
Background
Adversary Model
Attacks and Defenses
Routing Attacks
Storage and Retrieval Attacks
Miscellaneous Attacks
Conclusion
References
Dynamically Fault-Tolerant Content Addressable Networks
Introduction
Dynamic Fault Tolerance
Related Work
A Dynamically Fault-Tolerant Content Addressable Network
The Virtual CAN
Implementation of Virtual CAN by Peers
Search for a Data Item
Content and Peer Insertion
Conclusion
References
Appendix
Dynamic Fault-Tolerance
Scalable Management and Data Mining Using Astrolabe
Introduction
Astrolabe
Using Astrolabe
Low-Level Communication
Configuration
Communication through an ALG
Related Work
Conclusions
Acknowledgements
References
Atomic Data Access in Distributed Hash Tables
Introduction
Guarantees
Algorithm
Discussion
Fault-Tolerance
References
Pseudocode
Dynamic Replica Placement for Scalable Content Delivery
Introduction
Problem Formulation
Peer-to-Peer Location Services: The Tapestry Infrastructure
Tapestry Routing Mesh
Tapestry Distributed Location Service
Dissemination Tree Protocols
Replica Placement and Tree Construction
Soft State Tree Maintenance
Evaluation
Conclusions and Future Work
Acknowledgments
References
Peer-to-Peer Resource Trading in a Reliable Distributed System
Introduction
Data Trading
Trading Policies
Generalizing Trading in Peer-to-Peer Systems
Related Work
Conclusion
References
Erasure Coding Vs. Replication: A Quantitative Comparison
Introduction
Background
Assumptions
Availability
System Comparison
Fix MTTF and Repair Epoch
Fix Storage Overhead and Repair Epoch
Fix MTTF and Storage Overhead
Discussion
Future Work
Related Work
Conclusion
References
Appendix: Durability Derivation
Author Index