Say you want to build a fault-tolerant distributed system (who doesn't). Easy enough, you just replicate a bunch of state machines, the so-called state machine approach. Here's a little more detail to get you started.
At the core is the consensus problem. In order to keep the replicas consistent we need an algorithm for choosing a single value when multiple values may be proposed.
The Paxos algorithms can help us. The specific Paxos algorithm discussed below is the "basic" one (there's a bunch of Paxos algorithms). The model is asynchronous and non-Byzantine. This means that a process may crash and recover, but doesn't do anything weird like sending random, deceitful messages to other processes.
There are three players in the algorithm: proposers, acceptors and learners. Proposers propose values, acceptors accept (or reject) proposals, and learners become aware of the accepted proposal values. These are logical distinctions, a single process could be all three.
A proposer first sends out a prepare message, basically asking the acceptors if they promise to accept the proposer's proposal.
The prepare message is pretty simple, it just has a unique proposal number n. Initially, when the acceptors receive the prepare message they will reply with a prepare OK and remember the proposal number they promised to accept.
In this example the acceptor promises to accept proposal for n = 100 and will ignore requests for n < 100. But the prepare OK message may also contain an already accepted proposal value (say when a different proposer tries to send a prepare message).
Here, a proposer with n = 105 sends a prepare message to an acceptor that has already accepted a value for n = 100. The proposer will need to use that value in subsequent requests to maintain consistency. In the "normal" case the value sent back is null and the proposer is unconstrained, so it can propose any value it wants (the value requested by the client).
Once the proposer receives a majority of N response (prepare OK messages) it can issue accept requests.
As long as the acceptor has not promised to accept requests for a higher n then it will accept the proposal and send an accepted acknowledgment.
When a majority of N accepted messages are received by the learner the learner becomes aware of the accepted proposal value. Notice that at key points in the algorithm data is saved to stable storage so that upon crash recovery things remain consistent.
The reason for requiring a majority N in the algorithm is intuitive. If a majority has accepted the proposal then losing any minority is still acceptable.
Returning to the proposal number. Each proposer needs to use proposal numbers that are unique.
In this example we have three proposers and three disjoint sets. Each proposer uses numbers from one of the sets. The proposal numbers in the sets are calculated by a simple mod operation.
Pretty simple, huh? Of course there are many challenges when you actually want to implement this algorithm, but let us leave that as an exercise to the reader.
And that's my interesting algorithm of the week (corrections appreciated).
Incidentally, I love this OmniGraffle Professional drawing program. For the first time I'm thinking, wow, this program blows anything I've used on Windows (i.e., Visio).
I studied that with this books.
Everything is gone now. Sigh.
http://books.google.pt/books?id=lLHC-0DsZRwC&dq=Introduction+to+Reliable+Distributed+Programming&printsec=frontcover&source=bn&hl=pt-PT&ei=NDgISs2zGoOU_Qb5tPiGBw&sa=X&oi=book_result&ct=result&resnum=4#PPR13,M1
Posted by: blah | May 11, 2009 at 07:38 AM