Searching in Peer-to-Peer Networks
Matthias Ruhl, MIT

Abstract:
Peer-to-peer networks are collections of networked computing devices, cooperating in distributed applications without any central control. The availability of networking infrastructures and cheap computing devices have recently made these networks economically feasible and therefore led to a considerable amount of research on them. In this talk, we focus on distributed data storage as an application for peer-to-peer networks, and in particular on the search function necessary for such an application.

In this talk we present two recent results extending the search capabilities of peer-to-peer networks. First, we show a protocol that starting from any node in the network, can find the nearest node in the remaining network, measured in network latency or geographical distance. The protocol can also be used to find the closest copy of a redundantly stored data item. Usage of this protocol can lead to reduced bandwidth usage and access time when retrieving data items. Second, we show how perform efficient searches on ordered data, such as finding the closest match to a given query, or find all data items that fall within a certain range. Since many kinds of data have natural orders, this protocol has many applications.

Host: Danny Sleator
Appointments: Susan Hrishenko (susan027@cs.cmu.edu, x8-7317)