Understanding CAP Theorem, Paxos, and ZAB: Balancing Consistency and Availability

CAP Theory Overview

CAP theory, proposed by Eric Brewer, states that a distributed system can simultaneously satisfy at most two of three properties: Consistency (all nodes see the same latest data), Availability (every request receives a response), and Partition Tolerance (the system continues operating despite network partitions).

In large‑scale environments, network partitions are inevitable, forcing designers to choose between consistency and availability for each type of data.

Paxos Consensus Algorithm

Paxos, introduced by Leslie Lamport, guarantees strong consistency by requiring a majority (f+1 of 2f+1) of nodes to agree on a proposal. It achieves high availability by allowing the system to remain operational as long as enough nodes are up, dramatically increasing overall reliability.

The algorithm proceeds in two phases: Phase 1 (prepare) where a proposer obtains the highest numbered accepted proposal from a majority, and Phase 2 (accept) where it proposes a value based on that information. If a majority accepts, the value is chosen.

ZooKeeper's ZAB Protocol

ZAB (ZooKeeper Atomic Broadcast) builds on Paxos by electing a single leader to serialize proposals, eliminating the need for the prepare phase and avoiding livelocks caused by multiple proposers. The leader ensures total order of updates, while followers act as acceptors.

When the leader fails, a new leader is elected using a Paxos‑style proposal, preserving consistency.

Key Takeaways

CAP theory highlights the unavoidable trade‑off between consistency and availability under network partitions. Paxos provides a simple yet powerful way to achieve strong consistency while maximizing availability, and ZAB adapts Paxos for practical use in systems like ZooKeeper, offering ordered updates and leader‑based optimization.