Peer-to-peer systems distribute storage, bandwidth, and responsibility across participants. Their history is a sequence of trade-offs in lookup cost and centralization.
| Design | Lookup idea | Strength | Weakness |
|---|---|---|---|
| Napster | Central directory | Fast lookup | Directory bottleneck/failure |
| Gnutella | Flood query to neighbors | No central index | Many messages, bounded horizon |
| FastTrack | Supernodes index local peers | Better scale | Unequal roles and hotspots |
| BitTorrent | Tracker/DHT finds swarm; peers exchange pieces | Parallel download, incentives | Discovery and availability still matter |
| Chord | Structured ring and finger table | Expected logarithmic lookup | Maintenance under churn |
Chord as a distributed hash table
Chord hashes node identities and keys into the same (m)-bit circular space. A key belongs to the first node clockwise whose ID is equal to or follows the key: its successor.
key K42 ──clockwise──> node N45Consistent hashing moves mainly the keys adjacent to a node that joins or leaves, rather than remapping the whole dataset.
Each node keeps a successor plus fingers at exponentially increasing distances. The table uses (O(log N)) entries and routes a lookup in expected (O(log N)) hops.
In plain terms: every hop skips roughly half the remaining distance around the ring.
Churn makes the elegant ring operational
Nodes join, leave, and fail. Stabilization repairs successor information; successor lists reduce the risk of losing the ring when an immediate neighbor fails; replication protects values. Correct lookup complexity assumes this maintenance keeps pace with churn.
Pastry uses prefix-based routing and locality-aware choices. Kelips spends more membership state to approach constant lookup hops. No overlay wins every dimension: routing latency, memory, maintenance traffic, locality, and churn tolerance trade against one another.
Review card
- P2P design distributes resource ownership but still needs discovery.
- Unstructured flooding trades simplicity for message cost.
- Structured overlays constrain topology to make lookup predictable.
- Chord maps nodes and keys onto one ring.
- Finger tables give logarithmic state and expected hops.
- Churn turns routing into a continuous repair problem.