And again, Lamport it says, he came up with this Paxos algorithm, which is essentially a quorum consensus already existed, but it's an elegant formulation of the quorum consensus system through this Paxos algorithm. As I said, Leslie Lamport always tries to come up with pithy analogies, byzantine generals is something that he came up with the show that they could be computers can fail and then start behaving and misbehaving. And similarly, Paxos is Is apparently a small Greek island and the kind of agreement that they had in terms of resolving disputes in terms of governance. He picked that idea from there, so that is where this Paxos name comes from. And the Paxos algorithm participants in the algorithm can play different roles, even though they play different roles they could be the same server that is playing a different role. So for instance if we have a client server system, again, have a node serving as a server for one particular client, but it can turn around and become a client when it makes a request to another service, right? So in the similar manner all these roles are interchangeable. So there are four different roles proposer coordinator acceptor and a learner in order to implement this quorum system. You can think of the proposer as the application command to perform a particular action that is durable. So for instance the application may say right to this particular location x, a value v, right? That maybe the command, so if it is in memory and it is a crash it's going to go away. So when you say it's durable, it means that has been committed to stable storage so that if there is a crash and you come back from a crash you can actually look at the log records and figure out what was the last thing that was done, so that is durability. So this is the action that somebody wants to perform there is a proposer. So he is going to coordinate if you contact the coordinator and for the purposes of the discussion let's assume that there is only one coordinator but it actually works even if there are many coordinators. But for the discussion, let's think of the being a single coordinator. And the reason why it works even if there are multiple coordinators because the durability that I mentioned, that there are logs that are being written. And so let's let's talk about what happens. Well, when the coordinator what it's going to do is in phase 1 it's going to send prepared accept to a bunch of water called acceptors. And accept is you can think of a servers to which I'm giving a write command for instance. The acceptors can say I'm ready to accept or they can say I'm not accepting, either of those can be response that you get back. Once you get enough number of ready to accept a response from the servers, then you send this accept command, which is the actual command that is sent to the to the system. And then the command is actually performed by this entity called Learners who'll execute the command. So in the first phase you send ready to accept and you get responses back. We have enough number of response, so if you think about the quorum consensus, I want to do it right and I want to get a majority say yes, I will participate. If they say yes, then you can go ahead and issue the right command. But if you don't get enough acceptance, then you have to go back to phase 1 and retry again to get the the the sufficient number of acts in order to say that I have the quorum in order to perform the command that I want. So that's the way in which you can sort of implement this quorum consensus protocol, which is saying that you want to have a majority of the server's participating in the read, majority of the service participating in the write, so that I can ensure that there is failed safety in the way this works. I want to give you a little bit of a footnote to this just so that you're all many of you graduate students and we are used to sending paper and getting acceptance sometimes but sometimes rejections as well. I should tell you something about what happened is this paper that Lamport wrote, do you know the date of this paper? This paper was written 1990, where is the first time he wrote that paper. And when you sent it, he got three reviews and all of them said, well, it's okay some minor ideas, but this access is terrible analogy, you should get rid of that completely from the paper. And Leslie Lamport is an interesting guy, he said I'm not going to do that. So he just shelf that paper completely, didn't touch it, he didn't bother revising it or anything like that, sat on a shelf until 1998. And he worked for a company called the Digital Equipment Corporation. We used to have a lab in the west coast called the Western Research Lab and the Systems Research Lab. A couple of researchers there, they were trying to build a fault-tolerant storage system. And they were thinking about what to do in terms of feature recovery. And they talked to Leslie and and they found access to be exactly what they wanted and they adopted that. And that sort of revived is interesting in this and he sent the paper and got accepted and got published in 1998. And so just to tell you that you get a paper rejection, don't be dejected you and Leslie Lamport [LAUGH] are the people is actually like that. Usually you got frustrated with because is use this sense of humor but it was appalled to see that the review is had no sense of humor. So he said the heck with that, I'm not going to publish this paper. [LAUGH] But the interesting thing is Paxos is what is the bread and butter of cloud computing today. You look as I said as first used in DEC SRC, the storage system was called Petal storage system. But with the advent of cloud computing wide use it is used pretty much by every major technology players that you can think of. We talked about Google Borg system resource manager, it has to manage resources redundantly and worry about failure because the manager himself could fail. And if that happens you have to revive the manager Azure Service Fabric uses it. Facebook Cassandra uses it, Amazon web service, Apache Zookeeper, all of these technologies are pretty much built on this Paxos algorithm. The one computer scientists that you should really revere is Leslie Lamport impact that is had in parallel and distributed system is really unparalleled.
