Distributed Systems Fundamentals: From CAP Theorem to Consensus Algorithms and Consistency Models

Single Server                  Distributed System
+-----------+               +-----+  +-----+  +-----+
|  App + DB |    vs         | N1  |--| N2  |--| N3  |
+-----------+               +-----+  +-----+  +-----+
                                  \    |    /
                             Network (unreliable)

Network partition occurs!

  [Node A]  ----X----  [Node B]
  data=1                data=1

  Client sends write(data=2) to Node A

  Option 1 (CP): Cannot sync with Node B → Reject request (sacrifice availability)
  Option 2 (AP): Update Node A only → Allow inconsistency (sacrifice consistency)

if (Partition) then
    Availability vs Consistency
else
    Latency vs Consistency

Strict Consistency
    |
Linearizability
    |
Sequential Consistency
    |
Causal Consistency
    |
Eventual Consistency

Time -->
Client A:  write(x=1) ------>
Client B:              read(x) --> must return 1

Real time:       A:write(x=1)  B:write(x=2)
Sequential OK:   B:write(x=2), A:write(x=1)
                 (as long as all nodes agree on this order)

A writes a post --> B writes a comment (causally related)
  --> All nodes see the post before the comment

C writes a post / D writes another post (no causal relation)
  --> Different nodes may see them in different orders

Time -->
Node A:  x=1 ......... x=1 (propagation) --> x=1
Node B:  x=0 ......... x=0 --> x=1 (slight delay)
Node C:  x=0 ......... x=0 --> x=1

           writes
Client --> [Leader] --> replication --> [Follower 1]
                                   --> [Follower 2]
                                   --> [Follower 3]
           reads
Client --> [any Follower 1, 2, or 3]

# Semi-synchronous replication pseudocode
def write(data):
    leader.write(data)
    ack_count = 1  # leader itself
    for follower in followers:
        if follower.replicate(data):
            ack_count += 1
            if ack_count >= 2:  # at least 1 follower confirmed
                return SUCCESS
    return FAILURE

[Leader A] <--> [Leader B] <--> [Leader C]
    |               |               |
[Follower]     [Follower]     [Follower]

         write(x=1)
Client --> [Node A] OK
       --> [Node B] OK
       --> [Node C] FAIL (down)

W=2 success --> Write succeeds!

         read(x)
Client --> [Node A] x=1
       --> [Node B] x=1
       --> [Node C] x=0 (stale)

R=2 --> return latest value (x=1)

hash(key) mod N = partition_number

key="user_123" --> hash --> 7 --> 7 mod 3 = 1 --> Partition 1
key="user_456" --> hash --> 2 --> 2 mod 3 = 2 --> Partition 2

Partition 0: A-F
Partition 1: G-M
Partition 2: N-S
Partition 3: T-Z

        0
       / \
     330   30
     /       \
   300        60
   |    Ring    |
   270        90
     \       /
     240   120
       \ /
       180

Node A: 0-90
Node B: 90-180
Node C: 180-270
Node D: 270-360

Add Node E at position 135 --> only keys 90-135 move from B to E

Phase 1: Prepare
  Proposer --> Acceptor: "Please prepare for proposal number n"
  Acceptor --> Proposer: "OK" (includes previously accepted value if any)

Phase 2: Accept
  Proposer --> Acceptor: "Please accept proposal n with value v"
  Acceptor --> Proposer: "Accepted" (consensus reached if majority accepts)

Time -->
           Term 1          Term 2
Follower: [Heartbeat]... [Timeout!] --> Candidate
Candidate: Votes for self + sends RequestVote to others
           Gets majority --> Elected as Leader!

Leader:   [Heartbeat]-->[Heartbeat]-->[Heartbeat]-->...

# Raft leader election pseudocode
class RaftNode:
    def __init__(self):
        self.state = "follower"
        self.current_term = 0
        self.voted_for = None
        self.election_timeout = random(150, 300)  # ms

    def on_timeout(self):
        self.state = "candidate"
        self.current_term += 1
        self.voted_for = self.id
        votes = 1  # self-vote

        for peer in self.peers:
            if peer.request_vote(self.current_term, self.log):
                votes += 1

        if votes > len(self.peers) // 2:
            self.state = "leader"
            self.send_heartbeats()

Client --> Leader: write(x=5)

Leader Log: [Term1:x=3] [Term1:y=7] [Term2:x=5]
                                        | AppendEntries
Follower1: [Term1:x=3] [Term1:y=7] [Term2:x=5] OK
Follower2: [Term1:x=3] [Term1:y=7] [Term2:x=5] OK
Follower3: [Term1:x=3] [Term1:y=7] (network delay)

Majority (3/5) replicated --> Commit! --> Respond to client

Phase 1: Prepare (Vote)
  Coordinator --> Participant A: "Can you commit?"
  Coordinator --> Participant B: "Can you commit?"
  A --> Coordinator: "Yes"
  B --> Coordinator: "Yes"

Phase 2: Commit (Execute)
  Coordinator --> A: "Commit!"
  Coordinator --> B: "Commit!"

Phase 1: CanCommit
Phase 2: PreCommit (with timeout)
Phase 3: DoCommit

Order Creation Saga:

T1: Create Order --> T2: Process Payment --> T3: Deduct Inventory --> T4: Start Shipping
                          | FAIL!
C2: Refund Payment <-- C1: Cancel Order

# Saga Orchestrator pseudocode
class OrderSaga:
    steps = [
        ("create_order", "cancel_order"),
        ("process_payment", "refund_payment"),
        ("update_inventory", "restore_inventory"),
        ("arrange_shipping", "cancel_shipping"),
    ]

    def execute(self):
        completed = []
        for action, compensation in self.steps:
            try:
                getattr(self, action)()
                completed.append(compensation)
            except Exception:
                # Run compensations in reverse
                for comp in reversed(completed):
                    getattr(self, comp)()
                raise SagaFailed()

Rules:
1. Increment counter on each event
2. Include counter when sending messages
3. On receive: max(own counter, received counter) + 1

Process A:  (1)--> (2)--> (3)---------> (6)
                          send          recv
Process B:        (1)--> (2)--> (4)--> (5)
                          recv          send

3 nodes: A, B, C

A: [1,0,0] --> [2,0,0] --> [2,0,0] send to B
B: [0,0,0] --> [0,1,0] --> [2,2,0] recv from A --> [2,3,0] send to C
C: [0,0,0] --> [0,0,1] --> [2,3,2] recv from B

def compare_vector_clocks(vc1, vc2):
    """Compare two vector clocks"""
    less = False
    greater = False
    for a, b in zip(vc1, vc2):
        if a < b:
            less = True
        elif a > b:
            greater = True

    if less and not greater:
        return "BEFORE"      # vc1 < vc2
    elif greater and not less:
        return "AFTER"       # vc1 > vc2
    elif not less and not greater:
        return "EQUAL"
    else:
        return "CONCURRENT"  # concurrent events!

HLC = (physical_time, logical_counter)

When physical times are equal, the logical counter determines ordering
--> Guarantees causal ordering within NTP error bounds

Node A --> "Are you alive?" --> Node B
Node A <-- "Yes!" <-- Node B

... timeout expires ...

Node A --> "Are you alive?" --> Node B
Node A <-- (no response) <-- Node B
--> Consider Node B failed

Phi value:
  phi = 1  --> 10% chance of failure
  phi = 2  --> 1% chance of failure
  phi = 3  --> 0.1% chance of failure

If above threshold (e.g., phi > 8) --> consider node failed

1. Node A pings Node B
2. No response --> A asks Nodes C, D to "indirect ping B"
3. C, D ping B --> still no response, B is suspected
4. After timeout, if still no response, B is removed
5. Gossip protocol spreads membership changes

Architecture:
  - Leaderless, Consistent Hashing
  - Quorum reads/writes (W + R > N)
  - Gossip protocol for membership
  - Last-Write-Wins conflict resolution
  - SSTable + Memtable storage

PACELC: PA/EL
  - During partition: Availability first
  - Normal operation: Low latency first

Architecture:
  - Globally distributed, strong consistency
  - TrueTime API: GPS + atomic clocks provide time uncertainty intervals
  - Paxos-based replication
  - External consistency guarantee

TrueTime:
  TT.now() --> [earliest, latest]
  Uncertainty interval typically 1-7ms

  On transaction commit:
  1. Assign timestamp s
  2. commit-wait: wait until TT.after(s) is true
  3. Wait for uncertainty interval to guarantee ordering

Architecture:
  - Consistent Hashing + virtual nodes
  - Sloppy Quorum: other nodes respond during failures
  - Hinted Handoff: data delivered to original node after recovery
  - Vector Clocks for versioning
  - Merkle Trees for anti-entropy