Chapter 8: The Trouble with Distributed Systems

Core Concepts

Fundamental Challenges

• Network unreliability
• Clock synchronization issues
• Process pauses
• Partial failures

System Model

• Synchronous model: Every operation takes bounded time
• Asynchronous model: No guarantees on timing
• Partial synchronous model: Sometimes synchronous, sometimes not

---

Unreliable Networks

Common Failures

• Packet loss
• Network partitions
• Delays (queueing, congestion)
• Asymmetric communication

Timeout Problems

• How long to wait for response?
• Too short: False failure detection
• Too long: Slow failure detection

Unbounded Delays

• No guarantee on response time
• Queueing in network switches
• TCP retransmission
• Operating system scheduling

---

Unreliable Clocks

Problems with Clocks

• Clock skew between machines
• Clock jumps (NTP adjustments)
• Monotonic vs wall-clock time

Timestamps for Ordering

• Lamport timestamps: Capture causality
• Vector timestamps: Capture full causality

Clock Synchronization

• NTP: Network Time Protocol
• GPS: More accurate
• Atomic clocks: Most accurate

Limitations

• Clock readings have confidence intervals
• Cannot rely on clock for ordering

---

Process Pauses

The Problem

• Single-threaded server pauses for GC
• Other nodes think it's dead
• Resumes and may cause conflicts

Solutions

• Fencing tokens: Detect stale operations
• Leader and locks: Ensure only one leader
• Consensus algorithms: Handle process pauses

---

Truth and Lies

Fencing Tokens

• Monotonically increasing tokens
• Reject operations with old tokens
• Prevent stale writes

Byzantine Faults

• Nodes can lie or send incorrect data
• Requires Byzantine fault tolerance
• Used in blockchain, aerospace

CAP Theorem

• Consistency: All nodes see same data
• Availability: Every request gets response
• Partition tolerance: System works despite network failures

Theorem: Can only have 2 of 3 in presence of partitions

Trade-offs

• CP: Consistent but may be unavailable
• AP: Available but may be inconsistent
• CA: Not possible in distributed systems

---

Consistency and Consensus

Linearizability

• Strongest consistency model
• Operations appear atomic and instant
• Equivalent to single-copy serial execution

Ordering Guarantees

• Total order: All operations ordered
• Causal order: Operations ordered by causality

---

Key Takeaways

1. Networks are unreliable - design for failures
2. Clocks are unreliable - don't use them for ordering
3. Process pauses are real - handle them explicitly
4. CAP theorem forces trade-offs in distributed systems
5. Linearizability is expensive but provides strong consistency