Consensus Problem

Back to Computer-Science-Concepts

A fundamental problem in distributed computing, which requires agreement among a number of processes for a single data value.

Two-Phase Commit

  1. A self assigned coordinator contacts every node, propose a value and gather boolean responses
  2. if everyone agrees, commit

Solves consensus problem assuming no failures.

Three-Phase Commit

Similar to 2PC. Second phase of 2PC has two sub-phases.

  1. Coordinator proposes
  2. If everyone agrees, prepare to commit, communicating the result of the vote to every node
  3. commit (or abort if delivery of prepare to commit to any node fails)

Problem: network partitioning can cause inconsistenet states. In network systems, fail-stop isn't the only model of failures. Nodes can follow a fail-recover fault model. Coordinator can recover and interfere with another recovery node. Failure in this case isn't crashing, but could be instead network interuptions.

Paxos -- source

Phase 1a: Prepare -- source

A Proposer (the leader) creates a proposal identified with a number N. This number must be greater than any previous proposal number used by this Proposer. Then, it sends a Prepare message containing this proposal to a Quorum of Acceptors. The Proposer decides who is in the Quorum.

Phase 1b: Promise

If the proposal's number N is higher than any previous proposal number received from any Proposer by the Acceptor, then the Acceptor must return a promise to ignore all future proposals having a number less than N. If the Acceptor accepted a proposal at some point in the past, it must include the previous proposal number and previous value in its response to the Proposer.

Otherwise, the Acceptor can ignore the received proposal. It does not have to answer in this case for Paxos to work. However, for the sake of optimization, sending a denial (Nack) response would tell the Proposer that it can stop its attempt to create consensus with proposal N.

Phase 2a: Accept Request

If a Proposer receives enough promises from a Quorum of Acceptors, it needs to set a value to its proposal. If any Acceptors had previously accepted any proposal, then they'll have sent their values to the Proposer, who now must set the value of its proposal to the value associated with the highest proposal number reported by the Acceptors. If none of the Acceptors had accepted a proposal up to this point, then the Proposer may choose any value for its proposal.

The Proposer sends an Accept Request message to a Quorum of Acceptors with the chosen value for its proposal.

Phase 2b: Accepted

If an Acceptor receives an Accept Request message for a proposal N, it must accept it if and only if it has not already promised to any prepare proposals having an identifier greater than N. In this case, it should register the corresponding value v and send an Accepted message to the Proposer and every Learner. Else, it can ignore the Accept Request.


Same goal and efficiency as Paxos, but uses a different structure aimed to be more understandable for humans