What You Can Do By The End

• Explain how messages go wrong
• Compute a minimum round-trip time
• Describe partial failure
• State the CAP theorem with an example
• Simulate eventual consistency in Python

No Shared Memory, No Shared Clock

• Machines learn about each other only through messages
• Messages take time
• Parts fail while other parts continue
• Each machine keeps its own drifting clock

The Eight Fallacies

• The network is reliable
• Latency is zero, bandwidth is infinite
• The network is secure and never changes
• There is one administrator
• Transport cost is zero, the network is uniform

What A Message Can Do

• Arrive on time
• Arrive late
• Arrive twice
• Arrive out of order
• Never arrive

UDP, TCP And Repeatable Requests

• UDP sends and forgets
• TCP numbers packets and resends lost ones
• A dropped connection leaves the sender unsure
• Make operations idempotent: safe to send twice

Latency Has A Floor

• Light in fiber moves at about two thirds of vacuum speed
• 5,000 km needs around 25 ms one way
• Round trip costs at least 50 ms
• Software cannot beat physics

distance_km = 5000
speed_km_per_s = 200000   # light in fiber, approx
one_way_ms = distance_km / speed_km_per_s * 1000
print(one_way_ms, one_way_ms * 2)

Latency Versus Bandwidth

• Latency: length of the road
• Bandwidth: number of lanes
• More lanes do not shorten the road
• Timeouts are chosen with typical and worst cases in mind

Partial Failure

• Some parts work while others fail
• A silent machine may be crashed, busy or unreachable
• Timeouts are guesses, not facts
• Wrong answers are harder than crashes

Network Partitions

• The network splits machines into groups
• Each group may work fine inside
• Rare on a good day, certain over time
• Design for them from the start

[A] [B]   X   [C] [D]
 group 1   cut   group 2

Time And Order

• Every clock drifts
• Timestamps cannot always order close events
• Lamport (1978): order events by what could influence what
• Logical clocks are counters carried in messages

Replication And Consistency

• Replicas are copies kept on different machines
• They survive failure and serve nearby users
• Strong consistency: every reader sees the latest write
• Weaker forms allow stale reads for a while

The CAP Theorem

• C: every read sees the latest write
• A: every request to a working machine gets an answer
• P: the system continues despite dropped messages
• During a partition, choose C or A

CP Or AP: Choosing By Cost

• CP: refuse some requests to stay correct
• AP: keep answering, repair differences later
• Bank balance leans CP
• Social feed leans AP

Eventual Consistency In 12 Lines

• Two replicas accept writes during a partition
• A merge rule picks the final value
• Last write wins is simple but can lose updates

a = {'v': 'red',  't': 1}
b = {'v': 'blue', 't': 2}

def merge(x, y):
    return x if x['t'] >= y['t'] else y

winner = merge(a, b)
a, b = dict(winner), dict(winner)
print(a, b)
# both replicas now hold {'v': 'blue', 't': 2}

Recap

• Messages can be late, lost, duplicated or reordered
• Latency has a physical floor
• Partial failure and partitions are normal
• CAP: pick C or A during a partition
• Eventual consistency repairs differences later

Next Week

• Peer-to-peer networks
• BitTorrent, DHTs and gossip
• NAT and how peers find each other

Questions And Exercise

• Run replicas.py and read the output
• Change the merge rule
• Add a third replica
• Write when last write wins is dangerous