Paxos is a consensus protocol in a network of unreliable computers for implementing a fault-tolerant distributed system to ensure that one consistent value is chosen. There are three basic roles for the nodes that are participating in it: proposers, acceptors & learners. Proposers are nodes that are trying to get this "chosen" value across all of the participating nodes, acceptors are nodes that receive proposals and could vote on which proposals should be accepted while learners just learn the correct value that has been voted by the majority of the acceptors.
The following is how the algorithm will work on a typical system. Firstly, we enter the proposal phase in which a proposer selects a value n and sends it to the acceptors. This proposal could be rejected if an acceptor has received a proposal with a value greater than n. Else, it will be accepted. In the second phase, the proposer receives a response to its proposal from a majority of acceptors in which it will response with an accept request to each of those acceptors with a value v where v is the value of the highest-numbered proposal among the responses. In my opinion, the structure of this paper makes Paxos harder to understand than it actually is since the author proves each subsection of the Paxos algorithm before leading up to the overview of the protocol. If the author had given us the overview of the protocol in the beginning, that will be very helpful. However, the simplicity of the Paxos itself makes it, as we know today, very popular and have many papers that are written to further optimize it. So I'd say that this paper is very influential.
The paper "Paxos Made Practical" takes one more step on how to actually implement the algorithm in a real-life situation, how to handle nodes that failed and how to add a state machine to maintain replicas of the data since previous works that claim to use Paxos as a consensus protocol leaves many details unspecified. However, I feel that for this paper, its influential for itself is not that much since it's too specific on one implementation although I guess, it will help people who will like to design a system that utilizes Paxos Protocol.
On the other hand, we have Chubby lock service that is intended to provide coarse grained-locking in a loosely-coupled distributed system (such as one that exists in Google). It is interesting to note that, as the paper explicitly mentioned, Chubby lock service is an engineering effort that claims no new algorithms and techniques, not research. As shown in figure 1 of the paper, Chubby is running distributed consensus protocol (Paxos?) on a small cell of five machines to elect a master in which the master is a "contact point" that receives requests from the client until the master is down or the lease expire. The paper then goes on to describe other features of Chubby; such as how it does backups, mirroring, handling fail-overs, etc.
No comments:
Post a Comment