Structured Gossip: A Partition-Resilient DNS for Internet-Scale Dynamic Networks Priyanka Sinha
Dilys Thomas
[email protected] Docyt India
[email protected] Tata Consultancy Services Limited India
arXiv:2603.07750v1 [cs.NI] 8 Mar 2026
Abstract Network partitions pose fundamental challenges to distributed name resolution in mobile ad-hoc networks (MANETs) and edge computing. Existing solutions either require active coordination that fails to scale, or use unstructured gossip with excessive overhead. We present Structured Gossip DNS, exploiting DHT finger tables to achieve partition resilience through passive stabilization. Our approach reduces message complexity from 𝑂 (𝑛) to 𝑂 (𝑛/log 𝑛) while maintaining 𝑂 (log2 𝑛) convergence. Unlike active protocols requiring synchronous agreement, our passive approach guarantees eventual consistency through commutative operations that converge regardless of message ordering. The system handles arbitrary concurrent partitions via version vectors, eliminating global coordination and enabling billion-node deployments.
CCS Concepts • Information systems → Distributed database systems; • Networks → Network protocol design; Mobile and wireless networking.
Keywords Distributed Hash Tables, Gossip Protocols, Network Partitions, DNS, MANET, Eventual Consistency ACM Reference Format: Priyanka Sinha and Dilys Thomas. 2026. Structured Gossip: A PartitionResilient DNS for Internet-Scale Dynamic Networks. In Proceedings of International Conference on Management of Data (SIGMOD ’26). ACM, New York, NY, USA, 4 pages. https://doi.org/XXXXXXX.XXXXXXX
1
Introduction
Network partitions represent a critical failure mode in distributed systems, particularly devastating for hierarchical name resolution services like DNS. In mobile ad-hoc networks (MANETs), edge computing deployments, and disaster scenarios, network partitions occur frequently due to node mobility, link failures, and environmental interference [2]. Traditional DNS architectures rely on a stable root server hierarchy, making them fundamentally incompatible with partition-prone environments. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]. SIGMOD ’26, Philadelphia, PA, USA © 2026 ACM. ACM ISBN 978-1-4503-XXXX-X/26/06 https://doi.org/XXXXXXX.XXXXXXX
Previous work on auto-configuration in multi-hop networks [2] identified the core problem: when a MANET partitions across organizational boundaries, nodes lose access to authoritative DNS servers even when they remain physically reachable. Simply adapting DHT-based protocols like CHORD [3] to MANETs fails catastrophically during network mergers, as concurrent ring repairs create irrecoverable topologies (detailed in Section 2). Recent approaches fall into two categories: (1) active coordination protocols that scale poorly beyond thousands of nodes due to synchronization overhead [4], and (2) unstructured gossip protocols that achieve eventual consistency but generate 𝑂 (𝑘𝑛) messages per round for fanout 𝑘 [5]. Neither approach satisfies the dual requirements of internet-scale deployability and partition resilience. We make the following contributions:
• A passive stabilization protocol using structured gossip that reduces message complexity from 𝑂 (𝑛) to 𝑂 (𝑛/log 𝑛) by exploiting DHT finger tables as the gossip network • Formal proof of eventual consistency guarantees through commutative and idempotent state merge operations • A version vector-based merger protocol that handles arbitrary numbers of concurrent partitions without global coordination or active synchronization • Theoretical analysis proving 𝑂 (log2 𝑛) convergence time with 𝑂 (𝑛 log2 𝑛) total message complexity • An interactive demonstration showing partition resilience at scale
2 Background and Motivation 2.1 The Partition Problem in MANETs Consider a MANET with DNS servers arranged in a CHORD ring. When the underlying network partitions, the logical DHT ring fragments into disconnected segments. Sinha [2] documented specific failure modes: Single Partition Scenario: A ring of 16 nodes splits at node 5, creating partitions 𝑃1 = {0, 1, 2, 3, 4, 5} and 𝑃2 = {6, 7, ..., 15}. Each partition can stabilize its local ring using CHORD’s passive stabilization. However, when the network merges, nodes may attempt concurrent joins, creating cycles and unreachable segments. Multiple Partition Scenario: If the network fragments into partitions 𝑃1 , 𝑃2 , and 𝑃3 simultaneously, and later 𝑃1 and 𝑃 2 merge while 𝑃3 remains isolated, existing protocols fail. Active join protocols create coordination bottlenecks, while passive stabilization produces the pathological cases illustrated in [2] Figures 4.7 and 4.8, where rings form invalid topologies with unreachable segments.
SIGMOD ’26, June 22–27, 2026, Philadelphia, PA, USA
2.2
Why Existing Approaches Fail
Active Coordination: Protocols like RANCH [4] use two-phase commits requiring 𝑂 (𝑛) messages per join. For 𝑘 partitions with 𝑛 nodes, this generates 𝑂 (𝑛 2 ) messages. Critically, active protocols require synchronous agreement—if any participant is unreachable, the protocol blocks. The price of validity in dynamic networks [14] shows this blocking behavior is fundamental to consistency guarantees in active protocols. In MANETs with frequent partitions, this halts all progress. Passive Stabilization (CHORD): CHORD’s passive approach [3] scales well but assumes a single ring. During partitions, fragments stabilize independently. On merger, concurrent stabilization creates race conditions yielding pathological topologies [2] with cycles and unreachable segments. Unstructured Gossip: Epidemic protocols [5] with fanout 𝑘 generate 𝑘𝑛 messages per round, totaling 𝑂 (𝑘𝑛 log 𝑛) for convergence—90 billion messages for a billion nodes with 𝑘 = 3.
3 Structured Gossip Protocol 3.1 Core Insight DHT finger tables already provide exponentially spaced links across the identifier space. In a 𝑛-node CHORD ring, node 𝑖 maintains fingers to nodes at distances 20, 21, ..., 2 ⌈log 𝑛⌉ . These fingers enable 𝑂 (log 𝑛) lookup by creating shortcuts across the ring. Our key insight: use finger links as the gossip network. Instead of gossiping to random partners, each node gossips along its DHT structure. This provides exponential information spread similar to Symphony’s small-world DHT [11] but optimized for partition resilience. The approach leverages lookahead properties [12] where knowing neighbors’ neighbors accelerates convergence.
3.2
Passive Stabilization vs. Active Coordination
Our protocol uses passive stabilization [1]: nodes make local decisions without waiting for acknowledgments. This follows Dijkstra’s principle that systems can converge to correct states through local actions despite distributed control. Active coordination requires synchronous agreement, blocking operations, and 𝑂 (𝑛) coordination overhead. Passive stabilization uses asynchronous updates, non-blocking operations, and eventual consistency through commutative operations (proven in Section 4.4).
3.3
Algorithm Description
Each node maintains three types of state: Hard State (authoritative data): • DNS translations: (𝑛𝑎𝑚𝑒, 𝐼𝑃,𝑇𝑇 𝐿, 𝑣𝑒𝑟𝑠𝑖𝑜𝑛) tuples • Version vector: 𝑉𝑉 [𝑖] tracks latest update from node 𝑖 Soft State (reconstructable via gossip): • Successor and predecessor pointers • Finger table: {(2𝑘 , node)} for 𝑘 ∈ [0, log 𝑛] Partition State: • Local partition ID • Known partitions set • Cross-partition link set
Priyanka Sinha and Dilys Thomas
Algorithm 1: Structured Gossip Round Input: Node 𝑖 with partition ID 𝑝𝑖 Output: Gossip messages sent, state updated // Identify reachable gossip targets in same partition 1 𝑡𝑎𝑟𝑔𝑒𝑡𝑠 ← ∅; 2 𝑠𝑎𝑚𝑒𝑃𝑎𝑟𝑡 ← { 𝑗 ∈ 𝑉 : 𝑝𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛[ 𝑗 ] = 𝑝𝑖 ∧ 𝑎𝑐𝑡𝑖𝑣𝑒 [ 𝑗 ] = true}; // Always gossip to successor if reachable 3 if 𝑠𝑢𝑐𝑐𝑒𝑠𝑠𝑜𝑟 [𝑖 ] ∈ 𝑠𝑎𝑚𝑒𝑃𝑎𝑟𝑡 then 4 𝑡𝑎𝑟𝑔𝑒𝑡𝑠 ← 𝑡𝑎𝑟𝑔𝑒𝑡𝑠 ∪ {𝑠𝑢𝑐𝑐𝑒𝑠𝑠𝑜𝑟 [𝑖 ] }; // Select furthest finger for exponential spread 𝑓 𝑖𝑛𝑔𝑒𝑟𝑠 ← { 𝑓 ∈ 𝑓 𝑖𝑛𝑔𝑒𝑟𝑇 𝑎𝑏𝑙𝑒 [𝑖 ] : 𝑓 ∈ 𝑠𝑎𝑚𝑒𝑃𝑎𝑟𝑡 }; 6 if 𝑓 𝑖𝑛𝑔𝑒𝑟𝑠 ≠ ∅ then 7 𝑓 𝑢𝑟𝑡ℎ𝑒𝑠𝑡 ← arg max 𝑓 ∈ 𝑓 𝑖𝑛𝑔𝑒𝑟𝑠 distance(𝑖, 𝑓 ); 8 𝑡𝑎𝑟𝑔𝑒𝑡𝑠 ← 𝑡𝑎𝑟𝑔𝑒𝑡𝑠 ∪ { 𝑓 𝑢𝑟𝑡ℎ𝑒𝑠𝑡 }; 5
// Send gossip messages with version vectors foreach 𝑗 ∈ 𝑡𝑎𝑟𝑔𝑒𝑡𝑠 do 10 𝑚𝑠𝑔 ← ⟨𝑘𝑛𝑜𝑤𝑛𝑁 𝑜𝑑𝑒𝑠 [𝑖 ], 𝑉𝑉 [𝑖 ], 𝑝𝑖 , 𝑝𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛𝑉 𝑒𝑟𝑠𝑖𝑜𝑛[𝑖 ] ⟩; 11 SendGossip(𝑖, 𝑗, 𝑚𝑠𝑔); 9
// Detect cross-partition links for merger detection 𝑠𝑡𝑟𝑢𝑐𝑡𝑢𝑟𝑒𝐿𝑖𝑛𝑘𝑠 ← 𝑓 𝑖𝑛𝑔𝑒𝑟𝑇 𝑎𝑏𝑙𝑒 [𝑖 ] ∪ {𝑠𝑢𝑐𝑐𝑒𝑠𝑠𝑜𝑟 [𝑖 ], 𝑝𝑟𝑒𝑑𝑒𝑐𝑒𝑠𝑠𝑜𝑟 [𝑖 ] }; 13 foreach 𝑘 ∈ 𝑠𝑡𝑟𝑢𝑐𝑡𝑢𝑟𝑒𝐿𝑖𝑛𝑘𝑠 do 14 if 𝑎𝑐𝑡𝑖𝑣𝑒 [𝑘 ] = true ∧ 𝑝𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛[𝑘 ] ≠ 𝑝𝑖 then 15 𝑐𝑟𝑜𝑠𝑠𝑃𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛𝐿𝑖𝑛𝑘𝑠 [𝑖 ] ← 𝑐𝑟𝑜𝑠𝑠𝑃𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛𝐿𝑖𝑛𝑘𝑠 [𝑖 ] ∪ {𝑘 }; 16 𝑘𝑛𝑜𝑤𝑛𝑃𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛𝑠 [𝑖 ] ← 𝑘𝑛𝑜𝑤𝑛𝑃𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛𝑠 [𝑖 ] ∪ {𝑝𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛[𝑘 ] }; 12
System Invariants: Following Dijkstra’s self-stabilization principles [1], our system maintains key invariants: (I1) Version vector monotonicity: 𝑉𝑉 [𝑖] [ 𝑗] never decreases; (I2) Partition ID minimality: nodes in connected components converge to minimum partition ID; (I3) Ring connectivity: within each partition, successor links form a cycle; (I4) Finger correctness: fingers point to reachable nodes or are marked invalid. These invariants are preserved under gossip and enable convergence proofs.
3.4
Partition Merger Protocol
When the underlying network heals and partitions can communicate: Phase 1 - Detection: Nodes detect when their DHT links (successor, predecessor, fingers) point to nodes in different partitions. These become cross-partition links. Phase 2 - Merger Decision: Use deterministic rule: lowest partition ID wins. All nodes in merging partitions adopt the minimum partition ID. This requires no coordination—each node makes the decision locally. Phase 3 - Convergence: Gossip propagates the new partition assignment. Nodes update their partition ID when they receive gossip from the merged partition. The DHT structure self-repairs as nodes discover new reachable fingers. Version Vector Reconciliation: When merging, version vectors are merged element-wise using
Structured Gossip: A Partition-Resilient DNS for Internet-Scale Dynamic Networks
Algorithm 2: Partition Merger Detection and Execution Input: Node 𝑖 with cross-partition links detected Output: Updated partition assignment // Check if this node is at partition boundary 1 if |𝑐𝑟𝑜𝑠𝑠𝑃𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛𝐿𝑖𝑛𝑘𝑠 [𝑖 ] | > 0 then // Gather all known partition IDs 2 𝑘𝑛𝑜𝑤𝑛𝑃𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛𝑠 [𝑖 ] ← {𝑝𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛[𝑖 ] }; 3 foreach 𝑗 ∈ 𝑐𝑟𝑜𝑠𝑠𝑃𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛𝐿𝑖𝑛𝑘𝑠 [𝑖 ] do 4 𝑘𝑛𝑜𝑤𝑛𝑃𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛𝑠 [𝑖 ] ← 𝑘𝑛𝑜𝑤𝑛𝑃𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛𝑠 [𝑖 ] ∪ {𝑝𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛[ 𝑗 ] };
5
6 7 8 9
10
// Deterministic merger: choose minimum partition ID 𝑡𝑎𝑟𝑔𝑒𝑡𝑃𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛 ← min(𝑘𝑛𝑜𝑤𝑛𝑃𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛𝑠 [𝑖 ] ); // Update partition if different from current if 𝑝𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛[𝑖 ] ≠ 𝑡𝑎𝑟𝑔𝑒𝑡𝑃𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛 then 𝑜𝑙𝑑𝑃𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛 ← 𝑝𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛[𝑖 ]; 𝑝𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛[𝑖 ] ← 𝑡𝑎𝑟𝑔𝑒𝑡𝑃𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛; 𝑝𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛𝑉 𝑒𝑟𝑠𝑖𝑜𝑛[𝑖 ] ← 𝑝𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛𝑉 𝑒𝑟𝑠𝑖𝑜𝑛[𝑖 ] + 1; // Maintain invariant I2: partition ID minimality LogEvent(“Merged P𝑜𝑙𝑑𝑃𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛 into P𝑡𝑎𝑟𝑔𝑒𝑡𝑃𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛”);
SIGMOD ’26, June 22–27, 2026, Philadelphia, PA, USA
the furthest finger for ≈ log 𝑛 others. Each receives gossip from ≈ 𝑛/log 𝑛 senders. □
4.2
Theorem 2. Structured gossip converges in 𝑂 (log2 𝑛) rounds. Proof Sketch: Ring gossip propagates at 𝑂 (𝑛) rate. Finger gossip spreads exponentially: info reaches distance 𝑑 in 𝑂 (log 𝑑) rounds. This matches optimal CHORD routing bounds [13]. Complete coverage requires 𝑂 (log 𝑛) rounds for ring and 𝑂 (log 𝑛) for fingers, yielding 𝑂 (log2 𝑛) total. □
4.3
Input: Node 𝑖 receives 𝑚𝑠𝑔 from node 𝑗 Output: Updated local knowledge and version vector 1 ⟨𝑘𝑛𝑜𝑤𝑛𝑁 𝑜𝑑𝑒𝑠 𝑗 , 𝑉𝑉 𝑗 , 𝑝 𝑗 , 𝑝𝑉 𝑒𝑟𝑠𝑖𝑜𝑛 𝑗 ⟩ ← 𝑚𝑠𝑔; // Merge knowledge sets within same partition 2 if 𝑝 𝑗 = 𝑝𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛[𝑖 ] then 3 foreach 𝑘 ∈ 𝑘𝑛𝑜𝑤𝑛𝑁 𝑜𝑑𝑒𝑠 𝑗 do 4 if 𝑘 ∈ 𝑉 ∧ 𝑝𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛[𝑘 ] = 𝑝𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛[𝑖 ] then 5 𝑘𝑛𝑜𝑤𝑛𝑁 𝑜𝑑𝑒𝑠 [𝑖 ] ← 𝑘𝑛𝑜𝑤𝑛𝑁 𝑜𝑑𝑒𝑠 [𝑖 ] ∪ {𝑘 };
6 7
// Merge version vectors element-wise foreach 𝑛𝑜𝑑𝑒 ∈ (𝑉𝑉𝑖 ∪ 𝑉𝑉 𝑗 ) do 𝑉𝑉 [𝑖 ] [𝑛𝑜𝑑𝑒 ] ← max(𝑉𝑉 [𝑖 ] [𝑛𝑜𝑑𝑒 ], 𝑉𝑉 𝑗 [𝑛𝑜𝑑𝑒 ] ); // Preserves invariant I1: monotonicity
else // Cross-partition message: trigger merger detection 9 𝑐𝑟𝑜𝑠𝑠𝑃𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛𝐿𝑖𝑛𝑘𝑠 [𝑖 ] ← 𝑐𝑟𝑜𝑠𝑠𝑃𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛𝐿𝑖𝑛𝑘𝑠 [𝑖 ] ∪ { 𝑗 }; 10 𝑘𝑛𝑜𝑤𝑛𝑃𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛𝑠 [𝑖 ] ← 𝑘𝑛𝑜𝑤𝑛𝑃𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛𝑠 [𝑖 ] ∪ {𝑝 𝑗 }; 8
11
𝑙𝑎𝑠𝑡𝑈 𝑝𝑑𝑎𝑡𝑒 [𝑖 ] ← currentTime( );
𝑉𝑉𝑚𝑒𝑟𝑔𝑒𝑑 [𝑘] = max(𝑉𝑉1 [𝑘], 𝑉𝑉2 [𝑘]) for all nodes 𝑘. This ensures causal consistency without coordination.
4 Complexity Analysis 4.1 Message Complexity Theorem 1. Structured gossip achieves 𝑂 (𝑛/log 𝑛) messages per round. Proof Sketch: Each node gossips to ≤ 2 targets. The furthest finger points ≈ 𝑛/2 away. By pigeonhole principle, each node is
Partition Resilience
Theorem 3. The merger protocol handles arbitrary concurrent partitions without coordination. Proof: The merger rule 𝑡𝑎𝑟𝑔𝑒𝑡 = min(∪𝑖 𝑃𝑖 ) is deterministic. For nodes 𝑢 ∈ 𝑃𝑖 , 𝑣 ∈ 𝑃 𝑗 that communicate, both compute identical 𝑡𝑎𝑟𝑔𝑒𝑡 since min is commutative and associative. Version vector merging is idempotent and commutative. Cross-partition detection is local. Invariant I2 (partition ID minimality) ensures all nodes converge to single partition ID without global coordination. □
4.4
Algorithm 3: Process Received Gossip Message
Convergence Time
Space Complexity
Per-node state: 𝑂 (log 𝑛) for finger table + 𝑂 (𝑚) for 𝑚 DNS translations + 𝑂 (𝑛) for version vector. In practice, version vectors can be compressed using techniques from [9].
4.5
Eventual Consistency Guarantees
We now formally prove that our passive stabilization protocol guarantees eventual consistency. Definition 1 (Eventual Consistency): A distributed system is eventually consistent if, for any execution where message delivery eventually succeeds and no new updates occur, all nodes eventually converge to the same state. Theorem 4. Structured gossip guarantees eventual consistency for partition membership and version vectors. Proof: We prove this by showing that all state merge operations satisfy the sufficient conditions for eventual consistency: commutativity, associativity, and idempotence. (1) Partition ID Convergence: The merger operation is: 𝑚𝑒𝑟𝑔𝑒 (𝑝 1, 𝑝 2 ) = min(𝑝 1, 𝑝 2 ) This is: • Commutative: min(𝑝 1, 𝑝 2 ) = min(𝑝 2, 𝑝 1 ) • Associative: min(min(𝑝 1, 𝑝 2 ), 𝑝 3 ) = min(𝑝 1, min(𝑝 2, 𝑝 3 )) • Idempotent: min(𝑝, 𝑝) = 𝑝 Therefore, regardless of message ordering, all nodes in communicating partitions converge to the minimum partition ID. (2) Version Vector Convergence: The merge operation for version vectors is element-wise maximum: 𝑉𝑉𝑚𝑒𝑟𝑔𝑒 [𝑘] = max(𝑉𝑉1 [𝑘], 𝑉𝑉2 [𝑘]) for all nodes 𝑘 This is: • Commutative: max(𝑣 1, 𝑣 2 ) = max(𝑣 2, 𝑣 1 ) • Associative: max(max(𝑣 1, 𝑣 2 ), 𝑣 3 ) = max(𝑣 1, max(𝑣 2, 𝑣 3 )) • Idempotent: max(𝑣, 𝑣) = 𝑣 (3) Known Nodes Set: The merge operation for node knowledge is set union: 𝐾𝑛𝑜𝑤𝑛𝑁𝑜𝑑𝑒𝑠𝑚𝑒𝑟𝑔𝑒 = 𝐾𝑛𝑜𝑤𝑛𝑁𝑜𝑑𝑒𝑠 1 ∪ 𝐾𝑛𝑜𝑤𝑛𝑁𝑜𝑑𝑒𝑠 2
SIGMOD ’26, June 22–27, 2026, Philadelphia, PA, USA
This is: • Commutative: 𝐴 ∪ 𝐵 = 𝐵 ∪ 𝐴 • Associative: (𝐴 ∪ 𝐵) ∪ 𝐶 = 𝐴 ∪ (𝐵 ∪ 𝐶) • Idempotent: 𝐴 ∪ 𝐴 = 𝐴 (4) Monotonic Progress: Each gossip round monotonically increases the known nodes set. Since bounded by 𝑛, convergence occurs in finite time—a property formalized in streaming algorithms [15]. (5) Message Delivery: Assume eventual delivery within partitions. By Theorem 2, information spreads in 𝑂 (log2 𝑛) rounds. Combining (1)-(5): All operations are CRDTs [10, 17], guaranteeing eventual consistency. □ Corollary 1: Passive stabilization makes progress in each partition independently; active coordination blocks. Corollary 2: The protocol is partition-tolerant (CAP theorem): available during partitions, eventually consistent when healed.
5
Demonstration
We provide an interactive web-based demonstration at: https:// priyankaiitg.github.io/chordgossip • Create networks of up to 100 nodes with CHORD DHT • Trigger arbitrary network partitions (2-5 partitions) • Visualize gossip message flow along finger links • Observe independent convergence within partitions • Simulate gradual and concurrent mergers • Compare message counts vs. unstructured gossip • Test DNS lookups within and across partitions The visualization shows nodes colored by partition, with green lines for intra-partition links and red dashed lines for detected cross-partition links. Users can observe how information spreads exponentially via finger gossip while ring gossip maintains connectivity. The demo incorporates version vector visualization showing causal ordering similar to techniques used in distributed stream processing [15] and privacy-preserving distributed systems [16].
6
Related Work
DHT Architectures: Symphony [11] pioneered small-world DHT routing with 𝑂 (log 𝑛) hops. Optimal CHORD routing [13] proved tight bounds for structured overlays. Our work extends these with partition resilience. Dynamic Networks: Bawa et al. [14] analyzed consistency-availability tradeoffs in dynamic P2P systems, showing active protocols pay high costs. Our passive approach avoids this. Lookahead in P2P: Manku et al. [12] showed neighbor knowledge accelerates convergence—we exploit this via finger tables. DHTbased DNS: CoDoNS [7] uses CHORD for DNS but lacks partition handling. MANET: Khan et al. [18] address DHT faults in MANETs via replication; we use passive convergence. Original thesis [2] identified issues; our CRDTs [17] solve them.
7
Conclusion
Structured gossip demonstrates that internet-scale partition resilience is achievable through passive stabilization rather than active coordination. By exploiting DHT structure for gossip propagation, we reduce message complexity from 𝑂 (𝑛) to 𝑂 (𝑛/log 𝑛) while maintaining logarithmic convergence time. Our formal proof
Priyanka Sinha and Dilys Thomas
shows that commutative and idempotent state merge operations guarantee eventual consistency without requiring synchronous agreement—a critical property for MANET deployments where partitions are frequent and prolonged. The key insight is that passive stabilization can be both correct and efficient when state operations are carefully designed as conflict-free replicated data types (CRDTs). Unlike active coordination protocols that block during partitions, our approach continues making progress in each partition independently and merges deterministically when network connectivity is restored. Future work includes: (1) compression techniques for version vectors in billion-node deployments, (2) integration with existing DNS infrastructure for backward compatibility, (3) security mechanisms against Byzantine nodes in partition scenarios, and (4) adaptive gossip rates based on partition stability metrics.
References [1] Edsger W. Dijkstra. Self-stabilizing systems in spite of distributed control. Communications of the ACM, 17(11):643–644, November 1974. [2] Priyanka Sinha. Auto-configuration in Multi-hop Mobile ad hoc Networks. Master’s thesis, Auburn University, 2007. [3] Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, and Hari Balakrishnan. Chord: A scalable peer-to-peer lookup service for internet applications. In Proceedings of ACM SIGCOMM, pages 149–160, 2001. [4] Xiaozhou Li, Jayadev Misra, and C. Greg Plaxton. Concurrent maintenance of rings. Technical Report TR-04-36, University of Texas at Austin, 2004. [5] Alan Demers, Dan Greene, Carl Hauser, Wes Irish, John Larson, Scott Shenker, Howard Sturgis, Dan Swinehart, and Doug Terry. Epidemic algorithms for replicated database maintenance. In Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing, pages 1–12, 1987. [6] Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati, Avinash Lakshman, Alex Pilchin, Swaminathan Sivasubramanian, Peter Vosshall, and Werner Vogels. Dynamo: Amazon’s highly available key-value store. In Proceedings of ACM SIGOPS Symposium on Operating Systems Principles, pages 205–220, 2007. [7] Venugopalan Ramasubramanian and Emin Gün Sirer. Beehive: O(1) lookup performance for power-law query distributions in peer-to-peer overlays. In Proceedings of NSDI, volume 4, pages 8–8, 2004. [8] Nicholas J. A. Harvey, Michael B. Jones, Stefan Saroiu, Marvin Theimer, and Alec Wolman. SkipNet: A scalable overlay network with practical locality properties. In Proceedings of USENIX Symposium on Internet Technologies and Systems, 2003. [9] David Ratner, Peter Reiher, and Gerald J. Popek. Roam: A scalable replication system for mobile computing. In Proceedings of the Workshop on Mobile Computing Systems and Applications, pages 96–101, 1994. [10] Marc Shapiro, Nuno Preguiça, Carlos Baquero, and Marek Zawirski. Conflictfree replicated data types. In Proceedings of the 13th International Symposium on Stabilization, Safety, and Security of Distributed Systems, pages 386–400, 2011. [11] Gurmeet Singh Manku, Mayank Bawa, and Prabhakar Raghavan. Symphony: Distributed hashing in a small world. In Proceedings of the 4th USENIX Symposium on Internet Technologies and Systems (USITS), 2003. [12] Gurmeet Singh Manku, Moni Naor, and Udi Wieder. Know thy neighbor’s neighbor: The power of lookahead in randomized P2P networks. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC), pages 54–63, 2004. [13] Prasanna Ganesan and Gurmeet Singh Manku. Optimal routing in Chord. In Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 169–178, 2004. [14] Mayank Bawa, Aristides Gionis, Hector Garcia-Molina, and Rajeev Motwani. The price of validity in dynamic networks. In Proceedings of the ACM SIGMOD International Conference on Management of Data, pages 515–526, 2004. [15] Gurmeet Singh Manku, Mayank Bawa, and Prabhakar Raghavan. Symphony: Distributed hashing in a small world. In Proceedings of the 4th USENIX Symposium on Internet Technologies and Systems (USITS), 2003. [16] Rakesh Agrawal, Ramakrishnan Srikant, and Dilys Thomas. Privacy preserving OLAP. In Proceedings of the ACM SIGMOD International Conference on Management of Data, pages 251–262, 2005. [17] Paulo Sérgio Almeida. Approaches to conflict-free replicated data types. arXiv:2310.18220, October 2023. [18] Najeeb Khan, Kashif Naseer Qureshi, Gwanggil Jeon, and Rajesh Kumar. Fault tolerant DHT-based routing in MANET. Sensors, 22(11):4280, June 2022.