Understanding Consistency in Distributed Systems: Strong vs Weak, CAP/FLP Theorems, and Consensus Protocols (2PC, 3PC, Paxos)

What is Consistency?

Consistency in distributed systems refers to the protocol by which multiple nodes agree on a value. It can be classified as strong consistency, where all nodes hold identical data at any time, and weak (eventual) consistency, where data converges over time.

Use Cases for Consistent Distributed Systems

Multi‑node read/write services that require high availability and scalability, such as ZooKeeper, DNS, and Redis clusters.

Challenges in Distributed Systems

Asynchronous messaging (delays, loss, lack of synchrony)

Node fail‑stop

Fail‑recovery

Network partitions

Byzantine faults (assuming a trusted internal network)

Designing a consistent system typically assumes no Byzantine failures.

The FLP impossibility theorem states that in the presence of node crashes, a system cannot simultaneously guarantee availability and strong consistency. The CAP theorem expresses a trade‑off among consistency, availability, and partition tolerance, of which only two can be fully achieved.

Two‑Phase Commit (2PC)

2PC is a distributed transaction protocol that ensures atomicity across multiple data shards. It involves a coordinator and participants and proceeds in two phases: a prepare phase where participants log intent and vote, and a commit/abort phase based on the votes.

Advantages: simple principle, easy to implement.

Disadvantages: synchronous blocking, single‑point coordinator failure, possible inconsistency if the coordinator crashes after sending commit, and reliance on timeouts.

Three‑Phase Commit (3PC)

3PC extends 2PC with an additional pre‑commit phase to avoid blocking, but it still cannot guarantee absolute consistency.

Process: after collecting votes, the coordinator sends a prepare‑commit command; participants lock resources and can roll back; a final commit phase follows after acknowledgments.

Paxos Consensus Algorithm

Paxos is a foundational consensus algorithm that solves the single‑point failure problem; many other algorithms are its simplifications. It involves three roles: Proposer, Acceptor, and Learner.

Proposer: proposes values.

Acceptor: votes to accept or reject proposals.

Learner: learns the chosen value from a majority of acceptors.

The algorithm proceeds in two phases: a prepare phase where a proposer requests a proposal number and acceptors promise not to accept lower numbers, and an accept phase where the proposer sends the value to be chosen. Learners record accepted proposals and determine consensus when a majority is reached.