Paxos Algorithm

Here is my understanding of Paxos algorithm.

The key is to make every acceptor agree on one value, no matter who proposes the value.

Let’s have this scenario. We have 5 killers and each killer is able to kill someone. We also have 3 bosses. Each boss would like the killers to kill the person he proposes. But the overall objective is to make all the killers kill one person rather than kill the person the boss proposes. When the boss tries to ask the killers to kill someone, he has to pay some money.

  1. Prepare. Each boss tells every killer: i want you to kill someone. I don’t tell you which one he is, but I can tell each killer how much money i would like to pay. For example, boss B1 would like to pay N1 dollars to ask the killers to kill someone. During this phase, the boss doesn’t tell which one should be killed.
    1. The killer receives this request. If the killer has already agreed to kill someone, e.g. to kill Y. Then, no matter how much the boss would like to pay, the killer will tell the boss: it might be better to kill Y. Remember: the overall purpose is to agree on one person to be killed, no matter who proposes the person. Meanwhile, if the killer receives the proposal with N1 dollars, the killer will also promise: he will not answer any proposal with less than N1 dollars. If some boss pays less money, the killer prefers to follow the boss who gives more money.
  2. Accept. After receiving the ack message from the killers, the boss tries to tell the killer which person should be killed and would like the killers to agree on the proposal. For each boss, if all the messages he receives from the killers has no agreed person who should be killed, that means all the killers has not agreed on the result. Then, the boss will send the person he initially proposes, e.g. X. If one of the messages show some killer has agreed to kill Y, then the boss will change his mind by proposing Y rather than X, no matter how much money he would like to pay. Even if he pays the most, he has to use Y rather than the initial idea X. The reason is the overall goal to make all the killers kill one person no matter which boss proposes this person. In this phase, the boss will tell the killers which person should be killed, maybe it is his initial idea or the replaced one. The boss should also attach how much he will pay. The amount should be the same with that in the first Prepare phase. This is also a promise for the boss to the killers: if I will pay N1 dollars in the phase 1, i will also be willing to pay N1 dollars in the Accept phase.
    1. the killer will receive the message with 1) how much money the boss will pay and 2) which person should be killed. From the prepare phase, we know each killer will not agree on the proposal with less than some money. Thus, each kill keeps the minimal amount of money with which he will agree. In this phase, if the money is higher than or equal to this minimal amount, he will accept the proposal, or he will reject the proposal.

Now, let’s have some real examples.

Boss B1 would like to kill X and pay 101 dollars; Boss B2 to kill Y and 102 dollars. Killers: K1, K2, K3, K4, K5.

  1. The channel between B1 and all the killers are very fast while that between B2/B3 to killers are very slow. B1 will send the message to all killers: i would like to pay 101 dollars to ask you guys to kill someone. All the killers now will receives the message and send ack to B1. B1 will send the Accept message: Please agree to kill X and i will pay 101 dollars. All the killers will agree to kill X. After all these, the Prepare message from B2 has reached to the killers: B2 would like to pay 102 dollars. The killer has agreed to kill X, and then all the killers will tell B2: i have agreed to kill X. When B2 receives this message, he will not persist on killing Y, but he will change to kill X. Then B2 will send the Accept message: I will pay 102 dollars and please kill X. Now, X is the final value all the killers agree on.
  2. Let’s assume all the communication channels are similar. B1/B2/B3 will send the Prepare message to tell the killer how much money the boss will pay. If the killer first receives B1’s message (101 dollars), he will promise B1: he will not accept any proposal with less than 101 dollars. After a short period, the killer receives B2’s message (102 dollars), he will again promise B2: he will not accept any proposal with less than 102 dollars. Finally, the minimal amount of money for all the killers to accept some proposal is 102 since each killer can receive two messages no matter which one comes first. Then, B1 will send Accept message, but will get rejected because B1 is only willing to pay 101 dollars, which is less than the minimal 102 dollars. All the killers will accept the proposal from B2, because B2 is willing to pay 102 dollars, which is equal to the minimal amount. Now, the final value is Y, which is proposed by B2.

(in this explanation, all the killers can be replaced with the majority of the killers)

Advertisements

2 thoughts on “Paxos Algorithm”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s