1. What Peer-to-Peer Is#

Peer-to-peer became widely known in the early 2000s through file-sharing applications, which at their peak accounted for roughly two-thirds of all internet traffic. That share has since fallen (streaming services replaced much of the demand), though the growing fragmentation of streaming platforms has been credited with a partial revival. Our interest, however, is not the applications themselves but P2P as a paradigm for designing distributed systems: understanding when a peer-to-peer architecture fulfills a system’s requirements better than the alternatives.

The paradigm pays off precisely because edge resources have grown steadily richer, above all in connectivity. Depending on the application, a P2P system can pool different kinds of resource:

• Network bandwidth: for downloading and distributing files;
• Storage space: for distributed data stores;
• Processing cycles, e.g. the distributed computation that secures a blockchain ledger.

2. Client-Server vs. Peer-to-Peer#

The two paradigms sit at opposite ends of a spectrum. In client-server there are two distinct roles: servers provide the service (hosted in data centers) and clients merely consume it, contributing nothing back. Almost every familiar web application follows this pattern. In peer-to-peer the distinction between server and client is blurry or absent: every node contributes to the service in some way.

The client-server model has four structural weaknesses, all of which P2P is meant to address:

Problem	Description
Scalability	More clients raise the load on the server without adding resources; the new clients’ idle compute and network capacity go unexploited.
Single point of failure	If the server infrastructure goes down (e.g. an AWS outage), the whole service fails, however many clients are still connected.
Centralized administration	The system needs dedicated management; there is no self-adaptive protocol.
Wasted edge resources	Client-side processing, storage, and memory sit unused.

Peer-to-peer trades these for a different set of properties, and a harder engineering problem:

• Autonomy: each node acts independently and participates through decentralized protocols.
• Unreliability: nodes cannot be controlled or trusted; they may fail or behave unpredictably.
• Heterogeneity: nodes differ widely in compute, storage, and connectivity.
• Dynamicity (churn): nodes join and leave unpredictably, so protocols must tolerate constant topology change.
• Scale: a P2P system may span a very large number of edge nodes.

These characteristics make P2P protocols inherently more complex than client-server ones, but also more resilient and more scalable under the right conditions.

3. The Overlay Network#

In a client-server system clients connect to a known server. In P2P, peers connect to each other, typically over TCP links, forming a logical network on top of the physical infrastructure. This logical network is the overlay network.

The overlay does not necessarily reflect the physical topology of the internet, and this has real consequences. Two nodes may be neighbours in the overlay yet physically far apart, so a single overlay hop incurs high latency; conversely, physically close nodes may be many overlay hops apart. Building the overlay with the physical topology and latency in mind can markedly improve performance, and doing so is a central design consideration.

4. Locating Resources: Search vs. Lookup#

The core challenge for a P2P file-sharing system is locating resources spread across many nodes: finding the node(s) that hold a copy of a given resource so it can be downloaded directly. Two retrieval operations must be kept distinct, because they determine which protocols are applicable.

What is returned also varies. Returning the actual data through the overlay is only sensible for a lookup (a search returns many items, so shipping them all through the overlay is impractical); returning a reference (a pointer to the node that holds the data, which the client then contacts directly) is the more common choice and works for both search and lookup.

The rest of the chapter walks the spectrum of designs, from a fully centralized index to a fully decentralized structured overlay.

5. Centralized Index: Napster#

The first major approach used a centralized index, exemplified by Napster. Each peer keeps its own files locally; nothing is uploaded to a server. On joining, a peer publishes to the central server the list of files it owns (identifiers and metadata, not the files). To retrieve something, a client sends its query to the server, which performs the search and returns the addresses of peers that hold matching files; the client then downloads directly from a peer.

This is a hybrid: centralized for search, peer-to-peer for storage and transfer. The original legal argument, that a server holding no content could not be liable for copyright infringement, did not hold up in practice. Its trade-offs are those of any centralized design:

• Advantages: simple to build; a well-defined search scope (one known address that always answers); expressive queries (full-text metadata search), since the server does all the matching.
• Disadvantages: a single point of failure and, crucially, of control (it was easy to shut Napster down, legally and technically); and a scalability bottleneck, since the server must keep state for all clients and process every query.

6. Query Flooding: Gnutella#

At the opposite extreme, query flooding removes any central authority. The best-known example is Gnutella.

6.1 Building and joining the overlay#

With no central server, nodes must discover one another. The design aims for a moderate, balanced degree at every node: too few connections and a node risks disconnection when its neighbours leave; too many and it drowns in traffic. Joining proceeds as follows:

1. Anchor nodes. A newcomer must know the address of at least one participant. These addresses are shared out-of-band (e.g. on web forums) as maintained lists.
2. Ping. On connecting to an anchor, the newcomer sends a ping, which is flooded: each node forwards it to all neighbours except the sender, discarding duplicates so no loop forms.
3. Pong. Nodes willing to accept a connection reply with a pong along the reverse path; a node with fewer current connections replies with higher probability. This probabilistically evens out the degree across the network.
4. Connect. The newcomer opens links to the responders and becomes part of the overlay.

A time-to-live (TTL) field bounds how far each message propagates, preventing unbounded flooding.

6.2 Publishing and querying#

Publishing does nothing beyond marking local files available, there is no distributed registration. To find a resource, a node floods a query through the overlay; each node checks its own files and replies (along the reverse path) on a match. Queries can be arbitrarily expressive, because each node searches only its local files.

• Advantages: fully decentralized (no single point of failure or control); all client and file state stays local; expressive queries at low per-node cost; processing distributed across all nodes.
• Disadvantages: very high traffic, with an average degree $C$ and depth $D$, a single search generates on the order of $C \cdot D$ request messages; no guarantee that an existing file is found (the TTL may cut the search short); a worst-case search scope of $O(N)$; and high latency, since overlay hops may cross long physical distances.

7. Super-Peers: A Hybrid Overlay#

Between Napster’s single index and Gnutella’s full flood lies the super-peer (hierarchical) architecture, used by Kazaa (a proprietary protocol, studied by reverse engineering). The network splits into two tiers.

• Ordinary clients behave like Napster clients: they connect to a super-peer and submit their file metadata.
• Super-peers collectively maintain the distributed index and run a Gnutella-style flooding protocol among themselves: but the search scope is small, because super-peers are a small subset of all nodes.

Super-peers are chosen for connectivity (high bandwidth to carry the extra traffic), processing power (faster, lower-latency searches), network diversity (geographic spread, to keep each super-peer close to its clients), and availability (stable nodes keep the overlay robust; a flapping super-peer reintroduces the instability of pure flooding). Kazaa is believed to have selected super-peers with attention to the physical topology.

In operation, a protocol monitors node behaviour and proposes super-peer candidates (which may accept the role); ordinary clients publish their metadata to one or more super-peers; that information is propagated redundantly among super-peers; queries are flooded only across the super-peer sub-network; and downloads happen directly between peers, possibly split across several sources at once (as in eMule/eDonkey). From the user’s viewpoint the complexity is hidden, installing the software is all that is required, and the protocol decides automatically whether a node becomes a super-peer. (In pure Gnutella, every node is effectively a super-peer.)

The hybrid keeps the best of both worlds, the robustness of decentralization with the efficiency of a compact index, plus the ability to pick reliable, well-connected super-peers and to respect physical locality. It still offers no hard guarantees: retrieval remains probabilistic, and heavy super-peer churn degrades it toward pure flooding.

8. Collaborative Distribution: BitTorrent#

BitTorrent addresses a different problem: not how to find a resource, but how to download it efficiently and fairly once the set of peers holding it is known. Discovery is out-of-band, through torrent files obtained from dedicated websites; a torrent file carries metadata and the address of a tracker, a (centralized) service that lists the peers currently exchanging a given file.

The problem BitTorrent targets is free riders: in a fully decentralized system, nodes tend to download without uploading. Earlier systems tried to discourage this with social pressure (Napster), mandatory-but-unverified sharing (Direct Connect), or credit systems that modified clients easily circumvented (eMule/Kazaa). BitTorrent instead builds in a game-theoretic incentive that makes free-riding structurally unattractive. Two ideas make it work:

• Chunking. Each file is split into fixed-size chunks (~256 KB). A peer can download different chunks from different peers simultaneously, and can start uploading a chunk as soon as it holds it: before it has the whole file.
• Tit-for-tat via choking. Choking is a temporary refusal to upload to a peer. A node continuously measures the download rate it receives from each connection (over a rolling ~20-second average) and, roughly every 10 seconds, keeps uploading (unchokes) to the peers that give it the most, and chokes the rest. Each node also keeps one optimistic unchoke slot, a peer it uploads to regardless of return, rotated about every 30 seconds, which lets newcomers (who have nothing to offer yet) bootstrap, and helps discover better connections.

This “I share with you if you share with me” strategy is self-reinforcing: contributors attract better connections, download faster, and can contribute more, while free riders get choked out. It approximates Pareto efficiency, two peers both getting poor rates can start trading with each other and both improve, though Pareto efficiency is a weak optimality notion (it only rules out unexploited mutually beneficial trades). Chunk selection follows a rarest-first rule: prioritize the chunk fewest peers hold, which prevents bottlenecks and maximizes redundancy so the full file remains reconstructable even after the original seeders leave.

Once a node has the complete file it becomes a seed: it only uploads and is not subject to choking (it needs nothing in return). The tit-for-tat mechanism applies to nodes that still lack the full file, precisely those with an incentive to collaborate. BitTorrent is the most durable P2P protocol in practice (used for game updates, Linux distributions, and any case where many clients want a large file at once, the worst case for a central server), but it provides no integrated search, relies on a centralized tracker (single point of failure/control, though DHT-based trackerless variants exist), and gives only probabilistic performance.

9. Secure Storage: Freenet / Hyphanet#

Freenet (now Hyphanet) targets not download efficiency but censorship resistance and publisher anonymity. Its application model is a decentralized web: users browse pages by address, but no authority can take a page down. Its design goals are censorship resistance (no single authority can delete content), publisher anonymity (the author cannot be traced), and plausible deniability for storage contributors (a node storing a chunk does not know what it contains).

The key move is to decouple owners from storage. In every earlier system, a publisher also stores its file locally and can be identified as the owner. Freenet breaks that link: all data is encrypted and split into chunks, distributed across storage volunteered by participating nodes (say, 10 GB of disk). A contributing node does not know which pages sit in its space and usually lacks the decryption key, so it cannot read, and cannot be held responsible for, what it stores. To read a page a user needs two things, obtained out-of-band: the page identifier and the decryption key.

Identifiers are secure cryptographic hashes of the content. This makes it computationally infeasible to produce different content with the same identifier, so no one can substitute malicious content under a legitimate address, a property we will meet again in structured DHTs.

Routing uses steepest-ascent hill-climbing with backtracking. Each node keeps an approximate routing table, learned from prior traffic, recording which neighbours tend to hold keys near which values, plus its own local data. A query is forwarded to the neighbour whose table suggests keys closest to the target; on a dead end the search backtracks to the next-best option. When the chunk is found it travels back along the reverse path, and each intermediate node may cache it (LRU policy) and add a routing entry. Because chunks with similar keys cluster along the same paths, lookups take few hops despite the network’s size, a small-world effect. Publishing works identically: the publisher routes toward the key and the content is pushed along the resulting path, cached at intermediate nodes, so the publisher does not know where it ends up.

Storage is an LRU cache, so persistence is emergent, not guaranteed: popular content replicates widely and persists; content nobody reads is eventually evicted. This makes censorship self-defeating, searching for a file in order to delete its copies actually spreads it further, since the search caches it along the path. Publishers stay anonymous yet can sign content with a private key, so readers can verify that successive versions of a page come from the same (anonymous) source, an anonymous newspaper readers can trust. Finally, all inter-node traffic uses fixed-size encrypted packets (padded as needed), defeating traffic analysis.

10. Structured Overlays: DHTs and Chord#

Every unstructured approach so far, flooding, super-peers, Freenet’s approximate routing, shares one limitation: no guaranteed performance bounds. The number of hops to find a resource is probabilistic, and there is no certainty the resource is found at all. Structured P2P removes this by deliberately maintaining a defined overlay topology, then exploiting that structure to navigate with provable guarantees.

10.1 The DHT abstraction#

The stored value can be the resource itself or a pointer to the node that holds it. Chord (early 2000s) is the canonical structured DHT and the reference design for the family.

10.2 The Chord ring#

Both nodes and items receive identifiers from the same space, $m$-bit integers, i.e. $0 \dots 2^m - 1$, usually the hash of the node’s IP address and the hash of the item, respectively. Nodes are arranged in a circular ring ordered by identifier. The item with key $k$ is managed by its successor: the node with the smallest id $\ge k$ (modulo the ring). Equivalently, each node is responsible for the keys in the range from its predecessor’s id (exclusive) to its own id (inclusive).

For example, in a space of size 128 with nodes at 32, 90, 105: node 32 is responsible for keys $(105, 32]$ (that is $106 \dots 127, 0 \dots 32$), node 90 for $(32, 90]$, and node 105 for $(90, 105]$. The id space is deliberately far larger than the node population (e.g. $2^{64}$), so only a sparse subset of positions is ever occupied.

10.3 The routing trade-off and finger tables#

How much each node knows trades off against how many hops a lookup takes:

• Full knowledge: every node stores every other node. Lookup $O(1)$, routing table $O(N)$: impractical at scale and impossible to keep consistent under churn.
• Successor only: each node knows just its next node on the ring. Routing table $O(1)$, lookup $O(N)$: a full traversal in the worst case.

Chord takes the middle path: each node keeps a finger table of $O(\log N)$ entries and achieves $O(\log N)$ hops. Entry $i$ (for $i = 0 \dots m-1$) points to the first node at or after position $(n + 2^i) \bmod 2^m$, its successor. The fingers are exponentially spaced: finger $i$ reaches about $1/2^{\,m-i}$ of the way round the ring, so the top finger spans roughly half the ring, the next a quarter, and so on. That fan-out is exactly what lets one hop cover a large fraction of the remaining distance.

Each entry $i$ also owns a lookup interval $[\,n + 2^i,\; n + 2^{i+1})$: a key falling in that interval is forwarded to the entry’s successor. The course presents the finger table with the columns used in the exercises, $i$, $2^i$, $\text{Id}+2^i$, the interval $\text{int}$, and the successor $\text{succ}$. As a worked table, node 0 and node 1 (nodes 0, 1, 2, 6) look like this:

10.4 Routing a lookup#

On receiving a query for key $k$, a node first checks whether it stores $k$ locally; if not, it forwards the query to the finger-table entry whose interval contains $k$. Consider node 1 looking up key 7 in the ring above:

At each hop the query goes to the finger closest to the target without overshooting it, so in the worst case each hop at least halves the remaining ring distance; after $O(\log N)$ halvings the responsible node is reached. With an $m$-bit space the ring holds up to $N = 2^m$ positions and each finger table has $m = \log_2 N$ entries, giving the three headline costs: routing table $O(\log N)$, lookup $O(\log N)$ hops, join $O(\log^2 N)$.

10.5 Joining the network#

Besides its finger table, each node keeps a pointer to its predecessor, enabling counter-clockwise navigation during maintenance. When a new node $n$ joins:

1. Bootstrap. Like Gnutella, $n$ must know one existing node; it contacts that node, which assigns $n$ an available id.
2. Populate its own fingers. $n$ fills $O(\log N)$ entries, each found by a lookup for the first node at or after $n + 2^i$. Each lookup costs $O(\log N)$, so building the table costs $O(\log^2 N)$.
3. Update other nodes’ fingers. For each finger position $i$, exactly one node, the one $2^{i-1}$ steps counter-clockwise before $n$, may now need to point to $n$. Using the predecessor pointer, $n$ locates and updates each via a lookup. Again $O(\log N)$ nodes, each $O(\log N)$ work: $O(\log^2 N)$ total.

Joining also means moving content: the keys $n$ becomes responsible for must migrate to it from its successor (in a pointer-based DHT, the pointers move rather than the data). A departing node’s keys likewise migrate to its successor.

10.6 Handling churn: stabilization and replication#

The $O(\log^2 N)$ join analysis assumes one change at a time. In practice many nodes join and leave at once, leaving finger tables temporarily inconsistent. Chord copes with two mechanisms:

• Periodic stabilization. Every node periodically re-looks-up the successor of $n + 2^{i-1}$ for each finger $i$ and repairs any entry that has changed, so tables heal in the background rather than through a single precise update.
• Successor lists and replication. Each node keeps a successor list of its first $R$ successors rather than a single successor: if the immediate successor stops responding, it contacts the next entry, and the ring survives up to $R-1$ consecutive failures. Relatedly, a node stores not only its own keys but also those of a few neighbours, so that even during inconsistency, when a query may land slightly off target, the data is likely found in the neighbourhood of the intended node.

10.7 Other structured DHTs#

Chord is one point in a design space; the general principle is more connections = fewer hops, but higher maintenance cost and fragility.

• Kademlia (used in part by eMule/eDonkey) keeps a tree-based structure with Chord-like guarantees; it was the most successfully deployed DHT in practice.
• CAN (Content-Addressable Network) organizes nodes in a multi-dimensional coordinate space: more neighbours mean faster routing but larger, more fragile tables.

Chord’s own limitations are the flip side of its guarantees: lookup only (no expressive search), structural overhead (maintaining the ring under churn is expensive and complex), limited real-world adoption for that reason, and difficulty preserving physical locality, since the ring is imposed independently of the underlying network.

11. Looking Ahead: Content-Centric Networking and IPFS#

A natural extension of the DHT idea is content-centric networking: rebuilding the internet’s addressing around what a resource is rather than where it is. Today’s internet is address-based, to fetch a resource you need its location (an IP address), which centralizes popular resources at fixed hosts. Content-based addressing instead looks up a resource by its content hash, routing the lookup through a large-scale DHT and returning the resource wherever it resides. This is fully decentralized (no server must be permanently available), naturally supports replication (the same hash resolves to any holder), and is censorship-resistant (no single location to take down). IPFS (InterPlanetary File System) is the most prominent proposal for this model, aiming to be a P2P layer beneath the existing internet.

12. Recap#

The unstructured designs differ mainly in where the index lives and how search reaches it; the structured design gives up expressive search for a provable bound.

Protocol	Type	Index	Search	Guarantees	Key limitation
Napster	Hybrid	Central server	Full-text metadata	Yes	Single point of failure/control
Gnutella	Unstructured	None (local)	Expressive flooding	No	High traffic, no result guarantee
Kazaa	Hybrid super-peer	Distributed (super-peers)	Expressive flooding	Partial	Probabilistic, super-peer churn
BitTorrent	Swarm download	External (tracker)	None (out-of-band)	No	No integrated search, central tracker
Freenet	Unstructured (caching)	Approximate (LRU)	Lookup only	No	No persistence guarantee
Chord DHT	Structured	Distributed ring	Lookup only	Yes: $O(\log N)$	No expressive search, high upkeep

The unstructured-vs-structured contrast is the one most often examined:

Property	Unstructured (Gnutella, Kazaa)	Structured (Chord)
Search expressivity	High (keyword search)	Low (exact-key lookup only)
Search performance	Probabilistic, no guarantees	$O(\log N)$ guaranteed
Network traffic	High (flooding)	Low (targeted routing)
Resilience to churn	High (degrades gracefully)	Lower (structure must be maintained)
Complexity	Lower	Higher

13. Exam questions#

The exams recycle a small number of P2P templates: a query-flooding trace, a Chord finger-table-and-lookup exercise, and one or two discursive questions (Chord vs. a full routing table; publish-subscribe over a DHT). The mechanical exercises are worth practising until they are automatic.

13.1 Query flooding with a TTL#

Solution

The overlay adjacency is: 0:{1}, 1:{0,2,3}, 2:{1,5}, 3:{1,4}, 4:{3}, 5:{2,6}, 6:{5}. Flooding from node 3, forwarding to every neighbour but the sender, with TTL = 3:

• Hop 1: $3 \to 1$, $3 \to 4$.
• Hop 2: node 4 has no other neighbour (stop); node 1 forwards $1 \to 0$, $1 \to 2$.
• Hop 3: node 0 has no other neighbour (stop); node 2 forwards $2 \to 5$.

The TTL is now exhausted. Node 5 would forward to node 6 on hop 4, but that hop is not allowed, so node 6 is never reached. Node 0 holds A and replies on the reverse path $0 \to 1 \to 3$. Node 3 learns of node 0 and downloads directly.

Result: node 0 is discovered, node 6 is not, the query-flooding limitation: even an existing copy can be missed once it lies beyond the TTL horizon.

13.2 Chord lookup: nodes 2, 9, 12 (4-bit)#

Solution

Successor of each position is the first node at or after it (mod 16). Responsibilities: node 2 owns $(12, 2]$, node 9 owns $(2, 9]$, node 12 owns $(9, 12]$.

(a) Routing tables.

Node 2:

$i$	$2^i$	$\text{Id}+2^i$	$\text{int}$	$\text{succ}$
0	1	3	$[3, 4)$	9
1	2	4	$[4, 6)$	9
2	4	6	$[6, 10)$	9
3	8	10	$[10, 2)$	12

Node 9:

$i$	$2^i$	$\text{Id}+2^i$	$\text{int}$	$\text{succ}$
0	1	10	$[10, 11)$	12
1	2	11	$[11, 13)$	12
2	4	13	$[13, 1)$	2
3	8	1	$[1, 9)$	2

Node 12:

$i$	$2^i$	$\text{Id}+2^i$	$\text{int}$	$\text{succ}$
0	1	13	$[13, 14)$	2
1	2	14	$[14, 0)$	2
2	4	0	$[0, 4)$	2
3	8	4	$[4, 12)$	9

(b) Lookup of key 10 from node 2. Node 2 does not own key 10. Key 10 falls in node 2’s interval $[10, 2)$ (row $i = 3$), whose successor is node 12, so node 2 forwards to node 12. Node 12 owns $(9, 12] = \{10, 11, 12\}$, so key 10 is local and it returns the value.

Messages: $2 \xrightarrow{\text{lookup}(10)} 12 \xrightarrow{\text{value}} 2$, one hop.

13.3 Chord lookup: nodes 4, 9, 12 (4-bit)#

Solution

Responsibilities: node 4 owns $(12, 4]$, node 9 owns $(4, 9]$, node 12 owns $(9, 12]$.

(a) Routing tables.

Node 4:

$i$	$2^i$	$\text{Id}+2^i$	$\text{int}$	$\text{succ}$
0	1	5	$[5, 6)$	9
1	2	6	$[6, 8)$	9
2	4	8	$[8, 12)$	9
3	8	12	$[12, 4)$	12

Node 9:

$i$	$2^i$	$\text{Id}+2^i$	$\text{int}$	$\text{succ}$
0	1	10	$[10, 11)$	12
1	2	11	$[11, 13)$	12
2	4	13	$[13, 1)$	4
3	8	1	$[1, 9)$	4

Node 12:

$i$	$2^i$	$\text{Id}+2^i$	$\text{int}$	$\text{succ}$
0	1	13	$[13, 14)$	4
1	2	14	$[14, 0)$	4
2	4	0	$[0, 4)$	4
3	8	4	$[4, 12)$	4

(b) Lookup of key 5 from node 4. Node 4 does not own key 5. Key 5 falls in node 4’s interval $[5, 6)$ (row $i = 0$), successor node 9, so node 4 forwards to node 9. Node 9 owns $(4, 9] = \{5, 6, 7, 8, 9\}$, so key 5 is local.

Messages: $4 \xrightarrow{\text{lookup}(5)} 9 \xrightarrow{\text{value}} 4$, one hop.

13.4 Chord lookup: nodes 2, 3, 4, 6 (3-bit)#

Solution

With 3 bits the ring is $0 \dots 7$ and each finger table has 3 rows. Responsibilities: node 2 owns $(6, 2]$, node 3 owns $(2, 3]$, node 4 owns $(3, 4]$, node 6 owns $(4, 6]$.

(a) Routing tables.

Node 2:

$i$	$2^i$	$\text{Id}+2^i$	$\text{int}$	$\text{succ}$
0	1	3	$[3, 4)$	3
1	2	4	$[4, 6)$	4
2	4	6	$[6, 2)$	6

Node 3:

$i$	$2^i$	$\text{Id}+2^i$	$\text{int}$	$\text{succ}$
0	1	4	$[4, 5)$	4
1	2	5	$[5, 7)$	6
2	4	7	$[7, 3)$	2

Node 4:

$i$	$2^i$	$\text{Id}+2^i$	$\text{int}$	$\text{succ}$
0	1	5	$[5, 6)$	6
1	2	6	$[6, 0)$	6
2	4	0	$[0, 4)$	2

Node 6:

$i$	$2^i$	$\text{Id}+2^i$	$\text{int}$	$\text{succ}$
0	1	7	$[7, 0)$	2
1	2	0	$[0, 2)$	2
2	4	2	$[2, 6)$	2

(b) Lookup of key 5 from node 3. Node 3 does not own key 5. Key 5 falls in node 3’s interval $[5, 7)$ (row $i = 1$), successor node 6, so node 3 forwards to node 6. Node 6 owns $(4, 6] = \{5, 6\}$, so key 5 is local.

Messages: $3 \xrightarrow{\text{lookup}(5)} 6 \xrightarrow{\text{value}} 3$, one hop.

13.5 Chord lookup with the routing row: nodes 2, 6, 11 (4-bit)#

Solution

Responsibilities: node 2 owns $(11, 2]$, node 6 owns $(2, 6]$, node 11 owns $(6, 11]$.

(a) Routing tables.

Node 2:

$i$	$2^i$	$\text{Id}+2^i$	$\text{int}$	$\text{succ}$
0	1	3	$[3, 4)$	6
1	2	4	$[4, 6)$	6
2	4	6	$[6, 10)$	6
3	8	10	$[10, 2)$	11

Node 6:

$i$	$2^i$	$\text{Id}+2^i$	$\text{int}$	$\text{succ}$
0	1	7	$[7, 8)$	11
1	2	8	$[8, 10)$	11
2	4	10	$[10, 14)$	11
3	8	14	$[14, 6)$	2

Node 11:

$i$	$2^i$	$\text{Id}+2^i$	$\text{int}$	$\text{succ}$
0	1	12	$[12, 13)$	2
1	2	13	$[13, 15)$	2
2	4	15	$[15, 3)$	2
3	8	3	$[3, 11)$	6

(b) Lookup of key 7 from node 2.

• Node 2 does not own key 7 (it owns $(11, 2]$). Key 7 falls in interval $[6, 10)$, row $i = 2$, successor node 6, so it forwards to node 6.
• Node 6 does not own key 7 (it owns $(2, 6]$). Key 7 falls in interval $[7, 8)$, row $i = 0$, successor node 11, so it forwards to node 11.
• Node 11 owns $(6, 11] = \{7, 8, 9, 10, 11\}$, so key 7 is local.

Messages: $2 \xrightarrow[\text{row } i=2]{\text{lookup}(7)} 6 \xrightarrow[\text{row } i=0]{\text{lookup}(7)} 11 \xrightarrow{\text{value}} 2$, two hops, consistent with $O(\log N)$.

13.6 Design: Chord vs. a full routing table#

Solution

Use Chord for scenario (1). Chord is designed for internet-scale, churning networks: its $O(\log N)$ finger table and $O(\log N)$ lookup are what make tens of thousands of dynamic nodes tractable. A full routing table there would be huge and impossible to keep consistent under constant join/leave.

For scenario (2), use a full routing table (full mesh). With fewer than 100 stable hosts, every node can simply know every other node: the table (≈100 entries) fits trivially in memory, lookup is $O(1)$ (forward directly to the responsible host), and there is no structural maintenance to pay for. This is, in fact, how lookup services inside a data center typically work.

The general trade-off. The threshold is a design choice driven by two factors together: the number of nodes (which sets the routing-table size) and the network’s stability (which sets the cost of keeping tables consistent). A full mesh is preferable as long as the table fits comfortably in memory and nodes are stable enough that propagating an update to everyone stays manageable; beyond that point a structured DHT like Chord wins. (The instructor stressed that even a “large but stable” network can justify a full mesh until the table stops fitting in memory, measure it.)

13.7 Publish-subscribe over a DHT#

Solution

Map each topic to a key via $\text{hash}(\text{topic})$. The DHT node responsible for that key becomes the rendezvous point (broker) for the topic. A subscriber performs lookup(hash(topic)) to reach the responsible node and registers its subscription there; a publisher performs the same lookup and sends the event to that node, which forwards it to all registered subscribers. The DHT supplies scalable, decentralized rendezvous with $O(\log N)$ routing and no single point of failure, and topics spread their load across different responsible nodes.

Main limitation: a DHT supports exact-key lookup only, so only topic-based (subject-based) subscriptions are possible, content-based subscriptions (predicates over event attributes) cannot be implemented directly, because the subscriber would need to know, in advance, an exact key for every event it might match. Secondary drawbacks: each topic is served by a single responsible node, which becomes a hot spot and a fault-tolerance weak point for popular topics unless the topic’s state is replicated across its successor nodes.

13.8 Discursive Chord questions (older exams)#

Solution

Chord (model answer). Nodes and items share an $m$-bit id space and sit on a ring ordered by id; key $k$ is managed by its successor. Each node keeps a finger table of $O(\log N)$ exponentially spaced entries (finger $i$ = first node at or after $n + 2^i$). Routing forwards a query to the finger closest to the key without overshooting, halving the remaining distance each hop, so lookup is $O(\log N)$; the routing table is $O(\log N)$; a join is $O(\log^2 N)$ ($O(\log N)$ affected nodes, each updated via an $O(\log N)$ lookup). It beats Gnutella and Kazaa because those give only probabilistic guarantees, flooding may miss an existing file and has no bound on messages or hops, whereas Chord provides provable bounds on both lookup cost and maintenance.

“Pure” P2P (model answer). A pure P2P system has no centralized component and treats every node symmetrically. Gnutella is the closest to pure (no central server; anchor nodes are only a bootstrap aid), and Freenet is similarly decentralized. Napster is not pure (central index). Kazaa is not pure (a super-peer tier, though otherwise decentralized). eDonkey is not pure (relies on servers; later Kad/Kademlia variants are closer). BitTorrent is not pure (a centralized tracker plus external torrent sites, though DHT-based trackerless variants move toward purity).

14. Glossary#

Term	Meaning
Overlay network	Logical network of peer-to-peer links laid on top of the physical network; a single overlay hop may span many physical hops.
Search	Retrieval by a (possibly expressive) query with no known identifier; returns all matches.
Lookup	Retrieval of a specific resource whose exact key/identifier is known.
Query flooding	Propagating a query to all neighbours (except the sender), bounded by a TTL (Gnutella).
TTL (hops-to-live)	Field bounding how many overlay hops a message may travel.
Super-peer	A well-connected, reliable node forming a small backbone that holds the index and floods queries among peers (Kazaa).
Free rider	A peer that consumes without contributing; BitTorrent’s tit-for-tat is designed against it.
Choking	A temporary refusal to upload to a peer; the basis of BitTorrent’s tit-for-tat.
Seed	A peer that holds the complete file and only uploads.
DHT	Distributed hash table: put/get by exact key, distributed with bounded lookup cost.
Chord	Ring-based DHT; keys managed by their successor node.
Finger table	A node’s $O(\log N)$ routing entries; entry $i$ = first node at or after $n + 2^i$.
Successor / predecessor	The next / previous node clockwise on the Chord ring.
Stabilization	Periodic background repair of finger tables under churn.
Successor list	The first $R$ successors, kept for fault tolerance and replication.

Compiled from G. Cugola's lectures (A.Y. 2025/26), slides + class transcriptions. Not official course material.