Distributed Tree Infrastructure for Peer-to-Peer Systems

Yale University, New Haven CT

Investigators

Abstract

Peer-to-peer networks are distributed systems without any central authority that are used for efficient management and location of shared resources. Unlike traditional client-server architectures, which concentrate load on a small number of server machines, peer-to-peer systems provide inherent scalability by distributing the cost of maintaining the system across its participants. At the same time, peer-to-peer systems create new challenges for efficient and robust implementation, as they are built from untrusted and unreliable components and can provide survivability only as an emergent property of the system as a whole. The project studies applications of large-scale distributed data structures to peer-to-peer systems, with an emphasis on efficiency, scalability, fault-tolerance, and recovery. Major goals of the project include (a) design and implementation of mechanisms for optimal trade-offs between use of the network and use of local storage; (b) design and implementation of mechanisms for very fast construction of large-scale distributed data structures; and (c) use of data structures providing ``range queries,'' in which the data structure finds nearest matches to a desired object instead of just exact matches, to support versioning, replication, and approximate matching.