Understanding Consistency in Distributed Systems: Strong vs Weak, CAP Theorem, 2PC, 3PC, and Paxos

Consistency refers to the agreement among multiple nodes in a distributed system to reach the same value, and it can be classified as strong consistency or weak (eventual) consistency.

Strong consistency : All nodes hold identical data at any moment, so reading the same key on any node returns the same value.

Weak consistency : Nodes may diverge temporarily; the most common implementation is eventual consistency, where data across nodes converges over time.

Typical distributed scenarios that require consistency include multi‑node read/write services for high availability and scalability, such as ZooKeeper, DNS, and Redis clusters.

Distributed systems face challenges such as asynchronous messaging, node crash‑stop failures, fail‑recovery, network partitions, and Byzantine faults. Designing a consistent system usually assumes a trusted internal network without Byzantine problems.

The article also mentions the FLP impossibility result (no algorithm can guarantee both availability and strong consistency when nodes may crash) and the CAP theorem, which states that a system can provide at most two of the three guarantees: consistency, availability, and partition tolerance.

Several protocols ensure consistency:

2‑Phase Commit (2PC)

A two‑stage locking protocol that guarantees atomicity across multiple data shards (distributed transaction). It designates a coordinator and participants, and proceeds in two phases:

Phase 1 – The coordinator asks each participant to prepare; participants write undo/redo logs and reply with yes/no.

Phase 2 – If all participants answered yes, the coordinator commits; otherwise it aborts. After commit/rollback, resources are released and acknowledgments are sent.

Advantages: simple principle, easy to implement. Drawbacks: synchronous blocking, single point of failure, possible inconsistency if the coordinator fails after sending commit, and reliance on timeout mechanisms.

3‑Phase Commit (3PC)

An extension of 2PC that adds a pre‑commit stage to avoid blocking, but it still cannot guarantee consistency in all failure cases. The three stages are query, pre‑commit, and commit. The coordinator sends a prepare‑commit command after receiving votes, participants lock resources, and a final commit is issued after acknowledgments.

Paxos Algorithm

Paxos is a fundamental consensus algorithm that underlies many consistency protocols. It involves three roles:

Proposer : proposes values.

Acceptor : votes to accept or reject proposals.

Learner : learns the chosen value once a majority of acceptors agree.

The algorithm proceeds in two phases:

Phase 1 (Prepare)

Proposer selects a proposal number n and sends a prepare request to a majority of acceptors.

Each acceptor promises not to accept proposals with numbers lower than n and may return the highest-numbered proposal it has already accepted.

Phase 2 (Accept)

If the proposer receives enough promises, it sends an accept request with value and number n to the acceptors.

Acceptors accept the proposal if n is not less than any previously promised number.

Once a majority of acceptors have accepted, learners are notified and the value is chosen.

These protocols illustrate how distributed systems achieve consistency despite failures and network partitions.