Kademlia DHT Architecture in Macula

Overview

Macula uses a Kademlia Distributed Hash Table (DHT) for service discovery and procedure routing between relay nodes. In the federated relay mesh, the DHT runs between relays (not between end nodes). Nodes discover services by querying their relay, which routes lookups through the Kademlia network of peered relays.

Key Reference: Kademlia: A Peer-to-peer Information System Based on the XOR Metric (Maymounkov & Mazières, 2002)

Why Kademlia?

Traditional DHTs (like Chord) use numeric distance metrics that don't align well with network topology. Kademlia's XOR-based metric provides:

1. Symmetric distance - distance(A, B) = distance(B, A)
2. Network-aware routing - Nodes sharing common prefixes tend to be routed through similar paths
3. O(log N) lookup complexity - Efficient even with millions of nodes
4. Self-organizing - No central coordination required
5. NAT-friendly - Works well with HTTP/3's connection-oriented transport

Core Concepts

1. Node IDs and XOR Metric

Every node in the Macula mesh has a 160-bit Node ID derived from:

• Hash of (realm + peer_id) for deterministic addressing
• Or randomly generated via crypto:strong_rand_bytes(32) on startup

Note: Since v0.8.5, all nodes have identical capabilities. The terms "Gateway mode" and "Edge peer mode" are deprecated.

XOR Distance Formula:

distance(A, B) = A ⊕ B (bitwise XOR)

Example:

Node A: 0b10110101
Node B: 0b11010011
-------
XOR:    0b01100110  (distance = 102 decimal)

Nodes are considered "closer" when their XOR distance is smaller. This creates a geometric address space where routing naturally follows network topology.

2. K-Buckets (Routing Table)

Each node maintains a routing table of 160 k-buckets, where k = 20 (typical value).

Structure:

• Bucket 0: Nodes at distance 2^0 to 2^1 - 1 (immediate neighbors)
• Bucket 1: Nodes at distance 2^1 to 2^2 - 1
• Bucket i: Nodes at distance 2^i to 2^(i+1) - 1
• Bucket 159: Nodes at distance 2^159 to 2^160 - 1 (furthest)

K-Bucket Properties:

• Maximum of k entries per bucket
• Least-recently-seen nodes are evicted first (LRU)
• Bucket 0 (closest nodes) is most important for routing

Macula Implementation:

%% In macula_routing.erl (conceptual)
-define(KADEMLIA_K, 20).          %% Bucket size
-define(KADEMLIA_ALPHA, 3).       %% Parallel lookup factor
-define(ID_BITS, 160).            %% SHA-1 hash size

-record(k_bucket, {
    distance_range :: {integer(), integer()},
    nodes :: [node_entry()],       %% Max 20 entries
    last_updated :: erlang:timestamp()
}).

3. DHT Operations

Kademlia defines four core RPC operations:

PING

Purpose: Check if a node is alive

Request:

{ping, FromNodeID, Timestamp}

Response:

{pong, ToNodeID, Timestamp}

Use Case: Health checking, routing table maintenance

STORE

Purpose: Store a key-value pair on a node

Request:

{store, Key, Value, TTL}

Response:

{stored, Key, ExpiresAt}

Macula Mapping:

• Key: Service name hash (e.g., sha1("game.matchmaking"))
• Value: Service endpoint info (realm, node_id, capabilities)
• TTL: Advertisement lifetime (default: 5 minutes)

FIND_NODE

Purpose: Locate k closest nodes to a target ID

Request:

{find_node, TargetID, K}

Response:

{nodes, [
    {NodeID1, IP1, Port1, Realm1},
    {NodeID2, IP2, Port2, Realm2},
    ...
]} %% Sorted by XOR distance to TargetID

Use Case: Populating routing table, iterative lookups

FIND_VALUE

Purpose: Retrieve value for a key (service discovery)

Request:

{find_value, Key}

Response (if found):

{value, Key, ServiceInfo}

Response (if not found):

{nodes, [...]}  %% Fallback to FIND_NODE

Macula Mapping:

• Key: Service name (e.g., "game.matchmaking")
• ServiceInfo: List of providers advertising that service

4. Iterative Lookup Algorithm

To find a service or node, Macula performs an iterative FIND_VALUE lookup:

Algorithm:

1. Start with the α = 3 closest nodes from local routing table
2. Send parallel FIND_VALUE requests to these nodes
3. If value found → return immediately
4. Otherwise, add returned nodes to candidate set
5. Select next α closest unqueried nodes
6. Repeat until:
   • Value is found, OR
   • No closer nodes remain, OR
   • Maximum hops reached (log₂N)

Convergence: Guaranteed to find value in O(log N) hops

Macula Implementation (conceptual):

find_service(ServiceName, Realm) ->
    Key = crypto:hash(sha, ServiceName),
    ClosestNodes = get_closest_nodes(Key, ?KADEMLIA_ALPHA),
    iterative_lookup(Key, ClosestNodes, #{}, 0).

iterative_lookup(Key, [], _Queried, _Hops) ->
    {error, not_found};
iterative_lookup(Key, Candidates, Queried, Hops) when Hops > 20 ->
    {error, max_hops_exceeded};
iterative_lookup(Key, Candidates, Queried, Hops) ->
    %% Query α closest unqueried nodes in parallel
    Results = query_nodes(Candidates, {find_value, Key}),

    case find_value_in_results(Results) of
        {ok, Value} ->
            {ok, Value};
        not_found ->
            NewNodes = extract_nodes(Results),
            NextCandidates = select_closest_unqueried(Key, NewNodes, Queried),
            iterative_lookup(Key, NextCandidates,
                           maps:merge(Queried, mark_queried(Candidates)),
                           Hops + 1)
    end.

Macula-Specific Adaptations

1. Realm-Scoped DHT

Unlike traditional Kademlia, Macula implements multi-tenancy via realms:

• Each realm has its own isolated DHT keyspace
• Node IDs include realm hash: sha1(Realm || IP || Port)
• Service keys are realm-scoped: sha1(Realm || ServiceName)
• Cross-realm queries are blocked at protocol level

Example:

%% Realm "macula.arcade"
NodeID_A = sha1("macula.arcade" ++ "192.168.1.10" ++ "4433")

%% Realm "macula.energy"
NodeID_B = sha1("macula.energy" ++ "192.168.1.10" ++ "4433")

%% Same IP/port, different realms → different DHT partitions

2. Seed Nodes (Bootstrap)

Traditional Kademlia requires bootstrap nodes to join the network. Macula uses seed nodes:

All Nodes Are Equal (v0.8.5+):

• Any node can serve as a seed node for new peers
• Seed nodes are configured via MACULA_BOOTSTRAP_REGISTRY env var
• Published at predictable URLs (e.g., https://seed.example.com:4433)

Joining Process:

• New peer connects to seed node
• Seed returns α closest nodes to peer's ID
• Peer populates routing table via FIND_NODE requests

No Hardcoded Bootstrap IPs: Unlike BitTorrent DHT, Macula uses DNS/HTTPS URLs for seed discovery, making it firewall-friendly.

Note: The terms "Gateway mode" and "Edge peer mode" are deprecated since v0.8.5. All nodes have identical capabilities.

3. Service Advertisement TTL

Services are stored in the DHT with a Time-To-Live (TTL):

• Default TTL: 5 minutes
• Providers re-advertise every 60 seconds (heartbeat)
• Expired entries are removed by macula_advertisement_manager

Rationale: Short TTL ensures stale services don't linger after node crashes, while frequent heartbeats maintain availability.

4. HTTP/3 Transport Integration

Traditional Kademlia uses UDP for RPCs. Macula uses QUIC (HTTP/3):

Advantages:

• Reliable transport (no packet loss issues)
• Connection multiplexing (multiple RPCs over one connection)
• TLS 1.3 encryption (secure by default)
• QUIC connection migration

Message Encoding:

%% DHT query wrapped in Macula protocol
#{
  type => dht_query,
  operation => find_value,
  key => <<ServiceNameHash:160>>,
  realm => <<"macula.arcade">>,
  from_node_id => <<SenderNodeID:160>>,
  timestamp => erlang:system_time(millisecond)
}

Routing Table Maintenance

Macula keeps routing tables fresh through active probing:

1. Passive Updates

• When receiving any message from node N, refresh N's entry in k-bucket
• Update last-seen timestamp
• Move N to tail of LRU list (most recently seen)

2. Active Probing

• Every 60 seconds, ping least-recently-seen node in each non-empty bucket
• If ping fails 3 times consecutively, evict node
• Backfill bucket via FIND_NODE request

3. Bucket Splitting

• When bucket 0 (closest nodes) exceeds k entries, split into two buckets
• Move nodes to new buckets based on refined distance ranges
• Only split buckets containing own node ID (hot zone)

Implementation:

%% In macula_routing.erl
-define(REFRESH_INTERVAL, 60000).  %% 60 seconds
-define(PING_TIMEOUT, 5000).       %% 5 seconds
-define(MAX_FAILURES, 3).

refresh_buckets(State) ->
    lists:foldl(fun refresh_bucket/2, State, State#state.k_buckets).

refresh_bucket(Bucket, State) ->
    case get_least_recent_node(Bucket) of
        undefined -> State;  %% Empty bucket
        Node ->
            case ping_node(Node) of
                pong -> update_node_timestamp(Node, State);
                timeout -> handle_ping_failure(Node, State)
            end
    end.

Performance Characteristics

Example (10,000-node network):

• Expected hops: log₂(10,000) ≈ 13.3 → 14 hops max
• Parallel factor α = 3 → ~5 rounds of queries
• Average lookup time: 5 rounds × 100ms RTT = 500ms

Comparison to Other DHTs

Future Enhancements

1. S/Kademlia (Secure Kademlia)

• Cryptographic node ID generation (prevent Sybil attacks)
• Require nodes to solve proof-of-work for ID assignment
• Disjoint routing paths for redundancy

2. DHT Persistence

• Store service advertisements in distributed database (e.g., CRDT)
• Survive network partitions with eventual consistency
• Reduce re-advertisement overhead

3. Adaptive K-Bucket Sizing

• Dynamically adjust k based on network churn rate
• Larger k for stable networks (less probing overhead)
• Smaller k for high-churn networks (faster convergence)

References

1. Kademlia Paper: Maymounkov & Mazières (2002)
2. S/Kademlia: Baumgart & Mies (2007)
3. BitTorrent DHT (BEP-0005): bittorrent.org/beps/bep_0005.html
4. QUIC Protocol: RFC 9000
5. Macula Architecture: docs/QUIC_TLS_GATEWAY_SETUP.md

Last Updated: 2026-01-25 Macula Version: 0.20.2+ Status: ✅ Production-ready DHT implementation