We can send datagrams, but they get lost. Most applications don’t want to worry about that — they want a reliable communication layer reliable communication layer A messaging layer built on top of an unreliable network that guarantees delivery — and usually exactly-once, in-order delivery — using acknowledgments, timeout/retry, and sequence numbers. TCP/IP is the most common example. defined in ch. 48 — open in glossary that guarantees delivery on top of the unreliable network. Let’s build one.
48.3 Reliable Communication Layers
Start with one question: how does a sender know the receiver got its message? The answer is an acknowledgment acknowledgment A short message (an 'ack') the receiver sends back to confirm it received the sender's message. Receiving an ack lets the sender be sure the original message arrived; its absence (after a timeout) signals possible loss. defined in ch. 48 — open in glossary (ack) — a short reply confirming receipt. And if no ack comes back? The sender sets a timeout timeout A timer the sender sets when it sends a message; if no acknowledgment arrives before the timer fires, the sender concludes the message (or its ack) was lost. Choosing the value well matters — too short wastes resources on needless resends, too long hurts perceived performance. defined in ch. 48 — open in glossary when it sends; if the timer fires with no ack, it assumes loss and does a retry retry Re-sending a message after a timeout, in hopes it gets through the second time. This requires the sender to keep a copy of the message until it is acknowledged. The combined technique is called timeout/retry. defined in ch. 48 — open in glossary , re-sending a saved copy. The pair is called timeout/retry. But there’s a subtlety — walk all three cases:
The sender never throws the message away until it is acknowledged.
Case 3 is the trap. A lost ack is indistinguishable from a lost request at the sender, so it retries — and the receiver gets the message twice. For a reliable layer we usually want exactly-once exactly-once semantics The guarantee that each message is delivered to the receiving application exactly once — never lost and never duplicated. It matters because timeout/retry (e.g. after a dropped acknowledgment) can cause the same message to arrive twice on the wire; the receiver must ack the duplicate but not re-deliver it. Under failure, RPC often weakens this to at-most-once. defined in ch. 48 — open in glossary delivery, so the receiver must detect and suppress duplicates.
You could give each message a unique ID and have the receiver remember every ID it has ever seen — but that needs unbounded memory. The cheap fix is a sequence counter sequence counter A low-memory scheme for detecting duplicate messages. Sender and receiver each maintain a counter starting from an agreed value; the sender attaches its current value N as the message's ID and increments. The receiver expects N; if the incoming ID matches it delivers and increments, but if the ID is one it has already passed (a retransmission), it acks without re-delivering — preserving exactly-once. defined in ch. 48 — open in glossary : both sides keep a counter, and the value rides along as the message ID.
1Both counters start at 1
Sender and receiver agree on a start value (1). The sender will stamp each message with its current counter as the ID.
One counter per side, and duplicates are caught. The most common reliable layer, TCP/IP tcp The Transmission Control Protocol (TCP/IP), the most commonly used reliable communication layer. On top of unreliable IP it adds acknowledgments, sequence numbers, retransmission, congestion control, and many other optimizations to deliver an ordered, reliable byte stream. defined in ch. 48 — open in glossary , does all this and far more (congestion control, multiple outstanding requests, hundreds of optimizations).
Tip: Be Careful Setting The Timeout
Too short and the sender re-sends needlessly, wasting CPU and network; too long and it waits too long to recover, hurting perceived performance. The ideal is just long enough to detect loss. And with many clients hitting one server, loss often signals overload — so a client should use exponential back-off exponential back-off A strategy where, on repeated packet loss (often a symptom of overload), the sender increases its timeout/retry interval each time — for example doubling it — rather than resending at a fixed rate. This avoids adding still more load to an already-congested resource; it was pioneered in the Aloha network and adopted in early Ethernet. defined in ch. 48 — open in glossary (e.g. double the timeout after each miss, as pioneered in Aloha/Ethernet) rather than hammering an already-struggling server.48.4 Communication Abstractions
Given a messaging layer, what should we actually program against? One early idea took OS abstractions across the network: distributed shared memory distributed shared memory DSM: an abstraction that let processes on different machines share a single large virtual address space, implemented through the OS virtual-memory system (accessing a page held on another machine triggers a page fault that fetches it). It is not used in practice today because a machine failure makes part of the shared address space vanish (e.g. a pointer into missing memory) and remote page faults are expensive. defined in ch. 48 — open in glossary (DSM) let processes on different machines share one big virtual address space. It works through the VM system: touch a page held on another machine and a page fault fires, whose handler fetches the page over the network and installs it locally — so a distributed computation looks just like a multi-threaded program.
It didn’t last, for two reasons — and the first is fatal:
The second reason is performance: code assumes memory access is cheap, but in DSM some accesses silently become expensive remote page faults. Programmers had to organize computations to avoid communication almost entirely — defeating the point. Much was researched; little stuck. Nobody builds reliable distributed systems on DSM today. The abstraction that did win is a programming-language idea — remote procedure call — up next.
Check yourself: reliable messaging and abstractions
1.How do acknowledgments, timeouts, and retries combine to recover from a lost request?
2.When the ACK is lost (not the request), why does plain timeout/retry cause a problem?
3.How does a sequence counter detect duplicates cheaply, preserving exactly-once?
4.Under heavy load, why might a client use exponential back-off rather than retrying at a fixed interval?
5.Distributed shared memory (DSM) let machines share one virtual address space. Why isn't it used to build reliable distributed systems today?
6.What is TCP/IP in this picture?