Tutorial 8: Paxos

Question 1

Write a program (in pseudocode) for implementing an RSM using the Paxos algorithm.

Answer 1

• The values to agree on are the commands
• One instance of the Paxos algorithm per command
• Each process has all three roles (proposer, acceptor, learner)
• A leader, which has to be elected, is the only process that issues proposals (i.e., distinguished proposer and learner). The leader determines the order of commands.

If n is the number of commands issued by the client we need n instances of the Paxos algorithm.

• Clients send commands to the leader
• Leader proposes each command to a specific Paxos instance (cmdi → pi)
• As cmdi is the only proposal in pi every pi decides on command cmdi in the end.
• Each server sees the same sequence of need-to-be-executed commands.

Question 2

Assume that at fictitious time t, two processes think that they are the distinguished process (i.e., proposer & learner). Discuss what happens to the system in terms of the safety and liveness requirements.

Answer 2

In the proposed case, the safety requirement is still maintained. However the liveness requirement is broken and the system may not reach consensus until only a single leader is elected. By maintaining property P2c the system is guaranteed to be safe even in this case, since different processes will never disagree on a chosen value.

Property P2c says: For any v and n, if a proposal (i.e., accept request) with value v and proposal number n is issued, then there is a set S comprised of a majority of acceptors such that either

• no acceptor in S has ever accepted any proposal numbered less than n
• or, v is the value of the highest-numbered proposal among all proposals numbered less than n accepted by the acceptors in S

However if the system has two distinct leaders, each is going to keep “flooding” the system with different proposals preventing normal operation. This happens because new values may never be agreed on, until only one leader is elected.