Normal operation: You can have C + A + P (no partition occurring)

During partition:
┌─────────────┐         ╳         ┌─────────────┐
│  Node A      │    (partition)    │  Node B      │
│  data: v2    │         ╳         │  data: v1    │
└─────────────┘                    └─────────────┘

CP choice: Node B refuses reads (unavailable) until partition heals
AP choice: Node B serves stale v1 (inconsistent) but stays available

IF Partition:
    Choose Availability or Consistency (same as CAP)
ELSE (normal operation):
    Choose Latency or Consistency
    
Format: PA/EL, PC/EC, PA/EC, PC/EL

Linearizability (strongest)
     │
     ▼
Sequential Consistency
     │
     ▼
Causal Consistency
     │
     ▼
Eventual Consistency (weakest)

Timeline (real time →):

Client A: |--write(x=1)--|
Client B:          |--read(x)--| must return 1
Client C:                   |--read(x)--| must return 1

Once ANY client sees x=1, ALL subsequent reads must see x=1

Client A: write(x=1), write(x=2)
Client B: read(x)=2, read(x)=1  ← INVALID (violates A's program order)
Client B: read(x)=1, read(x)=2  ← VALID

Client A: write(x=1)
Client B: write(x=2)
Client C: read(x)=1, read(x)=2  ← VALID
Client D: read(x)=2, read(x)=1  ← INVALID (must agree with C's order)

Causal relationship: A "happened before" B if:
1. A and B are in the same process, A before B
2. A is a send, B is the corresponding receive
3. Transitivity: A→B and B→C implies A→C

Example:
Client A: write(x=1)
Client B: read(x)=1, write(y=2)  ← y=2 causally depends on x=1
Client C: MUST see x=1 before y=2 (causal order)
          MAY see other unrelated writes in any order

t=0: Client writes x=1 to Node A
t=1: Node A has x=1, Node B has x=0 (stale)
t=2: Node A has x=1, Node B has x=0 (still propagating)
t=5: Node A has x=1, Node B has x=1 (converged)

During t=1 to t=4: reads from Node B return stale data

Normal operation:
┌────────┐  heartbeat  ┌──────────┐  heartbeat  ┌──────────┐
│ Leader  │────────────►│ Follower  │◄────────────│ Follower  │
│ (term 1)│            │           │             │           │
└────────┘             └──────────┘             └──────────┘

Election timeout (no heartbeat received):
┌──────────┐  RequestVote  ┌──────────┐
│ Candidate │─────────────►│ Follower  │
│ (term 2)  │◄─────────────│ (grants)  │
└──────────┘   VoteGranted └──────────┘
     │
     │ Majority votes received
     ▼
┌────────┐
│ Leader  │  (term 2, begins serving)
│         │
└────────┘

Client request: "SET x=5"

Leader                    Followers
  │                         │
  │ 1. Append to local log  │
  │                         │
  │── AppendEntries ───────►│  2. Send to followers
  │                         │
  │◄── Success ─────────────│  3. Followers append
  │                         │
  │ 4. Entry committed       │  (majority acknowledged)
  │    (apply to state)      │
  │                         │
  │── AppendEntries ───────►│  5. Notify followers to commit
  │   (commitIndex updated)  │

Phase 1 (Prepare):
Proposer ──[Prepare(n)]──► Acceptors
Acceptors ──[Promise(n)]──► Proposer  (if n > any previous)

Phase 2 (Accept):
Proposer ──[Accept(n, value)]──► Acceptors
Acceptors ──[Accepted(n, value)]──► Learners

Node A:  1    2    3         6    7
         │    │    │         ▲    │
         │    │    └────►────┘    │
         │    │         msg(3)    │
Node B:  1    2    3    4    5    6
              │              ▲
              └────►─────────┘
                   msg(2)
Node C:  1    2    3    4    5    6

Node A: [A:1, B:0, C:0]
Node A sends to B: message carries [A:1, B:0, C:0]
Node B receives: B = max([A:0, B:1, C:0], [A:1, B:0, C:0]) + increment B
                 B = [A:1, B:2, C:0]

[2,1,0] < [2,2,0]  → causally ordered
[2,1,0] ∥ [1,2,0]  → concurrent (conflict!)

HLC = (physical_time, logical_counter)

- Uses physical time when possible (for human-meaningful timestamps)
- Falls back to logical counter when physical clocks are close
- Bounded drift from physical time

TrueTime API:
  tt.now() → returns [earliest, latest] interval
  
  Guarantee: actual time is within the interval
  Uncertainty: typically 1-7ms (GPS + atomic clocks)
  
  Spanner's rule: wait out uncertainty before committing
  → Ensures linearizability with ~7ms commit latency

Byzantine (arbitrary behavior)
     │
     ▼
Omission (may fail to send/receive)
     │
     ▼
Crash-Recovery (may crash and restart)
     │
     ▼
Crash-Fail (crashes permanently)

The problem: In an asynchronous system, you cannot distinguish between:
1. A crashed node
2. A very slow node

If you wait forever → no liveness (system hangs)
If you decide without the slow node → it might have voted differently

No timeout is "correct" because the system is asynchronous
(no bound on message delivery time)

Normal:
┌─────────────────────────────────────┐
│  [Leader] ←→ [Follower] ←→ [Follower] │
└─────────────────────────────────────┘

Network partition:
┌──────────────┐    ╳    ┌──────────────┐
│  [Leader A]   │         │  [Leader B]   │  ← TWO leaders!
│  [Follower]   │         │  [Follower]   │
└──────────────┘         └──────────────┘

Both sides accept writes → data divergence → SPLIT BRAIN

5-node cluster, partition into [3] and [2]:

[Node1, Node2, Node3]  |  [Node4, Node5]
     Majority (3/5)    |    Minority (2/5)
     Keeps leader      |    Steps down
     Accepts writes    |    Rejects writes

Epoch/Term numbers prevent stale leaders:

Leader A (term=1) gets partitioned
Leader B (term=2) elected by majority

Leader A recovers, tries to write with term=1
Storage layer rejects: term=1 < current_term=2

┌────────┐  write(term=1)  ┌─────────┐
│Leader A │───────────────►│ Storage  │──► REJECTED (stale term)
│(stale)  │                │ (term=2) │
└────────┘                 └─────────┘

When split-brain detected:
1. Surviving partition sends "kill" signal to other partition
2. Uses out-of-band mechanism (IPMI, power management)
3. Guarantees the other side is truly dead before proceeding

Used in: Pacemaker/Corosync clusters, some database HA setups

┌────────┐         ┌────────┐
│ Node A  │    ╳    │ Node B  │
│ (data)  │         │ (data)  │
└────┬───┘         └────┬───┘
     │                   │
     └───────┬───────────┘
             │
      ┌──────┴──────┐
      │   Witness    │  ← Lightweight node, no data
      │  (tiebreaker)│     Votes in elections only
      └─────────────┘

Designing a system? Ask:

1. What consistency do we need?
   - Financial: Linearizability (CP)
   - Social feed: Eventual consistency (AP)
   - Shopping cart: Causal consistency

2. What's our partition strategy?
   - CP: Reject requests from minority partition
   - AP: Serve all requests, reconcile later

3. How do we detect/handle failures?
   - Heartbeats + timeouts for crash detection
   - Quorum writes for durability
   - Fencing tokens for stale leader prevention

4. How do we order events?
   - Single leader: Leader assigns order
   - Multi-leader: Vector clocks for conflict detection
   - Global order needed: Consensus (Raft)