[SOUND] So, we've motivated both asset and base and we've talked about eventual consistency right at the beginning. Now, what we want to do is see how you would take eventual consistency and actually build a system to provide it in a cloud. So, we are going to do a centralized service. It's going to coordinate, it's coordination code you might say, it's going to coordinate everything inside the system. So that all of the system, whenever it wants to get to eventual consistency, can use this particular algorithm to achieve that. We're going to look at PackSource. Packsource acts in a very distributive manner. Lempel created it. It's based off a quite interesting discussion of a Greek island state operating in a parliamentary style. But we're going to address that, we're just look at the way the algorithm works. It, in general, it gets implemented as something called Zookeeper In many of the Apache projects. And ZooKeeper's a simplified version of Paxos and operates perhaps not quite to such scale as Paxos could. But it operates sufficiently well that to all intents and purposes, Zookeeper is the module you use. So we want to centralize service coordination. It's going to maintain configuration information. It'll allow you to do naming, get the consistency for naming right. It'll allow you to do distributed synchronization. It allows you to build group services, any sort of function inside a cloud where you need consistency. It avoids synchronization. It avoids races, so that if you have a race, you don't know who's going to win you may have to keep repeating the race. It's going to avoid all that and make sure that you'll have eventually a result you can use. The file system based API allows you to manipulate small data nodes and the state is a hierarchy of nodes. The system uses that sort of file system based API to keep track of everything so it remembers what the state of everything is. And we will now look at the actual algorithm employed. So If you were to describe this Paxos to people, what you would say is well let's suppose there's somebody wanting to make a change to the system, a proposer. The Proposer is going to request the Paxos system accepts some sort of command or change its state. And Paxos is going to act like a postal system. It's going to make sure that the state changes. It's going to think about the whole state of the system look at the letter, what letter needs to be done, or what needs to be done in the letter. It'll replicate data making sure that there's enough copies of things to guarantee as far as it can see that it will all occur. And then once all this is decided that whole process of how to do things is decided it then goes ahead and executes the proposer's command using its algorithm to make sure that there's lots of redundancy and you're going to achieve eventual consistency. And in the diagram you see the proposer sending mail to an acceptor. The job of the acceptor is to keep track that the proposer's asked this computation to be done. They're replicated. The acceptors are all going to sort of work out how to operate and how to conduct the command and then when they've all sort of sufficiently learned how to do that they will let their learners know what that command was. Now we have enough acceptors, and each one of them is responsible for trying to do this command, that the acceptors can actually form a quorum, and the learners will learn from the quorum of acceptors what was successful. So, here, you've got a system where you know that you're going to get an answer because of the quorum mechanism. You know that what you're going to achieve is a sort of an eventual consistency because eventually some quorum of those accepters is going to decide on some value that is how the mechanism is going to work. So, more detail, the client issues a request to the distributed system, waits for a response, and for instance might request a right on a file on some sort of distributed file server. The acceptors act as a fault-tolerant memory Reliable, durable memory. This is what's going on, and somebody's acceptors could die in the meantime, but it's still going to drive forward and actually produce a consistent result. Acceptors, there's enough of them that if one or two of them died, it doesn't matter. In fact, we have a lot of acceptors, they can even have 40 operation. What we're going to do is assume that the majority of the acceptors will come to a decision or a way of writing to the file, that is acceptable and that Quorum once it's formed it will let the learners know they've achieved their goal. Any message sent to an acceptor is duplicated to that quorum, and any message received from an acceptor is ignored unless you get enough of the acceptors sending the same copy of the message. Paxos is based on very sort of weak assumptions. The processors can operate at different arbitrary speeds. The processors can all fail. The processors with stable storage can rejoin the protocol after failures and it doesn't hurt what's going on. I remember the quorums, you can have people leave the quorum and join the quorum reporting to a leaner, it's okay. You can use crash, recovery fault tolerance techniques in the middle of this. And it doesn't affect any of the computations. There are some assumptions that the processes don't collude or lie or otherwise attempt to subvert the protocol. So, this isn't a sort of mechanism for presenting failures malicious code in there, sort of trying to cause trouble. This is that everybody's trying to do their best. And this protocol is trying to ensure that if they do their best, you're going to get an eventually consistent result. The network itself, well processors will have to send messages over a network to other processors. Messages can be sent asynchronisely, they can take arbitrarily long to deliver, and this is the key nuts and bolts of things that because they can take arbitrarily long, but you need to have some decisions made. You're going to have set of acceptors in the middle are going to make sure that. There is a reasonable confidence that the messages have been sent and received enough that you can move forward even if some of the messages have got lost. So messages are delivered without corruption, you can obviously put check sums and other things in the messages and that avoids some types of byzantine failures, and makes things a little bit more reliable. In general, how many processes do you need to actually do this? Well, there are consensus algorithms, that show that there are actually limitations on how well you can proceed in an asynchronized system. In general, this particular consensus algorithm can make progress if it has 2F+1 processors despite the simultaneous failure of any F processors. So you do need a lot of machines, but what it will do is to guarantee from one up to F that those failures can occur and it will still provide consensus. And this is why you're using the quorum. The quorum's going to guarantee that you vote amongst all of those duplicate processes in order to establish the results. If you're using reconfiguration, a protocols must be used and it makes survival of any number of total failures okay as long as you don't have more than F. Fail, at the same time. You can have F fail, or F minus one, fail. Then restart and that will be okay, but what you can't do is the total number. [MUSIC]