Source: Operating Systems: Three Easy Pieces (OSTEP) — Chapter 48, Arpaci-Dusseau & Arpaci-Dusseau

Distributed Systems

A browser talking to a web server is a simple client/server distributed system. Behind Google or Facebook: thousands of machines cooperating.

Crux: how do we build systems that work when components fail? (RAID-like idea, harder setting.)

Failure is also opportunity: imperfect parts + redundancy → a service that appears rarely to fail. That is why modern web stacks are distributed.

Also care about: performance (messages, latency, bandwidth) and security (who am I talking to? who is listening?).

Communication is unreliable

Packets are lost or corrupted: bit flips, severed cables, dead routers — and full buffers in switches/hosts even when every link is “up.” Loss is fundamental.

Tip: treat communication as inherently unreliable; build reliability on top when needed.

Unreliable layers: UDP/IP

Some apps handle loss themselves (end-to-end argument). UDP offers datagrams via the sockets API: send/receive fixed-size messages, checksums for some corruption, no delivery guarantee.

A tiny client/server (chapter figures) is enough to start: UDP_Open, UDP_Write, UDP_Read.

Reliable layers: ack + timeout/retry

Mechanism	Role
Acknowledgment	Receiver proves it got the message
Timeout + retry	No ack → resend a kept copy
Sequence numbers	Detect duplicates when the ack was what got lost

Without seq numbers, a lost ack causes a retry the receiver already accepted → duplicates. With counters: deliver only when ID matches expected N, then bump; duplicates are acked but not passed up → exactly-once (no failure) / at-most-once (with failure).

Set timeouts carefully: too short → wasteful retries; too long → slow recovery. Many clients + overloaded server → exponential back-off (Aloha / Ethernet [A70]).

TCP adds congestion control, pipelining, and more [VJ88].

Quiz

Rank the sequence

1 / 1

Order events when a request is sent but its ack is lost (top = first).

OrderDrag the handle to rearrange — top should be first.

1The sender sends the message; the receiver receives and processes it
2The receiver acks, but the ack packet itself is lost in transit
3The receiver sees a duplicate sequence number, acks again, but does not re-deliver to the app
4The sender times out (no ack arrived) and resends its kept copy of the message

Drag items into the correct order (or use ↑↓), then check.

Abstractions communication

Distributed shared memory (DSM): remote pages via page faults — looks like threads on one big address space. Failure (missing pages mid-structure) and performance (some loads are RPCs in disguise) killed practical use for reliable systems.

Remote procedure call (RPC) [BN84] won: calling a remote function should feel like a local call.

Stub generator

From an interface, generate client stubs (marshal → send → wait → unmarshal) and server stubs (unmarshal → call → marshal reply). Handles complex args via known types / annotations. Servers usually use a thread pool.

Run-time library

Naming: hostname + port (DNS, …)
Transport: TCP is “obviously” reliable but double-acks a request/response; many RPCs sit on UDP and implement reliability themselves
Long calls: early ack + “still working?” polls
Large args: fragmentation / reassembly
Endianness: e.g. XDR
Optional async RPC: fire, do other work, later wait for results

Quiz

Rank the sequence

1 / 1

Order a single RPC call through the stub/runtime layers (top = first).

OrderDrag the handle to rearrange — top should be first.

1The server stub marshals the function's return value and sends the reply
2The runtime layer transports the marshaled message to the server and waits
3The client stub marshals the call's arguments into a message
4The client stub unmarshals the reply and returns it to the caller as if it were a local call
5The server stub unmarshals the arguments and calls the real local function

Drag items into the correct order (or use ↑↓), then check.

End-to-end argument [SRC84]

Only the application ends can truly guarantee some properties (e.g. correct file transfer). Lower-layer reliability helps but cannot catch sender-memory corruption or a bad disk write. Corollary: lower-layer features can still optimize performance — use judgment.

Interactive

Try: why distribute · UDP · reliable messaging · RPC vs DSM · end-to-end.

Check your understanding

Quiz