P2P Systems: DHTs & Gossip

Consistent Hashing · DHTs · Epidemic Protocols

1:00

How peer-to-peer systems use consistent hashing, distributed hash tables, and gossip protocols to find any key and spread updates across N nodes — all in O(log N) steps.

By the end, you can

Explain the difference between client–server and peer-to-peer architectures, including the tradeoffs.
Describe why structured P2P (DHTs) provides guaranteed lookups while unstructured P2P does not.
Show why the naive hash(k) % N mapping reshuffles nearly all keys on any membership change.
Explain consistent hashing: how nodes and keys share a ring, how ownership is assigned, and why only ~K/N keys move on churn.
Describe Chord's finger table, explain why finger distances double, and derive the O(log N) hop count.
Calculate log₂(N) lookup hops and gossip rounds for given values of N.
Explain how Kademlia differs from Chord (XOR metric, k-buckets) and name real systems that use it.
Trace how gossip spreads exponentially and explain the O(log N) round bound.
Distinguish anti-entropy from rumor-mongering and identify when each is preferable.
State the key tradeoffs of gossip protocols: decentralized, fault-tolerant, scalable, but only eventually consistent with redundant messages.

Up next in Networking, Distributed Systems & Databases