Distributed-Chord-DHT | MPI-Based Peer-to-Peer Routing

A C implementation of the Chord Distributed Hash Table (DHT) protocol using MPI (Message Passing Interface). This project simulates a structured peer-to-peer network where nodes organize themselves in a logical ring to perform efficient, logarithmic lookups without a central coordinator.

Overview

In large-scale distributed systems, locating data efficiently is a major challenge. This project implements the core mechanics of the Chord protocol, enabling nodes to route queries across a network using "finger tables." Even in a large network, lookups are guaranteed to resolve in $O(\log N)$ steps.

Technical Architecture

1. Logical Ring & Static Membership

• Nodes are mapped onto a circular identifier space of size $2^M$.
• The system uses a static ring approach, where node positions and neighbors are established during the initialization phase using MPI's global communication primitives (MPI_Allgather).
• Each node identifies its immediate successor and predecessor to maintain the basic ring structure.

2. Finger Table Implementation

• To accelerate lookups, each node constructs a Finger Table, a routing table containing shortcuts to nodes at exponential distances ($2^i$).
• I implemented the build_finger_table logic to map these distances to the closest existing successor in the network, ensuring that routing is always directed toward active nodes.

3. Logarithmic Routing Logic

• Closest Preceding Finger: When a node receives a lookup request for a key it doesn't own, it uses closest_preceding_finger to find the furthest node in its table that still precedes the target key.
• Path Tracing: Every request carries a LookupMsg payload that records the full path (sequence of node IDs), allowing for debugging and verification of the $O(\log N)$ hop count.

4. Distributed Coordination & Termination

• Service Loop: Nodes run an asynchronous event loop, processing three types of MPI tags:
  • TAG_LOOKUP_REQ: Forwarding the query closer to the destination.
  • TAG_LOOKUP_REP: Returning the final path to the initiator once the key is found.
  • TAG_DONE: Signalling that a node has completed all its local tasks.
• Graceful Shutdown: Implemented a global termination detection mechanism where the system only exits after every node has finished its lookups and all transit messages are processed.

Tech Stack

• Language: C
• Protocol: Chord (Distributed Hash Table)
• Parallel Computing: MPI (Message Passing Interface)
• Tools: GCC, MPICH/OpenMPI

Setup & Execution

Build

You can compile the project using the provided Makefile:

make

Alternatively, manual compilation:

mpicc src/chord_prot.c -o chord_prot

Run

The system reads local IDs and lookup keys from rank-specific input files (in0.txt, in1.txt, etc.).

# Example for 4 nodes
mpirun -np 4 ./chord_system