What You Can Do By The End

• Contrast client-server and P2P
• Explain BitTorrent pieces and swarms
• Describe how a DHT finds data
• Explain gossip
• Describe NAT and how it is worked around

Client-Server Versus Peer-To-Peer

• Client-server: fixed roles, fixed capacity
• P2P: every peer requests and serves
• More peers bring more supply as well as demand
• The price: finding things without a boss

Client-server        P2P

 c   c   c          p--p--p
  \  |  /           |\ | /|
   [server]          p--p--p

A Short History

• Napster (1999): peers hold files, a central index finds them
• The central index was the weak point
• Gnutella flooded questions to neighbors
• BitTorrent and DHTs removed the central directory

BitTorrent In One Picture

• A file is cut into many pieces
• A peer fetches different pieces from different peers
• A peer re-shares every piece it holds
• A torrent file lists the hash of each piece

Hashes Protect Every Piece

• A hash is a fingerprint of data
• Change one bit and the fingerprint changes completely
• Peers check each piece against its listed hash
• A dishonest peer cannot slip in bad data

import hashlib
print(hashlib.sha256(b'hello').hexdigest())
print(hashlib.sha256(b'hellp').hexdigest())

Fairness And The Swarm

• Peers favor those who upload to them (tit-for-tat)
• A seeder holds the full file and uploads
• A tracker lists peers, a DHT can replace it
• Rules of exchange keep the swarm healthy

The Lookup Problem

• A million peers each hold some data
• Asking everyone does not scale
• A central index rebuilds the center
• Flooding works but creates heavy traffic

DHT: A Table Spread Over Peers

• Keys and peers both get numeric IDs
• A peer stores keys close to its own ID
• Closeness is measured with XOR
• Each peer knows many near contacts and a few far ones

A Lookup, Step By Step

• Ask the closest contacts you know for the key
• They reply with contacts even closer to the key
• Repeat until nobody knows a closer peer
• About twenty steps for a million peers

key = 0b1011
asker  -> knows 0b0001, 0b1000
0b1000 -> knows 0b1010
0b1010 -> holds key 0b1011

Gossip: Spreading By Rumor

• Tell a few random peers what you learned
• They tell a few more, and so on
• Informed peers roughly double each round
• No peer needs the whole picture

Gossip Simulation

• Start with one informed peer
• Each round, each informed peer tells two random peers
• Count rounds until everyone knows

import random

n, fanout = 100, 2
known = {0}
rounds = 0
while len(known) < n:
    for p in list(known):
        known.update(random.sample(range(n), fanout))
    rounds += 1
print(rounds)

The NAT Problem

• Many devices share one public address
• Replies to your own requests come back through the router
• Unexpected incoming connections are dropped
• Two peers behind NAT cannot start a connection

Working Around NAT

• Port mapping asks the router to open a port
• Hole punching: a helper tells both peers the other's address
• Both send at once so each router allows the reply
• A relay forwards traffic when nothing else works

The First Connection And Its Dangers

• Newcomers contact well-known bootstrap nodes
• Sybil attack: many fake identities
• Eclipse attack: surround a victim with attacker peers
• Defenses: diverse contacts, random choice, hash checks

Recap

• P2P peers both ask and serve
• BitTorrent shares in hashed pieces
• A DHT finds data in few hops
• Gossip spreads information robustly
• NAT needs hole punching or relays

Next Week

• Agreement without a boss
• Paxos and Raft at an intro level
• Byzantine generals and fault tolerance

Questions And Exercise

• Run gossip.py with 100 and 1000 peers
• Vary the fanout and add message loss
• Write three sentences on what you saw