Peer-to-Peer Systems
Stub. First-generation p2p (Napster, Gnutella) and second-generation structured overlays (KaZaA, Chord, CAN, Pastry, Koorde/De Bruijn graphs, skip graphs), the small-world phenomenon, replication management, free riders and BitTorrent, and censorship resistance/anonymity.
The evolution from unstructured to structured peer-to-peer overlays. First- generation systems (Napster’s centralized index, Gnutella’s flooding search) don’t scale; second-generation distributed hash tables (Chord, CAN, Pastry) fix this by giving every key a deterministic owner, reachable in hops via a structured routing topology — with Koorde/De Bruijn graphs and skip graphs as alternative topologies with different degree/hop tradeoffs. The small-world phenomenon explains why such structures can be navigated efficiently at all. Rounds out with the systems-level concerns any deployment faces: replication for availability, free-riding and BitTorrent’s tit-for-tat response, and censorship resistance/anonymity as a design goal in its own right — the strategic (rather than purely algorithmic) side of which is covered in incentives-in-p2p-systems.
Outline (TODO — flesh out each)
- First-generation p2p: Napster, Gnutella
- Second-generation p2p: KaZaA, Chord
- Content Addressable Network (CAN); Pastry
- Koorde and De Bruijn graphs
- The small-world phenomenon
- Skip graphs
- Replication management
- Free riders and BitTorrent
- Censorship resistance, anonymity, and ethical issues