具有逻辑路由跳数O(1)的可扩展的分散式查找算法

摘要

对等网络中的一个基本问题就是如何高效地进行数据查找.分散式查找是解决这类问题的一种新思路.现有的分散式查找方法在查找时所需的逻辑路由跳数都与网络中的节点数相关(一般为O(logn),少数为O(n1/c)). Sifter是一种可扩展、自组织、高容错和高效率的分散式查找算法.在该算法中,单个节点只需维护O(n1/c)个其他节点的链接信息,就能够在O(1)个逻辑路由跳内找到目的数据.该算法适用于网络动态性不大,但是对查找的实时性要求较高的应用.