Peer-to-Peer Architectures

A peer-to-peer (P2P) architecture is a distributed system in which participating hosts, called peers, act symmetrically as both clients and servers, contrasting with the Client-Server Model where roles are fixed and asymmetric. Peers form an overlay network: a logical graph built on top of the physical Application Layer and Security internet, where an edge represents an application-level connection (a TCP socket opened via ordinary Socket Programming Fundamentals) rather than a physical link. The overlay's topology and the rules for routing messages across it define the P2P system's essential character. Overlays split into two families. Unstructured overlays impose no relationship between a peer's identifier, its neighbors, and the data it stores; a peer connects to some arbitrary set of neighbors (often discovered via a bootstrap server or gossip), and content can be placed anywhere. Locating content requires search — flooding a query outward, or performing random walks — with no guarantee on cost or even success. Structured overlays instead impose an algebraic structure: both peers and data keys are mapped into a common identifier space (typically via a hash function), and the overlay topology is built so that this space can be navigated efficiently. The canonical structured overlay is the distributed hash table (DHT), which offers the interface of a hash table — `put(key, value)`, `get(key)` — implemented cooperatively across thousands of unreliable machines with no single point of failure and no central lookup table. A third pattern, exemplified by BitTorrent, is swarming content distribution: rather than locating a single copy of a file, peers cooperate to reconstruct one file from many small pieces obtained from many different peers simultaneously, turning a large download into a many-to-many exchange that gets faster, not slower, as more peers join. BitTorrent uses a hybrid architecture — a semi-centralized tracker or a DHT for peer discovery, and a fully decentralized, unstructured swarm for the actual data transfer — illustrating that real systems mix these ideas rather than choosing one purely.

Unstructured overlays: flooding and random walks

In a Gnutella-style unstructured overlay, a new peer bootstraps by contacting a small number of known "well-known" hosts, obtains a handful of neighbors, and joins the overlay graph. To find content, it issues a query that is flooded: forwarded to all neighbors, each of which forwards it to their neighbors, up to a time-to-live (TTL) bound to prevent infinite propagation. ``` FUNCTION FLOOD_QUERY(query, ttl, origin, seen_ids): IF query.id IN seen_ids: RETURN // avoid re-processing loops ADD query.id TO seen_ids IF LOCAL_STORE contains query.key: SEND result TO origin (via reverse path) IF ttl == 0: RETURN FOR each neighbor IN NEIGHBORS: IF neighbor != incoming_link: SEND (query, ttl - 1) TO neighbor ``` This guarantees discovery of any reachable content within TTL hops but the message cost grows exponentially with the branching factor of the overlay graph — a query with fan-out $d$ and TTL $t$ generates up to $O(d^t)$ messages, which does not scale. Random-walk search trades completeness for cost: a query takes $k$ independent random walks of bounded length instead of flooding, reducing message volume to $O(k \cdot \text{length})$ at the cost of a chance of missing existing content. Neither approach gives a bound on lookup cost relative to network size $n$; this is the fundamental limitation structured overlays are built to remove.

Distributed hash tables: the structured answer

A DHT assigns every peer and every data key an identifier in the same space, usually the output of a hash function such as SHA-1, giving an $m$-bit identifier space of size $2^m$. Both peer IDs (hash of IP\:port) and key IDs (hash of content name) live in this space, and a globally agreed rule — "key $k$ is owned by the peer whose ID is closest to $k$" — determines placement without any central authority. This is the DHT analogue of consistent hashing: when a peer joins or leaves, only the keys mapped to it need to move, not the entire table.

Chord arranges the identifier space $[0, 2^m)$ as a logical ring. A key $k$ is stored at its successor: the first peer whose ID is $\geq k$ (wrapping around). Each peer maintains:

• a successor pointer (its neighbor clockwise on the ring) and predecessor pointer;
• a finger table of up to $m$ entries, where the $i$-th finger points to the successor of $(n + 2^{i-1}) \bmod 2^m$.

The finger table is what makes lookup fast: it lets a peer jump roughly halfway across the remaining distance to the target on every hop, exactly like binary search over the ring. ``` FUNCTION FIND_SUCCESSOR(n, key): IF key IN (n.id, n.successor.id]: // key falls in this peer's range RETURN n.successor ELSE: n' = CLOSEST_PRECEDING_FINGER(n, key) IF n' == n: RETURN n.successor // fallback: no finger helps, walk one step RETURN FIND_SUCCESSOR(n', key) // recurse/forward at n' FUNCTION CLOSEST_PRECEDING_FINGER(n, key): FOR i FROM m DOWN TO 1: f = n.finger[i].node IF f IN (n.id, key): // f strictly between n and key on the ring RETURN f RETURN n ```

Joining and stabilization. A new peer $p$ computes its ID, contacts any existing peer to find its correct successor via `FIND_SUCCESSOR`, and inserts itself between its predecessor and successor. Because peers churn constantly, Chord runs a periodic background protocol, stabilize, so that successor pointers self-heal even if joins happen concurrently: ``` FUNCTION STABILIZE(n): x = n.successor.predecessor IF x IN (n.id, n.successor.id): n.successor = x // a new node inserted itself between n and old successor NOTIFY(n.successor, n) // tell successor "I might be your predecessor" FUNCTION NOTIFY(n, candidate): IF n.predecessor IS NULL OR candidate IN (n.predecessor.id, n.id): n.predecessor = candidate FUNCTION FIX_FINGERS(n): i = RANDOM(1, m) n.finger[i].node = FIND_SUCCESSOR(n, n.id + 2^(i-1)) ``` Every peer also runs `FIX_FINGERS` periodically to keep finger tables approximately correct as membership changes, and pings its predecessor to detect and route around failures. The key correctness claim — proved below — is that as long as successor pointers are eventually correct, lookups always terminate correctly even with somewhat stale finger tables.

Kademlia, used by BitTorrent's trackerless mode, Ethereum, and IPFS, uses the same big idea with a different metric: distance between IDs is XOR distance, $d(a,b) = a \oplus b$, and each peer keeps $k$-buckets — small lists of known peers at each level of XOR distance — instead of a single ring. XOR distance is symmetric and satisfies the triangle inequality, which lets Kademlia's iterative lookup converge without the wraparound bookkeeping Chord needs, while giving the same asymptotic $O(\log n)$ hop count and added resilience because each bucket holds several candidate contacts rather than one.

BitTorrent: swarming content distribution

BitTorrent solves a different but related problem: distributing one large file to many downloaders as fast as possible, rather than storing arbitrary key-value pairs. A file is split into fixed-size pieces (commonly 256 KB–4 MB), each further split into smaller blocks for transfer; a `.torrent` metadata file (or its magnet-link equivalent) records the SHA-1 hash of every piece, so any peer can verify a piece's integrity independently of who sent it. A peer joining a swarm (the set of peers sharing one torrent) discovers other peers via a tracker (a server that maintains swarm membership) or via a Kademlia-based trackerless DHT. Two algorithmic ideas make the swarm efficient: 1. Rarest-first piece selection. Each peer requests the piece that is least common among its currently connected neighbors first. This spreads rare pieces throughout the swarm quickly, so that no single peer holding a rare piece becomes a bottleneck, and it maximizes the diversity of pieces available for trading. 2. Tit-for-tat choking. A peer uploads primarily to the neighbors currently giving it the best download rate ("unchoking" a fixed number, e.g. 4, of its best providers) and periodically optimistically unchokes one random neighbor to discover potentially better partners and let newcomers with nothing to trade bootstrap into the system. ``` FUNCTION PIECE_SELECTION(peer): candidates = pieces NOT YET owned BY peer availability = COUNT(candidates, across all connected neighbors) RETURN argmin(availability) // rarest piece among candidates FUNCTION CHOKING_ALGORITHM(peer, all_neighbors): EVERY 10 seconds: ranked = SORT(all_neighbors BY download_rate_to_me, DESC) unchoke(top 4 of ranked) choke(the rest) EVERY 30 seconds: pick random neighbor NOT already unchoked optimistically_unchoke(that neighbor) ``` This game-theoretic design approximates a repeated Prisoner's Dilemma: peers that reciprocate uploads get reciprocated uploads back, discouraging free-riding (downloading without uploading) without requiring any central enforcement, currency, or trusted third party. ```:svg[Structured (Chord ring) vs. unstructured (flooding) overlay lookup] ```

Unstructured flooding. With branching factor $d$ (average neighbor count) and TTL $t$, the number of messages generated is $O(d^t)$ in the worst case (a tree with no overlap), giving no usable bound in terms of network size $n$ — this is why real deployments cap TTL aggressively and accept incomplete search. Random-walk search with $k$ walkers of length $\ell$ generates $O(k\ell)$ messages and succeeds with probability depending on content popularity; neither method offers a worst-case guarantee tied to $n$, which is the structural weakness structured overlays fix.

Chord lookup correctness and cost. Chord's central correctness claim is: > If every peer's successor pointer is eventually correct (points to the true successor on the ring), then `FIND_SUCCESSOR` always terminates and returns the correct owner of any key, regardless of the current state of finger tables. *Proof sketch. At each recursive call, `FIND_SUCCESSOR(n, key)` either returns immediately because `key` lies in $(n, n.successor]$, or forwards to some node $n'$ that is strictly closer to `key` (in clockwise ring distance) than $n$ is — because `CLOSEST_PRECEDING_FINGER` only returns nodes falling strictly between $n$ and `key`, and if no finger qualifies, the algorithm still falls back to `n.successor`, guaranteeing forward progress. Since ring distance to the target strictly decreases (a natural number bounded below by 0) at every hop, and there are at most $n$ peers on the ring, the recursion terminates in at most $n$ hops even with completely empty or wrong finger tables — correctness never depends on fingers being accurate, only on successor pointers being eventually correct. Fingers only affect speed, not correctness. $\blacksquare$ Speed argument.* With correct finger tables, each hop using finger $i$ at least halves the remaining clockwise distance to the key (finger $i$ points roughly $2^{i-1}$ steps ahead, and the algorithm always picks the largest finger that does not overshoot). Since the ring has $2^m$ points, distance can be halved at most $m = O(\log(2^m))$ times before reaching the target, giving expected lookup cost:

hops, each requiring one round-trip message, so lookup latency is $O(\log n)$ messages and the same in asymptotic time (assuming bounded per-hop latency). Each peer stores $O(\log n)$ finger-table entries, so per-node space is $O(\log n)$ and total overlay state is $O(n \log n)$. Join/leave operations require updating $O(\log n)$ fingers on average across the network via the periodic `FIX_FINGERS` and `STABILIZE` protocols, and the number of keys that must be re-owned when a peer joins or leaves is, in expectation, $O(K/n)$ for $K$ total keys — this is exactly the consistent-hashing guarantee that only a small local fraction of data moves per membership change.

Kademlia achieves the same $O(\log n)$ hop bound using XOR-metric $k$-buckets; its practical advantage is that lookups proceed iteratively with $\alpha$ parallel queries (typically 3) rather than Chord's strictly sequential recursive hops, reducing wall-clock latency, and its bucket structure (keeping multiple live contacts per distance range, preferring long-lived peers) makes it more robust to churn without an explicit periodic stabilization protocol.

BitTorrent efficiency. The swarm's aggregate download throughput scales roughly linearly with the number of well-seeded peers, because each peer contributes upload capacity, unlike single-server distribution where capacity is fixed. Rarest-first selection is a greedy heuristic; it does not carry a strict worst-case optimality proof, but it provably avoids the "last piece problem" pathology better than random selection because it keeps piece-availability roughly balanced across the swarm, empirically shown to minimize the expected time until every piece exists somewhere reachable. Tit-for-tat choking is not incentive-compatible in the strict game-theoretic sense (colluding or modified clients can exploit optimistic unchoking), which is an honest, known limitation rather than a proven guarantee.

Tradeoffs, honestly stated. Structured overlays guarantee lookup bounds but require maintaining consistent global structure under churn, adding protocol complexity (stabilization, finger repair) and vulnerability to certain routing-table poisoning attacks. Unstructured overlays are trivially robust to churn and require no invariant maintenance, at the cost of unbounded or probabilistic search. BitTorrent-style swarming is excellent for one-to-many bulk distribution of large, popular, static files, but poorly suited to small or highly dynamic content, or exact-match lookup of arbitrary keys — that remains the DHT's job.

Consider a small Chord ring with $m = 4$ bits (identifier space $0$–$15$) and five peers currently at IDs $\{1, 4, 9, 11, 14\}$. We trace looking up key $k = 12$ starting from peer $N1$.

(Finger targets are computed as $(n + 2^{i-1}) \bmod 16$; entries above show the illustrative successor for that target, with the understanding that a real table stores exact successor pointers computed at construction time.)

Trace of `FIND_SUCCESSOR(N1, 12)`: 1. At N1: is $12 \in (1, 4]$? No. Call `CLOSEST_PRECEDING_FINGER(N1, 12)`. Scan fingers from largest: finger[4] points to a node at/around id 9–11 which lies strictly between 1 and 12 — take the largest finger whose node is in $(1, 12)$, which resolves to N9 (finger[3], node at id 9). Forward to N9. 2. At N9: is $12 \in (9, 11]$? No. `CLOSEST_PRECEDING_FINGER(N9, 12)`: finger pointing to N11 falls in $(9, 12)$ and is the largest such — forward to N11. 3. At N11: is $12 \in (11, 14]$? Yes. Return N14 as the owner of key 12. Total hops: 3, consistent with $O(\log n) = O(\log 5) \approx 2.3$, rounding to the expected small-constant number of hops for a tiny ring — the bound is asymptotic, so small rings will show modest constant overhead. Each hop halved (or more) the remaining clockwise distance to 12: from N1 the distance was 11, after N9 it was 3, after N11 it was 1 — well within the "roughly halves each time" guarantee, and it terminates correctly at N14, exactly the peer with the smallest ID $\geq 12$.

BitTorrent trace. Suppose a swarm has one seeder (peer $S$, has all pieces) and three leechers $A$, $B$, $C$ join staggered. Piece availability starts uniform (only $S$ has anything), so rarest-first is moot initially; $A$ downloads piece 3 from $S$, $B$ downloads piece 7, $C$ downloads piece 1 — the tracker or DHT spreads requests so early pieces diverge. Once $A$, $B$, $C$ have distinct pieces, rarest-first now matters: $A$ sees that $B$ has piece 7 (rare, since only $S$ and $B$ have it) and requests it from $B$ rather than a common piece, so piece 7 quickly gets a third copy in the swarm. Choking: after 10 seconds, $S$ observes it is uploading to $A$, $B$, $C$ roughly equally and unchokes all three (fewer than 4 neighbors, so no choking needed yet); as the swarm grows past 4 active leechers, $S$ begins to choke the slowest downloaders and optimistically unchoke a random newcomer every 30 seconds, giving new peers a foothold even before they have anything to trade.

:::warning[Every peer that forwards queries or serves pieces to strangers is also a reflector: unauthenticated P2P protocols (flooding, DHT lookups, tracker responses) can be abused to amplify traffic toward a victim who never asked for it, a direct precursor to the reflection/amplification techniques covered under DDoS Attacks and Mitigation.]

BitTorrent remains one of the most efficient mechanisms ever deployed for distributing large files — Linux distributions, game patches, and research datasets are routinely seeded this way specifically because swarm throughput scales with demand rather than collapsing under it. Kademlia-style DHTs run inside every major blockchain's peer-discovery layer (Ethereum's devp2p, Bitcoin's address gossip descendants), inside the InterPlanetary File System for content-addressed storage, and inside Bittorrent's Mainline DHT, which lets clients find peers for a torrent with no tracker at all. Skype's early architecture used "supernodes" — a structured hybrid overlay — to route calls without centralized switching infrastructure. Content delivery networks and consistent-hashing-based storage systems (Amazon Dynamo, Apache Cassandra) borrow Chord's consistent-hashing ring directly, even though those systems are operated by a single organization rather than being fully open peer-to-peer, showing how the core algorithmic idea outlived its original decentralized-internet motivation. Understanding how P2P overlays forward traffic on behalf of strangers is also the necessary foundation for reasoning about the abuse of that same openness, the subject taken up under DDoS Attacks and Mitigation.

Ask the tutor: How would you modify Chord's stabilization protocol to tolerate simultaneous joins and failures without ever returning an incorrect lookup?