Fault-Tolerant Distributed Resource Location

容错分布式资源定位

• 批准号: 0098078
• 负责人: James Aspnes
• 金额: $ 20.09万
• 依托单位: Yale University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2001
• 资助国家: 美国
• 起止时间: 2001-09-01 至 2004-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0098078&HistoricalAwards=false
• 关键词: Fault; Tolerant; Distributed; Resource; Location

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.

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