Kademlia

Maymounkov & Mazières’s (2002) Distributed Hash Table organised around the XOR Metric on identifier space, with k-buckets biased toward long-lived nodes, iterative parallel lookups, and opportunistic routing-table maintenance. The DHT underlying BitTorrent Mainline, IPFS / libp2p, Ethereum Discv4/Discv5, Tor hidden services, I2P, and most production P2P systems.

In this vault

Backlinks

Linked Pages

Gossiping in Distributed Systems

Reference: Anne-Marie Kermarrec, Maarten van Steen (2007). ACM SIGOPS Operating Systems Review, Vol. 41, No. 5. Source file: Gossiping_in_distributed_systems.pdf. URL

Summary

This tutorial surveys the “gossip revival” in distributed systems, providing a unifying framework for reasoning about the broad space of gossip-based protocols now used far beyond their original role as epidemic reliable multicast. The authors organize gossip protocols by three crucial parameters: peer selection (who to talk to), data exchanged (what to send), and data processing (what to do with what arrives); varying these three gives rise to dissemination, peer sampling, aggregation, overlay/topology construction, resource monitoring, and slicing protocols.

They illustrate each axis with canonical examples — Lpbcast and Newscast for membership, Push-Sum and T-Man for aggregation and overlay construction, Astrolabe for monitoring — and highlight why gossip’s randomized, local-only interactions produce emergent convergent global behavior with exceptional robustness to churn and failures. The paper emphasizes gossip’s use in convergent, not just divergent (epidemic) behaviors.

Key Ideas

Three-parameter gossip framework: peer selection, data exchanged, data processing.
Applications: dissemination, peer sampling, aggregation, topology construction, monitoring, slicing.
Convergent behavior from local random pairwise exchanges.
Peer sampling service is the common substrate most gossip protocols assume.
Robustness through probabilistic redundancy and randomization.

Connections

Conceptual Contribution

Claim: The sprawling family of gossip-based algorithms can be unified as a three-parameter design space — peer selection, data exchanged, data processing — and the same substrate supports not just epidemic dissemination but convergent behaviours including aggregation, overlay construction, and monitoring.
Mechanism: Presents a generic active/passive-thread gossip skeleton; classifies protocols along the three parameters with canonical instances (Lpbcast, Newscast, Cyclon, T-Man, Push-Sum, Astrolabe, GEMS); highlights how peer-sampling acts as the common foundational service enabling higher-level applications.
Concepts introduced/used: Gossip Framework, Peer Selection, Data Exchange, Data Processing, Peer Sampling Service, Convergent Gossip, Epidemic Dissemination, Overlay Construction
Stance: survey
Relates to: Provides the taxonomy that situates Gossip-based Aggregation in Large Dynamic Networks (aggregation), Gossip-Based Computation of Aggregate Information (Push-Sum), Myconet Fungi Inspired Superpeer Overlay (topology construction), and the gossip-training mode surveyed in Edge Intelligence Survey. Anchor for Gossip Protocols hub.

IPFS - Content Addressed, Versioned, P2P File System

Reference: Juan Benet (2014). arXiv:1407.3561 (DRAFT 3). Source file: downloads/ipfs_benet.pdf. URL

Summary

Original whitepaper introducing the InterPlanetary File System (IPFS), a peer-to-peer hypermedia protocol that synthesises ideas from Git (Merkle-DAG object model), BitTorrent (incentivised block exchange via BitSwap), DHTs (Kademlia-based routing), and self-certifying file systems (SFS) into a single content-addressed distributed file system. Objects are referenced by the cryptographic hash of their contents, giving intrinsic integrity, deduplication, and location independence.

The design stack layers an identity/peer-routing layer (S/Kademlia DHT), a block exchange layer (BitSwap with tit-for-tat credit), an object graph layer (Merkle-DAG with links), a naming layer (IPNS for mutable pointers signed by keys), and application-level filesystem semantics. The paper positions IPFS as the substrate for a “permanent web” where content survives independent of any particular host.

Key Ideas

Content addressing: name = hash(content) -> intrinsic integrity, dedup, cacheability
Merkle-DAG as universal object model spanning files, directories, commits
BitSwap: BitTorrent-like block trading generalised beyond single swarms
Kademlia DHT for peer and content routing
IPNS: mutable pointer namespace via signed records keyed to public keys
Self-certifying paths and location-independent fetching

Connections

Conceptual Contribution

Claim: A single peer-to-peer protocol layered over Merkle-DAG content addressing can unify the roles played today by HTTP, Git, BitTorrent, and CDNs, yielding a permanent, decentralised, versioned web.
Mechanism: Five-layer stack — S/Kademlia DHT for identity/routing, BitSwap for incentive-compatible block exchange, Merkle-DAG for the object graph, IPNS for mutable naming via signed records, and filesystem-level conventions above that. All objects are referenced by their SHA-2 multihash, so any peer can serve any object and clients can verify it independently.
Concepts introduced/used: Content-addressed Storage, Merkle-DAG, Gossip Protocols, BitSwap, IPNS, Self-certifying paths, Peer Sampling Service, Hypermedia
Stance: engineering / systems
Relates to: Directly underpins the distribution story for Protocol Documents in A Scalable Communication Protocol for Networks of LLMs — Agora PDs are hash-identified and can be served over any content-addressed store, of which IPFS is the canonical example. Shares the decentralised-naming motivation with Decentralized Identifiers and the self-organising-overlay motivation with Myconet Fungi Inspired Superpeer Overlay.

In this vault

k-Buckets

Kademlia’s routing table structure: each node maintains bits (typically 160) k-buckets, where the i-th bucket holds up to k (typically 20) known peers whose XOR-distance from this node has its highest bit at position i. A peer for the i-th bucket shares an i-bit common prefix with the local node and differs at bit i+1. The least-recently-seen eviction policy biases bucket membership toward long-lived nodes, providing resilience against churn-based and Sybil-style attacks.

In this vault

XOR Metric

The distance function d(x, y) = x ⊕ y (interpreted as an unsigned integer) on k-bit identifiers, used as the routing distance in Kademlia. Symmetric (d(x,y) = d(y,x)), satisfies the triangle inequality, and uniquely unidirectional: for any point x and any distance d, there is exactly one point y at distance d from x. This unidirectionality eliminates the asymmetry of Chord’s clockwise routing and is what makes Kademlia’s routing tables symmetric (nodes that route through us also know us).

In this vault

Kademlia

In this vault

Structured Overlay

A peer-to-peer network whose topology is imposed by an algorithm (typically the DHT routing rule) rather than by ad-hoc peer-discovery — each node maintains a small, deterministic set of neighbour pointers chosen so that lookups can be routed in O(log N) hops. Examples: Chord (ring + finger table), Kademlia (XOR metric + k-buckets), Pastry, Tapestry, CAN. Contrast with unstructured gossip overlays in which neighbour selection is random or epidemic and lookup is by flooding.

In this vault

Consistent Hashing

Karger et al.’s (1997) hashing scheme in which the addition or removal of a single bin causes only 1/n of the keys to be remapped (vs the entire keyspace under naive modular hashing). The mechanism: hash both keys and bins onto a circular space; each key is assigned to the closest bin clockwise. Foundational for Chord and DHTs generally, and for production load balancers (HAProxy, Varnish, Memcached’s ketama, Discord’s gateway sharding).

In this vault

Distributed Hash Table

A class of decentralised key-value stores in which data is partitioned across a self-organising network of nodes via Consistent Hashing and a structured overlay routes lookups in O(log N) (or thereabouts) hops. Canonical members: Chord, Kademlia, Pastry, Tapestry. The structured-overlay counterpart of unstructured gossip — DHTs win for lookup with predictable cost; gossip wins for aggregation and dissemination under high churn. DHTs underlie IPFS, Ethereum discovery, BitTorrent’s Mainline DHT, and most P2P content-addressing infrastructure.