Paxos Examples

Question 1

Consider a system with 2 proposers P1 and P2 and 3 acceptors R1, R2, R3. Associated with each proposer P is a local variable P.v. This local variable is a color which is "red" for P1 and "blue" for P2. The system uses the Paxos algorithm by which a majority of acceptors come to a consensus about the colors of P1 and P2.

Write down a scenario by which acceptor R1 accepts (T, V) = (1, "red") and also accepts (T, V) = (2, "blue")

Answer to Question 1

First Round

• Step P.1: P1 sends prepare(1)
• Step A.1: Acceptors R1, R2 receive prepare(1) and reply with
  promise(R.t, R.v, R.acceptT) = promise(1, null, null).
• Step P.2: P1 receives promise(1, null, null) from 2 of the 3 acceptors. So P1 sends
  propose(P.t, P.v) = propose(1, "red")
  to all acceptors. This message reaches acceptor R1 but does not reach the other acceptors.
• Step A.2: Acceptor R1 accepts (1, "red") and sends accept(1, "red") to all learners.

Next Round

• Step P.1: P2 sends prepare(2)
• Step A.1: Acceptors R2, R3 receive prepare(2) and reply with
  promise(R.t, R.v, R.acceptT) = promise(2, null, null).
  Acceptor R1 does not receive this prepare message.
• Step P.2: P2 receives promise(2, null, null) from 2 of the 3 acceptors. So P2 sends
  propose(P.t, P.v) = propose(2, "blue")
  to all acceptors. This message reaches acceptor R1 but does not reach the other acceptors.
• Step A.2: Acceptor R2 accepts (2, "blue") and sends accept(2, "blue") to all learners.

  Question 2

  Is the following true? If a majority of acceptors accepts (T, V) and another majority of acceptors accepts (T', V') then (T, V) = (T', V')?

  Answer to Question 2

  No, it's not true.

  Here is a scenario for the system with 2 proposers and 3 acceptors described in question 1.

  First Round

  • Step P.1: P1 sends prepare(1)
  • Step A.1: Acceptors R1, R2, R3 receive prepare(1) and reply with
    promise(R.t, R.v, R.acceptT) = promise(1, null, null).
  • Step P.2: P1 receives promise(1, null, null) from a majority of acceptors. So P1 sends
    propose(P.t, P.v) = propose(1, "red")
    to all acceptors. This message reaches all 3 acceptors
  • Step A.2: All 3 acceptors accept (1, "red") and sends accept(1, "red") to all learners.

  Next Round

  • Step P.1: P2 sends prepare(2)
  • Step A.1: Acceptors R1, R2, R3 receive prepare(2) and reply with
    promise(R.t, R.v, R.acceptT) = promise(2, "red", 1).
  • Step P.2: P2 receives promise(2, "red", 1) from a majority of acceptors. So P2 sends
    propose(P.t, P.v) = propose(2, "red")
    to all acceptors. This message reaches all 3 acceptors
  • Step A.2: All 3 acceptors accept (2, "red") and sends accept(2, "red") to all learners.

  ---

  K. Mani Chandy, Emeritus Simon Ramo Professor, California Institute of Technology