How to create finger tables in a Chord distributed hash table

Finger tables enable efficient lookups within Chord distributed hash tables (DHTs). In this Answer, we'll delve into the significance of finger tables and walk through their creation process. Let's begin by understanding why finger tables are crucial for Chord DHTs.

Chord DHTs operate within an identifier space of $2^m$, generating IDs in the range of $0$ to $2^m-1$, where “m” is a user-defined value. To support the structure of Chord DHTs, each node maintains its own finger table consisting of “m” entries. These finger tables serve as a navigational aid and streamline the routing and retrieval of data.

To better understand finger tables, let's consider an example. Assume that we have “m” set to $4$. Here's the structure of that finger table:

In this table, we represent the entry numbers (indices) in the first column, and the associated successor node IDs are in the second. These successor node IDs play a crucial role in the lookup process.

Syntax overview

Before we dive into calculating successor node IDs, let's familiarize ourselves with some syntax, as detailed below:

• $FT_n$ refers to the finger table of the node with an ID equal to “n.” For instance, to refer to the finger table of node $3$, we use $FT_3$.

• $FT_n[i]$ refers to the $i^{th}$ successor node in the finger table of the node with an ID equal to “n.” For example, $FT_4[2]$ denotes the second successor node in the finger table of node $4$.

Calculate successor node IDs

Now, let's explore the expression used to find the $i^{th}$ successor node of the current node “n”:

$FT_{n}[i] = (n + 2^{i-1}) <br>$

Here:

• “n” represents the node ID.

• “i” denotes the entry number/index value of the successor node.

Note: Remember that subtracting the maximum possible node ID (i.e., $2^m-1$) is necessary if the resulting value exceeds the maximum value in the identifier space. Additionally, we round up values to the nearest greater node ID to match values with valid node IDs in the DHT.

A practical example

The following image illustrates how to create finger tables for the Chord DHT with nodes 3, 6, and 11.

We start by substituting appropriate values in the expression to evaluate node IDs and then evaluate them. First, we check if the resulting values are within the identifier space. In the example above, we subtract 11 from all the values exceeding the ID range. Then, we round up all the values that do not match any node ID to the closest greater ID. For example, we will round up 4 to ID 6.