Fault-Tolerant Distributed Resource Location

Yale University, New Haven CT

Investigators

Abstract

James Aspnes "Fault-Tolerant Distributed Resource Location" Resource location is a fundamental problem in distributed computing. Examples include such basic tasks as translating URLs into machine addresses, mapping telephone numbers to individual telephones, and searching for documents on the Web. Typical current solutions involve maintaining centralized directories that become bottlenecks that impair speed and reliability; such solutions are also unsuited to peer-to-peer systems where individual machines come and go freely. The research examines how to distribute directory information holographically throughout the network, so that the costs of searches are spread evenly, no specialized server machines are needed, and resources can still be found even if a large fraction of the machines leave the system. The main technique is the construction of random graphs whose nodes (representing resources and machines) are assigned coordinates in some space based on their keys. Searching for a resource involves moving a token from some initial node to adjacent nodes closer to the target until the target is reached. Core components of the project are the design of graph structures that provide the correct mix of short-distance and long-distance edges for fast searching and the design of local mechanisms for building and repairing such structures quickly without central coordination.