L. Lamport.
Paxos made simple.
ACM SIGACT News, 32(4):18-25, 2001.
pdf link:
http://www.disi.unitn.it/~montreso/ds/sy...http://www.disi.unitn.it/~montreso/ds/syllabus/papers/paxos-
Bibtex:
@article{lamport2001pms,
title={{Paxos made simple}},
author={Lamport, L.},
journal={ACM SIGACT News},
volume={32},
number={4},
pages={18--25},
year={2001},
}
Paxos algorithm is proposed to solve the problem: get a set of processes to reach consensus on a single proposed value. The algorithm itself actually does not care what value is chose, just as long as only a single value that have been proposed can be chosen and processes cannot learn that a value has been chosen until it really has been chosen(can not predit).
The algorithm is based on a model that processes communicate with each other by sending messages which are asynchronous, arbitrarily long, might be duplicate or lost. Each process plays as one, two or all three roles: proposers, acceptor and learner.
The paper first figure out a small set of requirements that the algorithm must satisfy and refine them step by step into something that can be easily implemented with clear logic. Let's see an example to clarify.
Proposers are p1 and p2.
Acceptors are a1, a2, and a3.
p1 sends prepare for proposal 1 to a1 and a2.
a1 and a2 reply to p1.
p2 sends prepare for proposal 2 to a2 and a3.
a2 and a3 reply to p2.
p1 sends accept request to a1 and a2 for proposal 1 with value A and p1 got to select which value to propose.
a1 accepts proposal 1.
a2 does not accept proposal 1, a2 promised p2 it wouldn't accept proposals < 2.
p2 sends accept request to a2 and a3 for proposal 2 with value B and p2 also got to select which value to propose.
a2 accepts proposal 2.
a3 accepts proposal 2.
now {a2, a3} is a majority of acceptors, so proposal 2 is chosen. Then, the chosen value is B.
p1 sends prepare for proposal 3 to a1 and a2.
a1 replies and it last accepted proposal 1 for A.
a2 replies and it last accepted proposal 2 for B.
p1 sends accept request to a1 and a2 for proposal 3 with value B(value must match the one from proposal 2)
a1 and a2 accept proposal 3.
Then, how do the learners learn? If each acceptor informs each learner, it will cause too many messages to be sent. Moreover, using a single distinguish learn will cause single point of failure. So we compromise with a set of distinguished learners.
The significance of Paxos algorithm is that it can be used to construct a distributed system of state machines. It can keep a collection of state machines consistent by running an infinite number of instances of Paxos simultaneously. This paper has made a very clear logic to clarify this algorithm step by step which make people easier to understand. It raises a good example of how to organize logic when write a good paper, especially when clarifying or demonstrating some theoretical logic and algorithms.