Abstract

我们描述了一个和对等分布式哈希表，并证实其一致性和易发生故障环境中的表现。我们的系统路径查询和定位node采用了新奇的基于异或的制度拓扑结构，这有利于简化我们的算法和促进我们的结论。该拓扑具有以下特性，每一个信息节点都能相互交换传送或者提供有用的联系信息。系统利用这些信息发送平行异步的请求信息并且达到能容忍节点故障，而不会导致用户超时延迟。

Introduction

这篇论文描述的是Kademlia协议，一个DHT(分布式哈希表)网络。Kademlia有许多不需要任何先前DHT网络提供的理想特性。它最小化了节点需要向其他节点发送学习的配置信息。配置信息会自动的扩展传导就像数据库中进行key lookup的寻找时附带的某种连带作用。节点有足够的能力和灵活性利用低延迟的路径进行路径查询。Kademlia使用平行异步的请求它去避免因为节点故障带来的延迟。算法通过节点去记录彼此从而来抵抗某些基本服务攻击。最后仅通过假设正常运行的分布式系统就可以正式的证明Kademlia的一些重要特性。

Kademlia采取许多DHTS的基本方法。key值是具有隐蔽性的，一串160位的二进制字符串。(比如使用SHA-1算法）。每一个计算机都应该具有一个160-bit的node ID。最后，通过一个基于node id的路由算法能够高效的定位任意一个给定node id的最近节点。

System Description

...

XOR Metric

...

Node State

...

Kademlia Protocol

...

Routing Table

 

说实话还是看原文吧。

Every node with prefix

001 would have an empty k-bucket into which u should be inserted, yet u’s bucket

refresh would only notify k of the nodes.

这句真是令人惆怅，比较难以理解。