My_CHORD - Distributed Peer-to-Peer Protocol

Author: Catalin Moldoveanu
Group: 331 CC

Overview

This project implements the My_CHORD protocol, a scalable Distributed Hash Table (DHT) logic using MPI for process communication. The system simulates a structured peer-to-peer network where nodes are organized in a logical ring. The implementation focuses on efficient resource location using logarithmic routing and robust synchronization to handle high-traffic scenarios across thousands of virtual nodes.

Implementation Details

Ring Architecture and Initialization

The network is built as a static ring where each process identifies its position based on a unique ID.

• Global Membership: At startup, every node participates in an MPI_Allgather operation to collect the IDs of all processes in the system.
• Topology Sorting: The gathered IDs are sorted locally. Each node then identifies its immediate Successor (the first node with a larger ID in circular order) and its Predecessor.
• Key Space Management: The system uses an $M=31$ bit identifier space, supporting keys up to $2^{31}-1$. All interval checks and distance calculations are performed using modulo $2^{31}$ arithmetic to ensure consistency across the ring.

Finger Table and Routing Optimization

To achieve $O(\log N)$ lookup complexity, I implemented a distributed routing table (Finger Table).

• Finger Table Construction: Each node builds a table with 31 entries. The $i$-th entry points to the node responsible for the ID $(self_id + 2^i) \pmod{2^{31}}$.
• Closest Preceding Finger (LPM-like logic): When searching for a key, the node parcurge the Finger Table from the largest index to 0. It looks for the furthest node that is strictly between itself and the target key. This ensures that each hop reduces the distance to the destination by at least half.

Message Processing and Communication

The router-like dataplane of the protocol uses a service loop based on MPI_Recv with specific message tags:

• TAG_LOOKUP_REQ: Represents a search query in transit. The node checks if its successor is the owner of the key; if not, it forwards the message using the Finger Table.
• TAG_LOOKUP_REP: The final response sent directly from the destination node back to the lookup initiator once the key is found.
• Path Tracking: Each message carries a path array, recording every node ID it visits to allow for performance analysis and debugging.

Critical Scalability Optimizations

To pass complex scalability tests (Tests 6, 7, and 8) without deadlocks, I implemented the following features:

1. Deadlock-Free Local Initiation

In high-load scenarios, sending a message to oneself via MPI_Send can fill the internal MPI buffers before the process reaches the MPI_Recv call. I modified the initiation logic so that locally generated lookup requests call the handle_lookup_request function directly, bypassing the network stack for the first hop.

2. Master-Worker Termination Protocol

To avoid network congestion ("network storms") during shutdown, I implemented a centralized coordination system:

• Nodes send a TAG_DONE message to Rank 0 when they finish their tasks.
• Rank 0 acts as a monitor, counting finished nodes.
• Once everyone is done, Rank 0 broadcasts a TAG_TERMINATE signal to all processes, ensuring a clean exit without flooding the MPI channels.

3. Memory-Efficient ID Mapping

Since the ID space is $2^{31}$, using a static array for ID-to-Rank mapping would consume gigabytes of RAM. Instead, I use a fast linear search through the sorted list of active IDs. This optimization maintains a minimal memory footprint while remaining efficient enough for the maximum node count allowed.

Features Implemented

• IPv4-style Identifier Mapping using a 31-bit space.
• Logarithmic Route Lookup via Finger Tables.
• Asynchronous Message Loop for distributed request handling.
• Master-Worker Coordination for scalable process termination.
• Direct Recursion Optimization to prevent MPI deadlocks.

How to Run

1. Navigate to the src folder: cd src/
2. Compile: make
3. Run: mpirun -np [nodes] ./My_CHORD