Fault-Tolerant Distributed Resource Location

James Aspnes的“容错分布式资源定位”资源定位是分布式计算中的一个基本问题。例如，将URL转换为机器地址、将电话号码映射到单个电话以及在Web上搜索文档等基本任务。典型的当前解决方案涉及维护集中式目录，这些目录成为速度和可靠性的瓶颈；这样的解决方案也不适合个人机器自由进出的点对点系统。研究了如何在整个网络中全息分布目录信息，从而使搜索的成本均匀分布，不需要专门的服务器机器，即使很大一部分机器离开系统，仍然可以找到资源。主要技术是构造随机图，其节点(代表资源和机器)根据它们的关键字在某个空间中被分配坐标。搜索资源涉及将目标从某个初始节点移动到更靠近目标的相邻节点，直到到达目标。该项目的核心部分是设计图表结构，为快速搜索提供正确的短距离和长距离边组合，以及设计本地机制，以便在没有中央协调的情况下快速建造和修复这种结构。

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 machineaddresses, mapping telephone numbers to individual telephones, andsearching for documents on the Web. Typical current solutions involvemaintaining centralized directories that become bottlenecks thatimpair speed and reliability; such solutions are also unsuited topeer-to-peer systems where individual machines come and go freely. Theresearch examines how to distribute directory informationholographically throughout the network, so that the costs of searchesare spread evenly, no specialized server machines are needed, andresources can still be found even if a large fraction of the machinesleave the system.The main technique is the construction of random graphs whose nodes(representing resources and machines) are assigned coordinates in somespace based on their keys. Searching for a resource involves moving atoken from some initial node to adjacent nodes closer to the targetuntil the target is reached. Core components of the project are thedesign of graph structures that provide the correct mix ofshort-distance and long-distance edges for fast searching and thedesign of local mechanisms for building and repairing such structuresquickly without central coordination.