Distributed Systems & Consensus Algorithms TECHNICAL REFERENCE DOCUMENT

Distributed Systems &

Consensus Algorithms
CAP Theorem, Raft, Paxos, CRDTs, and Eventual Consistency

A rigorous technical exploration of distributed systems theory and practice. Covers the CAP and
PACELC theorems, Paxos and Raft consensus protocols, conflict-free replicated data types
(CRDTs), vector clocks, distributed transactions (2PC, Saga, MVCC), and failure detector theory.
Intended for systems engineers and distributed database architects.

Version v2.4

Date June 2025

Classification Technical Reference

Confidential — Internal Technical Reference Page 1

Distributed Systems & Consensus Algorithms TECHNICAL REFERENCE DOCUMENT

Table of Contents
1. CAP & PACELC Theorems 3

2. Logical Clocks & Causality 4

3. Paxos: Single-Decree & Multi-Paxos 5

4. Raft Consensus Protocol 6

5. Byzantine Fault Tolerance 7

6. CRDTs: Conflict-Free Data Structures 8

7. Distributed Transactions 9

8. Replication Models 10

9. Consistent Hashing & Partitioning 11

10. Gossip Protocols 12

11. Failure Detectors 13

12. Systems Comparison Matrix 14

Confidential — Internal Technical Reference Page 2

Distributed Systems & Consensus Algorithms TECHNICAL REFERENCE DOCUMENT

1. CAP & PACELC Theorems

Brewer's CAP theorem states that a distributed system can provide at most two of three guarantees:
Consistency (all nodes see the same data), Availability (every request receives a response), and Partition
Tolerance (the system operates despite network partitions). Since partitions are unavoidable in real
networks, the practical choice is CP vs AP.

1.1 PACELC Extension

PACELC extends CAP: If Partition (P), choose Availability (A) or Consistency (C); Else (E — no partition),
choose Latency (L) or Consistency (C). This captures the always-present latency/consistency tradeoff.

System Partition Choice Normal Choice Classification

Zookeeper C C PC/EC

Cassandra A L PA/EL

DynamoDB A L (tunable) PA/EL

CockroachDB C C PC/EC

MongoDB C (w: majority) L (w: 1) PC/EL

Spanner C C PC/EC

Confidential — Internal Technical Reference Page 3

Distributed Systems & Consensus Algorithms TECHNICAL REFERENCE DOCUMENT

2. Logical Clocks & Causality

2.1 Lamport Timestamps
Lamport's algorithm assigns a monotonically increasing integer to each event. Rules: (1) increment
counter before each event; (2) on send, include current timestamp; (3) on receive, set counter = max(local,
received) + 1. Lamport timestamps establish a total order consistent with causality but cannot detect
concurrent events.

2.2 Vector Clocks

Vector clocks extend Lamport with per-process counters V[n]. Event A happens-before B iff V_A[i] ≤ V_B[i]
for all i and V_A[j] < V_B[j] for at least one j. Concurrent events: neither dominates. Used in Dynamo-style
systems for conflict detection.

2.3 Hybrid Logical Clocks (HLC)

HLC combines physical time with logical counters: l.j = max(l.j, pt.j) where pt is wall-clock time. This
enables causality tracking while preserving approximate wall-clock order, critical for globally distributed
databases like CockroachDB.

Confidential — Internal Technical Reference Page 4

Distributed Systems & Consensus Algorithms TECHNICAL REFERENCE DOCUMENT

3. Paxos: Single-Decree & Multi-Paxos

Paxos achieves consensus among f+1 of 2f+1 nodes despite f failures. Two phases: Prepare/Promise
(Phase 1) and Accept/Accepted (Phase 2).

3.1 Phase Details

• Phase 1a (Prepare): Proposer sends Prepare(n) to majority of acceptors.
• Phase 1b (Promise): Acceptor responds with highest accepted (n, v) or empty.
• Phase 2a (Accept): Proposer sends Accept(n, v) — v is highest-numbered from promises.
• Phase 2b (Accepted): Acceptor accepts if n ≥ any promised ballot.
• Commit: When proposer hears Accept from majority, value is decided.

3.2 Multi-Paxos Optimisations

Multi-Paxos skips Phase 1 for subsequent commands once a stable leader exists. Leader leases
(time-bounded) eliminate Phase 1 read quorums, reducing read latency from 2 RTT to 1 RTT. Pipelined
Accept messages allow concurrent in-flight instances.

Confidential — Internal Technical Reference Page 5

Distributed Systems & Consensus Algorithms TECHNICAL REFERENCE DOCUMENT

4. Raft Consensus Protocol

Raft decomposes consensus into leader election, log replication, and safety. It guarantees: Election Safety
(at most one leader per term), Log Matching (identical entries at same index), Leader Completeness
(committed entries preserved in future leaders).

4.1 Leader Election

Nodes start as followers. If no heartbeat within election timeout (150–300 ms randomised), a follower
becomes a candidate and broadcasts RequestVote(term, lastLogIndex, lastLogTerm). A vote is granted if
the candidate's log is at least as up-to-date.

4.2 Log Replication

Leader appends entries and sends AppendEntries RPCs in parallel. Entry is committed once replicated to
a majority. Leaders never overwrite their own log — the key difference from Paxos.

Property Raft Multi-Paxos ZAB (Zookeeper)

Leader election Random timeout Back-off ballot FIFO epoch

Log ordering Strict sequential Slot-based Epoch-ordered

Read linearisability ReadIndex/Lease Leader lease Yes

Reconfiguration Joint consensus View change Dynamic quorum

Implementations etcd, TiKV, CockroachDB Chubby, Spanner Zookeeper

Confidential — Internal Technical Reference Page 6

Distributed Systems & Consensus Algorithms TECHNICAL REFERENCE DOCUMENT

5. Byzantine Fault Tolerance

Byzantine faults are arbitrary failures (crashes, corrupted messages, malicious nodes). BFT requires 3f+1
nodes to tolerate f faults. PBFT (Practical Byzantine Fault Tolerance) achieves this in O(n²) messages per
consensus round via pre-prepare, prepare, and commit phases.

5.1 Tendermint & Modern BFT

Tendermint (used in Cosmos blockchain) achieves BFT consensus in two communication steps under
happy-path and is optimistically linear. HotStuff (used in Diem/Libra) reduces message complexity to O(n)
per phase using threshold signatures and a chained 3-phase pipeline.

Confidential — Internal Technical Reference Page 7

Distributed Systems & Consensus Algorithms TECHNICAL REFERENCE DOCUMENT

6. CRDTs: Conflict-Free Data Structures

CRDTs guarantee eventual consistency without coordination by ensuring merge operations form a
join-semilattice: commutative, associative, idempotent.

CRDT Type Operation Merge Rule Example Use Case

G-Counter Increment only max per node View counts

PN-Counter Increment/Decrement G-Counter pair Likes/dislikes

G-Set Add only Union Tags

2P-Set Add/Remove (tombstone) Union both sets Shopping cart

OR-Set (ORSWOT) Add/Remove with tokens Token set union Multi-user lists

LWW-Register Assign value Max timestamp wins Last-write-wins map

RGA Seq insert/delete Causal ordering Collaborative text

Confidential — Internal Technical Reference Page 8

Distributed Systems & Consensus Algorithms TECHNICAL REFERENCE DOCUMENT

7. Distributed Transactions
7.1 Two-Phase Commit (2PC)
2PC uses a coordinator: Phase 1 (Prepare) asks participants to vote commit/abort; Phase 2
(Commit/Abort) broadcasts the decision. Blocking failure: if coordinator crashes after Phase 1, participants
are stuck holding locks. 3PC adds a pre-commit phase to reduce blocking.

7.2 Saga Pattern

Sagas decompose a distributed transaction into local transactions with compensating transactions for
rollback. Choreography-based: events drive next steps. Orchestration-based: central saga orchestrator
drives state machine. No distributed locks; eventual consistency is accepted.

7.3 MVCC
Multi-Version Concurrency Control maintains multiple versions of rows tagged with transaction IDs.
Readers see a snapshot consistent at their start time; writers create new versions. Garbage collection
removes versions no longer visible to any active transaction.

Confidential — Internal Technical Reference Page 9

Distributed Systems & Consensus Algorithms TECHNICAL REFERENCE DOCUMENT

8. Replication Models
Replication strategies balance consistency, availability, and write amplification.

Strategy Description Used By

Primary-Backup All writes to primary; sync/async replicationHigh

to replicas
read scale; failover via VIP

Multi-Primary All nodes accept writes; conflict resolution required

Cassandra, CouchDB

Chain Replication Write enters head, propagates to tail; readsStrong

from tail
consistency, high throughput

Raft-based Replicated log drives state machine; leaderetcd,

handles
TiKV,
writes
CockroachDB

Confidential — Internal Technical Reference Page 10

Distributed Systems & Consensus Algorithms TECHNICAL REFERENCE DOCUMENT

9. Consistent Hashing & Partitioning

Consistent hashing maps keys to a virtual ring, minimising key movement on node changes.

Confidential — Internal Technical Reference Page 11

Distributed Systems & Consensus Algorithms TECHNICAL REFERENCE DOCUMENT

10. Gossip Protocols

Gossip (epidemic) protocols spread information in O(log N) rounds with O(N log N) messages total.

Confidential — Internal Technical Reference Page 12

Distributed Systems & Consensus Algorithms TECHNICAL REFERENCE DOCUMENT

11. Failure Detectors

Chandra-Toueg classify detectors by completeness and accuracy. PHI Accrual Detector (Cassandra)
outputs a suspicion level phi, allowing adaptive timeouts based on network jitter history.

Confidential — Internal Technical Reference Page 13

Distributed Systems & Consensus Algorithms TECHNICAL REFERENCE DOCUMENT

12. Systems Comparison Matrix

System Consistency Availability Partition Transactions Geo-dist

Spanner Linearisable High CP Yes (2PL+2PC) Yes (TrueTime)

Cassandra Tunable Very High AP LWT (Paxos) Multi-DC

CockroachDB Serialisable High CP Yes (SSI) Yes

DynamoDB Eventual/Strong Very High AP Yes (2PC) Global Tables

Zookeeper Linearisable Medium CP No No

MongoDB Tunable High CP/AP Yes (replica set) Atlas Global

Design Principle: There is no free lunch in distributed systems. Every consistency guarantee
costs latency; every availability guarantee risks staleness. Choose explicitly, not by accident.

Confidential — Internal Technical Reference Page 14