Could Paxos be made SIMPLE?
Paxos is one of the most difficult to comprehend algorithms in the Distributed Systems(DS) domain. However, it is a crucial part of the DS. To give you a brief, before I jump into the example, Paxos is a consensus algorithm that eventually concludes to a result. Having that said that, Paxos works perfectly under a few assumptions. Listing those assumptions is outside the scope of this article.
I try to remove the technical jargon from the ‘Paxos Made Simple’ (PMS) text by outlining a simple example, the Olympic Athletics Meet!
Let us dive right into it.
Disclaimer: I assume that you know the 5 rules mentioned in the PMS. If not, you might want to read the PMS first before reading forward. The article tries to make those rules understandable.
Let’s consider an Olympic Tournament having multiple seasons (co-relate it as multiple proposals).
There’s a slight change in how we decide winners for a season. If the majority of the judges cannot conclude a single winner, the season continues. So, it could run indefinitely. That’s true! Hence, we have some assumptions in the PMS.
We name the athletes: A1, A2… These are the PROPOSERS in PMS. I’m not taking the names as P1, P2, P3, P4 purposefully to keep the paper’s nomenclature separate.
And we have our Judges who announce the winners: J1, J2, J3… They are called the ACCEPTORS in PMS.
So, the objective:
Declare 1 winner for each season and the record of series of winners across seasons should be same with every judge and athlete.
Sounds good. Right?
P1: A judge should accept a winner as soon as ANY ATHLETE approaches them, claiming to be the WINNER.
Well, the judges are lazy in our scenario. They wait for the athletes to finish the race and then report to them who was first.
Pretty simple so far?
P2: If a MAJORITY of the judges declare a winner for a season, then every subsequent season would acknowledge all the previous season’s winners.
It allows us to remember the winners in the past and show gratitude towards their effort. Right?
But Wait! How do we make sure that the subsequent seasons acknowledge the previous season’s winners?
You might be thinking: The Judges have all the records. They will do it!
So, that brings us to the next rule.
P2a: If a MAJORITY of the judges declare a winner for a season, then in every subsequent season, the judges would acknowledge the winners of the previous season.
We let the judges handle the results as we trust them to be honest. Right?
Oh! But weren’t the judges lazy in the first place? If they were, then the records they get from the athletes might be altered?
P2b: If a MAJORITY of the judges declare a winner for a season, then in every subsequent season, the athletes would acknowledge the winners of the previous season.
Is it counter-intuitive if the athletes are dishonest? Who is stopping the athletes from approaching the judges with an altered history?
We forgot about the voting that takes place after all the judges have their new records. The majority will not accept the record if an athlete alters the history.
P2c: The athlete has two options to propose to a judge:
- If the athlete proposes that “There was no season winners before this season and here is the winner,” it should mean that no majority of judges have already declared the winner for a preceding season.
If it is season 1, an athlete should be able to propose a new winner. Right? Okay! That was easy.
- If the judges decided on the winners for the previous seasons, then the athlete’s proposal should be for a new season.
Obviously! An athlete cannot propose a winner for an old season as judges have already concluded on the result.
Okay! So, where are we now? Let’s integrate all the above rules to see if we are on the right track.
- Athletes have only two choices for proposing a new value. (P2c)
- Because 1 holds, the athlete‘s proposal always contains the previous year’s winners. An exception is Season 1, where is no previous season. (P2b)
- Because 2 holds, judges would always acknowledge previous season winners. Hence, the majority would agree on the history of the records. (P2a)
- Because 3 holds, we’re sure that previous year’s winners are acknowledged. (P2)
- Because 4 holds, we’re sure that the history of winners across judges and athletes would be the same. (P1)
And VOILA! We’re reached CONSENSUS!
I hope that was helpful!
I look forward to constructive feedback or any fallacies that might find in my example. I’d be more than happy to correct my understanding and the article.
