Review for Paxos

The consensus and fault tolerant in data processing is a vital problem, especially in large-scale distributed system. The Paxos is a consensus algorithm which ensures only one value proposed has been chosen, after which the processes can learn from the chosen value.

The key idea is three classes of agents: proposers, accepters and learner.

Proposers: propose (m, v) 
Acceptors: accept proposals and choose values 
Learners: learn the chosen values 

Phase 1: Prepare

Proposer proposes proposal number n

Acceptor responds if n > any prepare request to which it has responded

Phase 2: Accept

Proposer proposes (n, v) such that v = value of highest number proposal among phase 1 responses, or any if no reported proposal

Acceptor can accept request for a proposal unless it has already responded to a prepare request having a number greater than n.

The assumptions of Paxos is that the message takes arbitrary time for delivery, and can be duplicated, can be lost. However, the message cannot be corrupted. Given this, it is not appropriate to implement Paxos algorithm when it is likely to have message corruptions.

I think it maybe a classical consensus algorithm. I am not sure, but I think it is simple and practical. Thus it maybe influential in the following years.