Distributed Systems Concepts¶

Difficulty: ⭐⭐⭐⭐

Overview¶

A distributed system is multiple computers connected via a network that cooperate to function as a single system. In this chapter, we'll learn about the fundamental challenges of distributed systems, the concept of time, and leader election algorithms.

1. The 8 Fallacies of Distributed Computing¶

Fallacies of Distributed Computing¶

These are common false assumptions that distributed system beginners often make.

┌─────────────────────────────────────────────────────────────────────────┐
│              The 8 Fallacies of Distributed Computing                   │
├─────────────────────────────────────────────────────────────────────────┤
│                                                                         │
│  1. The network is reliable                                            │
│  ┌─────────────────────────────────────────────────────────────────┐   │
│  │  Reality:                                                       │   │
│  │  - Packet loss                                                  │   │
│  │  - Network partitions                                           │   │
│  │  - Switch/router failures                                       │   │
│  │                                                                  │   │
│  │  Node A ───X───► Node B                                         │   │
│  │         Packet loss                                              │   │
│  │                                                                  │   │
│  │  Mitigation: Retries, timeouts, idempotency                     │   │
│  └─────────────────────────────────────────────────────────────────┘   │
│                                                                         │
│  2. Latency is zero                                                    │
│  ┌─────────────────────────────────────────────────────────────────┐   │
│  │  Reality:                                                       │   │
│  │  - Local call: ~10 ns                                           │   │
│  │  - Same DC: 0.5 ms                                              │   │
│  │  - Cross-continent: 100+ ms                                     │   │
│  │                                                                  │   │
│  │  Seoul ──────────────────► US West                              │   │
│  │         ~150ms RTT                                               │   │
│  │                                                                  │   │
│  │  Mitigation: Caching, async processing, regional distribution   │   │
│  └─────────────────────────────────────────────────────────────────┘   │
│                                                                         │
│  3. Bandwidth is infinite                                              │
│  ┌─────────────────────────────────────────────────────────────────┐   │
│  │  Reality:                                                       │   │
│  │  - Network congestion                                           │   │
│  │  - Bandwidth limits                                             │   │
│  │  - Cost                                                         │   │
│  │                                                                  │   │
│  │  Mitigation: Compression, pagination, data locality             │   │
│  └─────────────────────────────────────────────────────────────────┘   │
│                                                                         │
│  4. The network is secure                                              │
│  ┌─────────────────────────────────────────────────────────────────┐   │
│  │  Reality:                                                       │   │
│  │  - Man-in-the-middle attacks                                    │   │
│  │  - Packet sniffing                                              │   │
│  │  - Malicious nodes                                              │   │
│  │                                                                  │   │
│  │  Mitigation: TLS, authentication, encryption                    │   │
│  └─────────────────────────────────────────────────────────────────┘   │
│                                                                         │
└─────────────────────────────────────────────────────────────────────────┘

┌─────────────────────────────────────────────────────────────────────────┐
│              The 8 Fallacies of Distributed Computing (cont.)           │
├─────────────────────────────────────────────────────────────────────────┤
│                                                                         │
│  5. Topology doesn't change                                            │
│  ┌─────────────────────────────────────────────────────────────────┐   │
│  │  Reality:                                                       │   │
│  │  - Server additions/removals                                    │   │
│  │  - Failure recovery                                             │   │
│  │  - Scaling                                                      │   │
│  │                                                                  │   │
│  │  Mitigation: Service discovery, dynamic configuration          │   │
│  └─────────────────────────────────────────────────────────────────┘   │
│                                                                         │
│  6. There is one administrator                                         │
│  ┌─────────────────────────────────────────────────────────────────┐   │
│  │  Reality:                                                       │   │
│  │  - Multiple teams, multiple organizations                       │   │
│  │  - Different policies                                           │   │
│  │  - Cloud + on-premises                                          │   │
│  │                                                                  │   │
│  │  Mitigation: Standardization, automation, governance            │   │
│  └─────────────────────────────────────────────────────────────────┘   │
│                                                                         │
│  7. Transport cost is zero                                             │
│  ┌─────────────────────────────────────────────────────────────────┐   │
│  │  Reality:                                                       │   │
│  │  - Cloud egress costs                                           │   │
│  │  - Serialization/deserialization overhead                       │   │
│  │  - Network equipment costs                                      │   │
│  │                                                                  │   │
│  │  Mitigation: Data locality, efficient protocols                 │   │
│  └─────────────────────────────────────────────────────────────────┘   │
│                                                                         │
│  8. The network is homogeneous                                         │
│  ┌─────────────────────────────────────────────────────────────────┐   │
│  │  Reality:                                                       │   │
│  │  - Various hardware                                             │   │
│  │  - Various protocols                                            │   │
│  │  - Legacy systems                                               │   │
│  │                                                                  │   │
│  │  Mitigation: Standard protocols, abstraction layers             │   │
│  └─────────────────────────────────────────────────────────────────┘   │
│                                                                         │
└─────────────────────────────────────────────────────────────────────────┘

2. Time and Ordering¶

Problems with Physical Clocks¶

┌─────────────────────────────────────────────────────────────────────────┐
│                     Physical Clocks                                     │
├─────────────────────────────────────────────────────────────────────────┤
│                                                                         │
│  Problem 1: Clock Drift                                                │
│  ┌─────────────────────────────────────────────────────────────────┐   │
│  │                                                                  │   │
│  │  Time ─────────────────────────────────────────────────────►     │   │
│  │                                                                  │   │
│  │  Real time: ═════════════════════════════════════════════════   │   │
│  │                                                                  │   │
│  │  Node A:    ════════════════════════════════════════════════     │   │
│  │              (slightly fast)                                     │   │
│  │                                                                  │   │
│  │  Node B:    ════════════════════════════════════════════════     │   │
│  │              (slightly slow)                                     │   │
│  │                                                                  │   │
│  │  Typical drift: 10-100 microseconds per second                  │   │
│  │  → Difference of several seconds per day!                       │   │
│  └─────────────────────────────────────────────────────────────────┘   │
│                                                                         │
│  Problem 2: NTP Synchronization Limitations                            │
│  ┌─────────────────────────────────────────────────────────────────┐   │
│  │  - Typical accuracy: tens of milliseconds                       │   │
│  │  - Internet environment: 100ms+ error possible                  │   │
│  │  - Time jumps possible (forward/backward)                       │   │
│  │                                                                  │   │
│  │  NTP Server ───────────► Node                                   │   │
│  │              Network delay                                       │   │
│  │              causes error                                        │   │
│  └─────────────────────────────────────────────────────────────────┘   │
│                                                                         │
│  Problem 3: Dangers of Timestamp-Based Ordering                        │
│  ┌─────────────────────────────────────────────────────────────────┐   │
│  │                                                                  │   │
│  │  Node A (clock fast):  Write X=1 at T=100                       │   │
│  │  Node B (clock slow):  Write X=2 at T=99                        │   │
│  │                                                                  │   │
│  │  Sorted by timestamp: X=2 (T=99) → X=1 (T=100)                  │   │
│  │  Actual order: X=1 first → X=2 later                            │   │
│  │                                                                  │   │
│  │  → Wrong order! Possible data loss!                             │   │
│  └─────────────────────────────────────────────────────────────────┘   │
│                                                                         │
└─────────────────────────────────────────────────────────────────────────┘

Happens-Before Relationship¶

┌─────────────────────────────────────────────────────────────────────────┐
│                     Happens-Before Relationship                         │
├─────────────────────────────────────────────────────────────────────────┤
│                                                                         │
│  Definition: a → b (a happens-before b)                                │
│                                                                         │
│  1. If a occurs before b in the same process                           │
│  2. If a is a message send and b is that message's receipt             │
│  3. Transitivity: a → b ∧ b → c ⟹ a → c                                │
│                                                                         │
│  ┌─────────────────────────────────────────────────────────────────┐   │
│  │                                                                  │   │
│  │  Process P1:  ─────●a─────────────●c──────────────────────►      │   │
│  │                    │              ▲                              │   │
│  │                    │              │                              │   │
│  │                    ▼ (message)    │ (message)                    │   │
│  │                    │              │                              │   │
│  │  Process P2:  ─────────●b─────────●d──────────────────────►      │   │
│  │                                                                  │   │
│  │  Relationships:                                                  │   │
│  │  - a → b (message send)                                          │   │
│  │  - b → d (same process)                                          │   │
│  │  - a → c (same process)                                          │   │
│  │  - d → c (message send)                                          │   │
│  │  - a → d (transitivity: a → b → d)                               │   │
│  │                                                                  │   │
│  └─────────────────────────────────────────────────────────────────┘   │
│                                                                         │
│  Concurrency:                                                          │
│  If neither a → b nor b → a, then a and b are concurrent              │
│  Denoted as a ∥ b                                                      │
│                                                                         │
│  ┌─────────────────────────────────────────────────────────────────┐   │
│  │  P1:  ─────●a─────────────────────────────────────────►          │   │
│  │                                                                  │   │
│  │  P2:  ─────────────●b─────────────────────────────────►          │   │
│  │                                                                  │   │
│  │  a and b have no causal relationship → undefined order           │   │
│  │  → concurrent (a ∥ b)                                            │   │
│  └─────────────────────────────────────────────────────────────────┘   │
│                                                                         │
└─────────────────────────────────────────────────────────────────────────┘

3. Logical Clocks¶

Lamport Clock¶

┌─────────────────────────────────────────────────────────────────────────┐
│                     Lamport Clock                                       │
├─────────────────────────────────────────────────────────────────────────┤
│                                                                         │
│  Rules:                                                                │
│  1. Each process maintains a counter C                                 │
│  2. On event: C = C + 1                                                │
│  3. On message send: include current C in message                      │
│  4. On message receive: C = max(C, msg.C) + 1                          │
│                                                                         │
│  ┌─────────────────────────────────────────────────────────────────┐   │
│  │                                                                  │   │
│  │  Process A:  ─●───────●───────────────●───────────────►          │   │
│  │  (C)          1       2               5                          │   │
│  │                       │               ▲                          │   │
│  │                       │ msg(C=2)      │ msg(C=4)                 │   │
│  │                       ▼               │                          │   │
│  │  Process B:  ─────────●───────●───────●───────────────►          │   │
│  │  (C)                  3       4       5                          │   │
│  │                               ▲                                  │   │
│  │                               │                                  │   │
│  │  B receives msg from A:      max(2, 2) + 1 = 3                  │   │
│  │  B local event:              3 + 1 = 4                          │   │
│  │  B sends msg to A:           4 (in message)                     │   │
│  │  A receives msg from B:      max(2, 4) + 1 = 5                  │   │
│  │                                                                  │   │
│  └─────────────────────────────────────────────────────────────────┘   │
│                                                                         │
│  Properties:                                                           │
│  ✓ a → b ⟹ C(a) < C(b)    (causality implies clock order)           │
│  ✗ C(a) < C(b) ⟹ a → b    (converse doesn't hold!)                  │
│                                                                         │
│  Limitations:                                                          │
│  - Cannot distinguish concurrent events                                │
│  - Same counter value possible                                         │
│                                                                         │
└─────────────────────────────────────────────────────────────────────────┘

Vector Clock¶

┌─────────────────────────────────────────────────────────────────────────┐
│                     Vector Clock                                        │
├─────────────────────────────────────────────────────────────────────────┤
│                                                                         │
│  Rules:                                                                │
│  - Each process i maintains vector V[1..N] (N = number of processes)   │
│  - On event: V[i] = V[i] + 1                                           │
│  - On message send: include entire vector V                            │
│  - On message receive: V[j] = max(V[j], msg.V[j]) for all j, V[i]++   │
│                                                                         │
│  ┌─────────────────────────────────────────────────────────────────┐   │
│  │                                                                  │   │
│  │  Process A:  ─●─────────●─────────────────●───────────►          │   │
│  │  V           [1,0,0]  [2,0,0]           [3,2,1]                 │   │
│  │                        │                   ▲                     │   │
│  │                        │                   │ msg [2,2,1]         │   │
│  │                        ▼                   │                     │   │
│  │  Process B:  ─────────●─────────●─────────●───────────►          │   │
│  │  V                  [2,1,0]   [2,2,0]   [2,2,1]                  │   │
│  │                        ▲         │                               │   │
│  │                        │         │ msg [2,2,0]                   │   │
│  │                        │         ▼                               │   │
│  │  Process C:  ─────────●─────────●─────────────────────►          │   │
│  │  V                  [0,0,1]   [2,2,1]                           │   │
│  │                                                                  │   │
│  └─────────────────────────────────────────────────────────────────┘   │
│                                                                         │
│  Comparison Rules:                                                     │
│  - V1 ≤ V2: V1[i] ≤ V2[i] for all i                                   │
│  - V1 < V2: V1 ≤ V2 and V1 ≠ V2                                       │
│  - V1 ∥ V2: neither V1 < V2 nor V2 < V1 (concurrent)                  │
│                                                                         │
│  Examples:                                                             │
│  [2,0,0] < [2,2,0]  ✓ (happens-before)                                │
│  [2,1,0] ∥ [0,0,1]  ✓ (concurrent)                                    │
│                                                                         │
│  Pros: Can detect concurrent events                                    │
│  Cons: Vector size = number of processes (scalability issue)          │
│                                                                         │
└─────────────────────────────────────────────────────────────────────────┘

Logical Clock Comparison¶

Property	Lamport Clock	Vector Clock
Size	1 integer	N integers
Causality detection	Partial	Complete
Concurrency detection	Not possible	Possible
Scalability	Excellent	Limited
Implementation complexity	Simple	Medium

Practical Usage Example¶

┌─────────────────────────────────────────────────────────────────────────┐
│                     Vector Clock Usage Example: DynamoDB                │
├─────────────────────────────────────────────────────────────────────────┤
│                                                                         │
│  Conflict Detection and Resolution:                                    │
│                                                                         │
│  ┌─────────────────────────────────────────────────────────────────┐   │
│  │                                                                  │   │
│  │  Initial state: X = "A", V = [1,0]                              │   │
│  │                                                                  │   │
│  │  Replica 1:  Write X = "B"  →  V = [2,0]                        │   │
│  │  Replica 2:  Write X = "C"  →  V = [1,1]                        │   │
│  │                                                                  │   │
│  │  At synchronization:                                            │   │
│  │  [2,0] ∥ [1,1]  (concurrent writes!)                            │   │
│  │                                                                  │   │
│  │  Resolution methods:                                            │   │
│  │  1. Last-Write-Wins (timestamp)                                 │   │
│  │  2. Return to client for resolution                             │   │
│  │  3. Application-defined merge                                   │   │
│  │                                                                  │   │
│  └─────────────────────────────────────────────────────────────────┘   │
│                                                                         │
│  Example: Shopping cart merge                                          │
│  ┌─────────────────────────────────────────────────────────────────┐   │
│  │  Client reads: [item1], [item2]  (two versions)                 │   │
│  │  Client merges: [item1, item2]                                  │   │
│  │  Client writes: merged result                                   │   │
│  └─────────────────────────────────────────────────────────────────┘   │
│                                                                         │
└─────────────────────────────────────────────────────────────────────────┘

4. Leader Election¶

Why Is Leader Election Needed?¶

┌─────────────────────────────────────────────────────────────────────────┐
│                     Leader Election                                     │
├─────────────────────────────────────────────────────────────────────────┤
│                                                                         │
│  Why is it needed?                                                     │
│  ┌─────────────────────────────────────────────────────────────────┐   │
│  │  Cases where a coordinator role is needed in distributed systems:│   │
│  │                                                                  │   │
│  │  - Distributed lock management                                  │   │
│  │  - Proposer in consensus algorithms                             │   │
│  │  - Database primary node                                        │   │
│  │  - Distributed job scheduling                                   │   │
│  │  - Message ordering                                             │   │
│  │                                                                  │   │
│  │  ┌─────────┐  ┌─────────┐  ┌─────────┐                          │   │
│  │  │ Node 1  │  │ Node 2  │  │ Node 3  │                          │   │
│  │  │(Leader) │  │(Follower│  │(Follower│                          │   │
│  │  │    ★    │  │         │  │         │                          │   │
│  │  └────┬────┘  └────┬────┘  └────┬────┘                          │   │
│  │       │            │            │                                │   │
│  │       └────────────┼────────────┘                                │   │
│  │                    │                                             │   │
│  │               Coordination/Sync                                  │   │
│  └─────────────────────────────────────────────────────────────────┘   │
│                                                                         │
│  Requirements:                                                         │
│  1. Safety: At most 1 leader at any time                              │
│  2. Liveness: Eventually a leader is elected                          │
│                                                                         │
└─────────────────────────────────────────────────────────────────────────┘

Bully Algorithm¶

┌─────────────────────────────────────────────────────────────────────────┐
│                     Bully Algorithm                                     │
├─────────────────────────────────────────────────────────────────────────┤
│                                                                         │
│  Rule: The node with the highest ID becomes leader                     │
│                                                                         │
│  ┌─────────────────────────────────────────────────────────────────┐   │
│  │                                                                  │   │
│  │  Initial state: Node 5 is leader                                │   │
│  │                                                                  │   │
│  │  Node 1   Node 2   Node 3   Node 4   Node 5 (Leader)            │   │
│  │    │        │        │        │         ✗ (failure)             │   │
│  │    │        │        │        │                                  │   │
│  │                                                                  │   │
│  │  Step 1: Node 2 detects leader failure                          │   │
│  │  ─────────────────────────────                                   │   │
│  │  Node 2 → "ELECTION" → Node 3, 4, 5                             │   │
│  │                                                                  │   │
│  │  Step 2: Higher IDs respond                                     │   │
│  │  ─────────────────────────────                                   │   │
│  │  Node 3 → "OK" → Node 2  (higher ID exists)                     │   │
│  │  Node 4 → "OK" → Node 2                                         │   │
│  │  Node 5 → (no response)                                         │   │
│  │                                                                  │   │
│  │  Step 3: Node 3, 4 also start elections                         │   │
│  │  ─────────────────────────────                                   │   │
│  │  Node 3 → "ELECTION" → Node 4, 5                                │   │
│  │  Node 4 → "ELECTION" → Node 5                                   │   │
│  │                                                                  │   │
│  │  Step 4: Node 4 becomes winner                                  │   │
│  │  ─────────────────────────────                                   │   │
│  │  Node 4 → "COORDINATOR" → All                                   │   │
│  │                                                                  │   │
│  │  Node 1   Node 2   Node 3   Node 4 (Leader)   Node 5            │   │
│  │                               ★                  ✗              │   │
│  │                                                                  │   │
│  └─────────────────────────────────────────────────────────────────┘   │
│                                                                         │
│  Complexity: O(n²) messages                                            │
│                                                                         │
│  Problems:                                                             │
│  - Split-Brain possible during network partition                       │
│  - Repeated elections if highest ID node is unstable                  │
│                                                                         │
└─────────────────────────────────────────────────────────────────────────┘

Ring Algorithm¶

┌─────────────────────────────────────────────────────────────────────────┐
│                     Ring Algorithm                                      │
├─────────────────────────────────────────────────────────────────────────┤
│                                                                         │
│  Structure: Nodes arranged in a logical ring                           │
│                                                                         │
│  ┌─────────────────────────────────────────────────────────────────┐   │
│  │                                                                  │   │
│  │                    ┌───────┐                                     │   │
│  │                    │Node 1 │                                     │   │
│  │                    └───┬───┘                                     │   │
│  │               ┌────────┘ └────────┐                              │   │
│  │               ▼                   ▼                              │   │
│  │           ┌───────┐           ┌───────┐                          │   │
│  │           │Node 5 │◄──────────│Node 2 │                          │   │
│  │           └───┬───┘           └───┬───┘                          │   │
│  │               │                   │                              │   │
│  │               ▼                   ▼                              │   │
│  │           ┌───────┐           ┌───────┐                          │   │
│  │           │Node 4 │───────────│Node 3 │                          │   │
│  │           └───────┘           └───────┘                          │   │
│  │                                                                  │   │
│  └─────────────────────────────────────────────────────────────────┘   │
│                                                                         │
│  Election Process:                                                     │
│  ┌─────────────────────────────────────────────────────────────────┐   │
│  │                                                                  │   │
│  │  1. On leader failure detection, create election message:       │   │
│  │     [initiator_id]                                              │   │
│  │                                                                  │   │
│  │  2. Forward to next node, adding own ID:                        │   │
│  │     Node 2: [3] → Node 3                                        │   │
│  │     Node 3: [3, 4] → Node 4                                     │   │
│  │     Node 4: [3, 4, 5] → Node 5                                  │   │
│  │     Node 5: [3, 4, 5, 1] → Node 1                               │   │
│  │     Node 1: [3, 4, 5, 1, 2] → Node 2                            │   │
│  │                                                                  │   │
│  │  3. When message returns to starting point:                     │   │
│  │     - Select highest ID from list: 5                            │   │
│  │     - Propagate COORDINATOR message: Node 5 is leader           │   │
│  │                                                                  │   │
│  └─────────────────────────────────────────────────────────────────┘   │
│                                                                         │
│  Complexity: O(n) messages                                             │
│                                                                         │
│  Pros: Fewer messages                                                  │
│  Cons: Ring maintenance required, slower election                      │
│                                                                         │
└─────────────────────────────────────────────────────────────────────────┘

Modern Leader Election¶

┌─────────────────────────────────────────────────────────────────────────┐
│                     Modern Leader Election Approaches                   │
├─────────────────────────────────────────────────────────────────────────┤
│                                                                         │
│  1. Consensus-based                                                    │
│  ┌─────────────────────────────────────────────────────────────────┐   │
│  │  - Using consensus algorithms like Raft, Paxos                  │   │
│  │  - Utilizing distributed lock services (ZooKeeper, etcd, Consul)│   │
│  │  - Split-Brain prevention                                       │   │
│  │                                                                  │   │
│  │  Example: Raft leader election                                  │   │
│  │  - Transition to Candidate after timeout                        │   │
│  │  - Leader elected by majority vote                              │   │
│  │  - Term-based leadership management                             │   │
│  └─────────────────────────────────────────────────────────────────┘   │
│                                                                         │
│  2. Using External Services                                            │
│  ┌─────────────────────────────────────────────────────────────────┐   │
│  │                                                                  │   │
│  │  ┌─────────────────────────────────────────────────────────┐    │   │
│  │  │                   ZooKeeper / etcd                       │    │   │
│  │  │                                                          │    │   │
│  │  │  /leader-election/                                       │    │   │
│  │  │    └─ lock (ephemeral node)                              │    │   │
│  │  │        owner: node-1                                     │    │   │
│  │  │                                                          │    │   │
│  │  └─────────────────────────────────────────────────────────┘    │   │
│  │            │           │           │                            │   │
│  │            ▼           ▼           ▼                            │   │
│  │       ┌────────┐  ┌────────┐  ┌────────┐                       │   │
│  │       │Node 1  │  │Node 2  │  │Node 3  │                       │   │
│  │       │(Leader)│  │(Watch) │  │(Watch) │                       │   │
│  │       └────────┘  └────────┘  └────────┘                       │   │
│  │                                                                 │   │
│  │  - Attempt to create ephemeral node                             │   │
│  │  - First creator becomes leader                                 │   │
│  │  - On leader failure, node auto-deleted → re-election           │   │
│  │                                                                 │   │
│  └─────────────────────────────────────────────────────────────────┘   │
│                                                                         │
└─────────────────────────────────────────────────────────────────────────┘

5. Distributed Systems Challenges¶

Network Partition¶

┌─────────────────────────────────────────────────────────────────────────┐
│                     Network Partition                                   │
├─────────────────────────────────────────────────────────────────────────┤
│                                                                         │
│  Partition Occurrence:                                                 │
│  ┌─────────────────────────────────────────────────────────────────┐   │
│  │                                                                  │   │
│  │   Partition A              ✗              Partition B           │   │
│  │  ┌─────────────┐    Network severed    ┌─────────────┐          │   │
│  │  │             │    ═══════════════    │             │          │   │
│  │  │  Node 1     │                       │  Node 3     │          │   │
│  │  │  Node 2     │                       │  Node 4     │          │   │
│  │  │             │                       │  Node 5     │          │   │
│  │  │             │                       │             │          │   │
│  │  └─────────────┘                       └─────────────┘          │   │
│  │                                                                  │   │
│  │  Each partition perceives the other as "failed"                 │   │
│  └─────────────────────────────────────────────────────────────────┘   │
│                                                                         │
│  Split-Brain Problem:                                                  │
│  ┌─────────────────────────────────────────────────────────────────┐   │
│  │                                                                  │   │
│  │  Partition A:             Partition B:                          │   │
│  │  "Node 3,4,5 failed!"     "Node 1,2 failed!"                    │   │
│  │  → Node 1 becomes leader  → Node 5 becomes leader               │   │
│  │                                                                  │   │
│  │  Two leaders! → Data inconsistency, conflicts                   │   │
│  │                                                                  │   │
│  └─────────────────────────────────────────────────────────────────┘   │
│                                                                         │
│  Solution: Quorum                                                      │
│  ┌─────────────────────────────────────────────────────────────────┐   │
│  │                                                                  │   │
│  │  Must communicate with majority (N/2 + 1) nodes to be leader    │   │
│  │                                                                  │   │
│  │  Out of 5 nodes:                                                │   │
│  │  - Partition A (2 nodes): 2 < 3 → Cannot be leader              │   │
│  │  - Partition B (3 nodes): 3 ≥ 3 → Can be leader                 │   │
│  │                                                                  │   │
│  │  → Only one leader exists!                                       │   │
│  │                                                                  │   │
│  └─────────────────────────────────────────────────────────────────┘   │
│                                                                         │
└─────────────────────────────────────────────────────────────────────────┘

Partial Failure¶

┌─────────────────────────────────────────────────────────────────────────┐
│                     Partial Failure                                     │
├─────────────────────────────────────────────────────────────────────────┤
│                                                                         │
│  Inherent characteristic of distributed systems: Only parts can fail   │
│                                                                         │
│  ┌─────────────────────────────────────────────────────────────────┐   │
│  │                                                                  │   │
│  │  Ambiguous situation:                                           │   │
│  │                                                                  │   │
│  │  Node A ──Request──► Node B                                     │   │
│  │         ◄───?────                                               │   │
│  │         Timeout!                                                 │   │
│  │                                                                  │   │
│  │  Possible causes:                                               │   │
│  │  1. Request was lost                                            │   │
│  │  2. Node B failed                                               │   │
│  │  3. Request processed but response lost                         │   │
│  │  4. Node B is slow (response may come later)                    │   │
│  │                                                                  │   │
│  │  → Retry? Don't retry? No way to know the right decision!       │   │
│  │                                                                  │   │
│  └─────────────────────────────────────────────────────────────────┘   │
│                                                                         │
│  Mitigation Strategies:                                                │
│  ┌─────────────────────────────────────────────────────────────────┐   │
│  │  1. Idempotent design: Safe to retry                            │   │
│  │  2. Timeout tuning: Not too short, not too long                 │   │
│  │  3. Health checks: Periodic node status checks                  │   │
│  │  4. Circuit breaker: Fast failure on repeated failures          │   │
│  └─────────────────────────────────────────────────────────────────┘   │
│                                                                         │
└─────────────────────────────────────────────────────────────────────────┘

Byzantine Failure¶

┌─────────────────────────────────────────────────────────────────────────┐
│                     Byzantine Failure                                   │
├─────────────────────────────────────────────────────────────────────────┤
│                                                                         │
│  Normal failure: Node stops or doesn't respond (Crash Failure)         │
│  Byzantine failure: Node behaves incorrectly/maliciously               │
│                                                                         │
│  ┌─────────────────────────────────────────────────────────────────┐   │
│  │                                                                  │   │
│  │  Normal node:                    Byzantine node:                 │   │
│  │  - Follows protocol              - Lies                         │   │
│  │  - Accurate information          - Different messages to        │   │
│  │  - Consistent behavior             different nodes              │   │
│  │                                   - Random behavior              │   │
│  │                                                                  │   │
│  │  ┌─────┐    "value is 5"  ┌─────┐                               │   │
│  │  │  A  │─────────────────►│  B  │                               │   │
│  │  │(bad)│                  └─────┘                               │   │
│  │  │     │    "value is 7"  ┌─────┐                               │   │
│  │  │     │─────────────────►│  C  │                               │   │
│  │  └─────┘                  └─────┘                               │   │
│  │                                                                  │   │
│  │  B and C receive different values → Cannot reach consensus!     │   │
│  │                                                                  │   │
│  └─────────────────────────────────────────────────────────────────┘   │
│                                                                         │
│  Countermeasures:                                                      │
│  - Byzantine Fault Tolerant (BFT) algorithms                           │
│  - 3f + 1 nodes tolerate f Byzantine failures                          │
│  - Mainly used in blockchain (PBFT, Tendermint)                        │
│                                                                         │
│  In typical systems:                                                   │
│  - Internal nodes assumed trusted (Crash Failure model)               │
│  - Only validate external input                                        │
│                                                                         │
└─────────────────────────────────────────────────────────────────────────┘

6. Practice Problems¶

Exercise 1: Lamport Clock Calculation¶

Calculate the Lamport timestamp for each event in the following sequence:

P1: a ────────────► b ──────────────────► c
         │                       ▲
         ▼                       │
P2: ─────d ─────────► e ─────────f ────►

Exercise 2: Vector Clock Analysis¶

Determine the relationship (happens-before, concurrent) for the following Vector Clock values: - V1 = [2, 1, 0] - V2 = [1, 2, 0] - V3 = [2, 2, 1] - V4 = [3, 1, 0]

Exercise 3: Leader Election Design¶

Design a leader election mechanism for a distributed database with 5 nodes: - Handle network partitions - Prevent Split-Brain - Auto-recovery on leader failure

Next Steps¶

In 16_Consensus_Algorithms.md, let's learn about distributed consensus algorithms like Paxos and Raft!

References¶

"Distributed Systems" - Maarten van Steen, Andrew Tanenbaum
"Designing Data-Intensive Applications" - Martin Kleppmann
"Time, Clocks, and the Ordering of Events in a Distributed System" - Leslie Lamport
"The Fallacies of Distributed Computing" - L Peter Deutsch
Raft Consensus Algorithm - raft.github.io