Koorde

Koorde is a peer-to-peer distributed hash table that combines a ring-based overlay with de Bruijn graph routing to support scalable and efficient key lookups in dynamic networks. It is designed to provide fast routing with a compact maintenance footprint, suitable for large and frequently changing groups of nodes.

In Koorde, each node has a unique identifier in a fixed binary space, and data keys are hashed into the same space. A key is stored at a node that is responsible for the corresponding identifier, typically near or at the position on the ring associated with the key. Each node maintains a small set of neighbours, including its immediate successor on the ring and a collection of de Bruijn-like edges derived from its identifier. This mix of edges allows for both local stability and longer-range routing opportunities.

The routing protocol uses the de Bruijn edges to progressively reduce the distance to the target identifier. By following edges that align with the bit-pattern of the destination, the lookup converges toward the target in a logarithmic number of steps relative to the number of participating nodes. The routing table remains compact, and lookups can be completed without requiring large, bandwidth-intensive routing structures.

Koorde supports dynamic membership through a stabilization process that updates successor pointers and de Bruijn edges as nodes join or depart. Data replication across multiple nodes enhances fault tolerance and availability, helping to mitigate churn and node failures.

Overall, Koorde aims to provide efficient routing with modest per-node state while maintaining robustness in changing networks. It is frequently discussed alongside other DHT designs such as Chord and Kademlia as a hybrid approach that leverages both ring structure and structured routing.