Understanding Koorde: A Simple Degree Optimal DHT
Koorde is a distributed hash table (DHT) algorithm based on Chord and de Bruijn graph, offering optimal lookup performance with a low number of hops. It embeds a de Bruijn graph on the Chord identifier ring, enabling efficient message routing between nodes. The algorithm is designed to provide logarithmic hops per lookup request, making it an efficient solution for decentralized systems.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Koorde Koorde: A simple degree optimal DHT : A simple degree optimal DHT M. Frans Kaashoek and David Karger MIT Laboratory of Computer Science
Introduction Introduction Koorde is a DHT based on Chord and de Bruijn graph. O(log n) hops per lookup request with only 2 neighbors per node. Can be generalized to O(log n/ log log n) hops per lookup request with O(log n) neighbors per node
Bounds Bounds Lemma An n-node network with maximum node degree d requires at least logd(n-1) routing hops in the worst case. Why?
De De Bruijn Bruijn graph graph A node m has two outgoing edges to nodes 2m mod 2b and 2m+1 mod 2b. Call them the 0-link and the 1-link
Koorde Koorde embeds a de Bruijn graph on the Chord identifier ring shown below.
Koorde Koorde A message from node i to node j can be routed as follows: 1. Shift the bits of j so that its leading r bits tally with the last r bits of i 2. Forward the query along the paths corresponding to the last (log n r) bits of j: Route via 0-link, 0-link Each 0 bit = a hop along the 0-link Each 1 bit = a hop along the 1-link. Routing takes at most log n hops (optimal)
Generalized version of Generalized version of Koorde Koorde For k > 2, the earlier construction can easily be generalized. From each node i, there will be k routing fingers pointing to the nodes k i, k i + 1, k i + 2,..., k i + k 1 (additions mod n) The path length will be at most logkn i.e. log n/log k between any pair of nodes When k=log n, the path length is log n/log log n
