distributedsystem/books/think-distributed-systems
System Models
Types of Distributed System Models
Synchronous Systems
- Strong notion of physical time.
- Clocks are synchronized or have a known bounded deviation.
- Message delays and processing time are bounded.
Benefit: Missing a deadlinw usually indicate failure.
Asynchronous Systems
No Notion of Time
- No clocks available.
- Events can occur with arbitrary delays.
- Timeouts cannot be used
Weak Notion of Time
- Clocks exist but are unsynchronized.
- Delays remain arbitrary.
- Timeouts can be used.
Key challenge: If a message does not arrive, you cannot know whether it is delayed or lost.
Partially Synchronous Systems
Most realistic model.
- System behaves synchronously most of the time.
- Occasionally behaves asynchronously.
Design principle:
- Ensure safety and liveness during synchronous periods.
- Prioritize safety during asynchronous periods.
Component Failure Models
- Crash-Stop Failure
- Components stops permanently.
- Perform no further actions.
- Omission Failure
- Component temporarily stops (takes a break)
- Resumes later without losing state.
- Crash-Recovery Failure
- Component temporarily stops.
- Resumes later but may lose some or all state.
- Byzatine Failure
- Byzantine Generals Problem
- Component behaves arbitrarily or maliciously.
- Can send incorrect or deceptive information
- Put simply, anything might happen.
Network Failure Models
The Fallacies of Distributed Computing > 1. The Network Is Reliable
Like components, system models for a network differ according to the failures that may occur in the network.
A network that experiences message reordering, message duplication, or message loss is commonly referred to as an unreliable network.
- Message Reordering
Messages may arrive in a different order than sent. - Message Duplication
Messages may be delivered multiple times. - Message Loss
Messages may never arrive.
A network with these behaviors is called an unreliable network.
Realistic Distributed System Assumptions
Most real-world systems are:
- Partially synchronous
- Subject to Crash-Stop, Omission, and Crash-Recovery failures
- Communicating over unreliable networks
Byzantine failures are generally ignored except in areas such as blockchain and cryptocurrency systems.
Order & Time
Why Ordering Matters
Distributed systems coordinate actions among components.
Since many operations are not commutative, different execution orders can produce different results.
Example: (+2) then (×2) → 4 , (×2) then (+2) → 2
Correct ordering is therefore essential.
Race Conditions
A system contains a race condition when:
- Multiple executions are possible.
- Some executions are correct.
- Others are incorrect.
Race conditions arise when outcomes depend on the order of events.
Coordinator-Based Ordering
One solution:
- Components send requests to a coordinator.
- Coordinator assigns sequence numbers.
- Receivers reorder requests using those numbers.
Result: Consistent ordering despite network delays or reordering.
Happened-Before Relationship
Concurrency vs Parallelism
Chapter 10 - Concurrency Patterns
Grokking Concurrency Book
Concurrency
Two operations are concurrent when neither happens before the other.
Determined using: Logical time, Logical clocks
Parallelism
Two operations are parallel when they overlap in real time.
Determined using: Physical time, Physical clocks
Concurrency ≠ Parallelism
Operations can be concurrent without running simultaneously.
Physical Time and Physical Clocks
Physical clocks use real-world time.
Problems
Clock Skew
Difference in time between clocks.
Example: Clock A = 10:00, Clock B = 10:05
Clock Drift
Clocks run at different speeds and gradually diverge.
Mitigation: NTP
Network Time Protocol (NTP) synchronizes clocks across systems to reduce skew and drift.
Types of Physical Clocks
Time-of-Day Clock
- Represents wall-clock time.
- Can move backward after synchronization.
- May violate ordering.
Monotonic Clock
- Never moves backward.
- Reliable for measuring durations.
- Cannot be compared across machines.
Logical Time and Logical Clocks
Logical clocks track causal ordering rather than real time.
Lamport Clocks
Rules:
- Each component maintains a counter.
- Increment counter for every event.
- Send counter value with messages.
- Receiver sets:
max(local, received) + 1
Benefits:
- Preserves causal ordering.
- Independent of clock synchronization.
Real-World Examples
Apache Kafka
- Partition = logical clock
- Message offset = logical timestamp
Messages are ordered within a partition.
etcd
- Key = logical clock
- Sequence number = logical timestamp
Updates can be ordered for each key.
Physical Clocks vs Logical Clocks
| Physical Clocks | Logical Clocks |
|---|---|
| Measure real time | Measure causal order |
| Subject to skew and drift | Immune to clock synchronization issues |
| Useful for durations | Useful for event ordering |
| Difficult to compare across machines | Consistent ordering across machines |
Big Picture
The author’s main point is:
A logical clock is not necessarily a special Lamport Clock data structure.
Many systems already use counters that provide ordering.
| System | Logical Clock | Logical Timestamp |
|---|---|---|
| Kafka | Partition | Offset |
| etcd | Key | Revision / Sequence Number |
| Lamport Clock | Process | Counter Value |
All three answer the same question:
“Which event happened before which other event?”
without relying on physical time (wall-clock timestamps). This avoids problems such as clock skew and clock drift between machine