Distributed Consistency Algorithms: CAP, BASE, 2PC, 3PC, Paxos, Raft, ZAB, and NWR Model

CAP Theorem

In a distributed system, it is impossible to simultaneously guarantee consistency, availability, and partition tolerance; at most two of these properties can be satisfied.

BASE Theory

BASE stands for Basically Available, Soft state, and Eventually consistent, offering a pragmatic trade‑off derived from CAP.

Two‑Phase Commit (2PC)

2PC splits a transaction into a voting phase and a commit/abort phase, ensuring atomicity but suffering from blocking, single‑point‑of‑failure, and potential data inconsistency.

Phase 1

The coordinator asks participants if they can commit; participants log undo/redo information and respond Yes or No.

Phase 2

If all vote Yes, the coordinator sends a commit request; otherwise it sends an abort request. Participants act accordingly and acknowledge.

Three‑Phase Commit (3PC)

3PC improves on 2PC by adding timeouts and an extra preparation stage, creating CanCommit, PreCommit, and DoCommit phases to avoid blocking.

CanCommit

Coordinator asks if participants can commit; participants reply Yes or No.

PreCommit

If all replied Yes, the coordinator sends a pre‑commit request; participants execute the transaction and acknowledge.

DoCommit

The coordinator sends a final commit request; participants finalize the transaction and acknowledge, or abort if any step fails.

Paxos Algorithm

Paxos achieves consensus in fault‑tolerant systems using proposers, acceptors, and learners, proceeding through a prepare phase and an accept phase to agree on a single value.

Raft Consensus Algorithm

Raft simplifies Paxos by electing a leader (candidate, follower, leader roles) and replicating logs; it handles leader election, log replication, and recovery from network partitions.

ZAB Protocol

ZAB (Zookeeper Atomic Broadcast) provides atomic broadcast and crash recovery for Zookeeper, using leader‑based replication, quorum acknowledgments, and versioned proposals (zxid) to ensure consistency.

NWR Model

Amazon Dynamo’s NWR model lets users choose the trade‑off between consistency, availability, and partition tolerance by configuring N (replicas), W (writes), and R (reads) with W+R>N, and resolves conflicts with vector clocks.