CS162 Lecture 23: Distributed Decision Making (Con't), Networking and TCP/IP

Welcome back everybody to CS 162. We are going to pick up where we left off on this rainy day in the Bay Area. If you recall from last time we were talking about communicating entities using a protocol and a protocol being a set of well-defined message messages with semantics and one of the things that you often do with a protocol as we mentioned is basically produce a replicated state machine on either side of a connection. And so for instance, I showed you this where we have state machines that might be here at Berkeley and in Beijing for instance and the idea of the protocol was to make sure that any arc that was taken on one side was also taken on the other and these state machines could be everything from copies of files to something much more interesting like what's the state of a running physical system replicated on both sides. And um as we mentioned a protocol basically has a syntax which is how the communications actually specified and structured as well as semantics. What do each of the communications mean? All right. And typically there's stable storage on either side so that if either side crashes, you can pick up where you left off and today we're going to talk about one use of that stable storage to allow us to do decision-making. Okay. So the other thing we started talking about was this idea of distributed applications and a distributed application is going to be something where the individual pieces are spread all over the network potentially and the question is how are we going to program something like that? And for instance, you're going to need to synchronize multiple threads on different machines but you don't have shared memory so test and set and all of the synchronization primitives we talked about in the first part of the course are not really available to you. And so what abstraction basically is to make use of messages which is pretty much what you've got and sending from one the other. And the nice thing about messages is they're already atomic. So you either receive the message or you don't. And one of the ways you make sure that you you don't receive a corrupted message of course is you put checksums or something on it. But this atomicity the either receiver don't can be turned into all sorts of interesting communication primitives which will lead among other things to the ability to build decision-making on top of the network which we'll talk about in a little bit. So the interface to this kind of message-based communication protocol is there's typically a mailbox with an address of some sort inbox which is a temporary holding area for messages and um it has in it both the the destination and the potential queue things are going to put in. So you could imagine this like a post office with a lot of post office boxes. The inbox itself is going to be not only which post office but which box to put it into. And then of course there's send and receive primitives. Send says send a message to a certain mailbox and receive basically says take something out of the mailbox and put it into the buffer and usually that's specified in a blocking sense so that threads sleep until they receive something. But of course all of the asynchronous primitives we've talked about earlier in the term are available typically as well. So um when should send return? So when a client does a send of a message there's a a real question about when it should return to the client. Should it return only when the receiver gets the message? So that might be a case where I've not only know that the message was received at the other end but there's an acknowledgement. That could take a long time. Maybe when the message is safely buffered in the destination. Okay, that way we're took the receiver out of the loop or right away if the message is already buffered on the source node and going out. So there's a lot of possibilities here as well and really questions are kind of have two parts to them. When can the sender be sure that the receiver actually received the message? That's an overriding question. But also when can the sender reuse the memory that contains the message? And what we'll see in the latter part of the lecture here is this question becomes comes up because if a message gets garbled on the way to the destination, we need to retransmit and typically the sender then needs to hold on to the message for long enough that the retransmission can happen. So mailbox really provides a one-way communication from T1 to T2 and really there's a buffer that's a combination of various storage areas in the network. Very similar to a producer consumer kind of thing where send is V and receive is P. However, you can't really tell in this case whether the sender or the receiver is local or not. So we can use send and receive for a producer consumer style communication not surprisingly. So the producer might do something like this where while one it prepares a message, sends it off and goes in a loop. The other consumer will be well receiving do something and then process the message. And so this the only way this is any different from some of the synchronization examples we gave earlier in the term is really that there's a network in between and so the physical separation here could be great. But other than that it it looks a lot pretty similar to some of the producer consumer code that we wrote earlier. There's no need in for the producer consumer to keep track of space in the mailbox because it's all handled by send and receive. In particular, if there's no space for some reason send will block on the way out and of course receive will block if there's nothing in the buffer and so all of that's taken care of for us under the covers. This is going to be one of the roles of the TCP window and we're automatically going to track the size of the buffer space at the receiver so that we don't send so much that the receiver overflows. So what about two-way communication? Obviously two-way communication is pretty standard for everybody. That's just two of these things in opposite directions. So this is a request response. You basically set up a mailbox on either side, one for the outgoing messages and the reception and the other for receiving the incoming messages. It's also called client server as we mentioned earlier. And so here's an example of a file service where the client basically says something like send read rutabaga into the server's mailbox and the server sends a response back. And the client basically goes and does a blocking receive on the client mailbox for the response. Okay, and the server sits here and in a infinite loop. I'm not showing that here for now but it waits to receive the request, decodes it figuring out what it is, reads the file into an answer buffer, sends it back. So this idea again of send and receive primitives now both both directions let us construct all sorts of interesting things. Okay? Now one thing that's buried in all of this which I'm not going to talk about today. I'll talk about it next time is the encoding of the send and receive commands. You know, how do we make sure that the the server understands the proper ordering and encoding of numbers from the client etc. That's going to be an interesting discussion. So let's talk about consensus making. So the consensus problem really is that all nodes in the system now where a node is a distributed a node is some item on the network and can be distributed from other nodes. So all nodes propose a value. Some nodes might crash and stop responding but eventually all of the remaining nodes decide on the same value from the set of proposed values. So this is like it's like everybody's going to vote on which value they want and we're going to come up with a result which is going to be the result of that decision-making. And this has got to work across a network and it's got to work in a way that is resilient when nodes crash. So distributed decision-making is really choosing simply between two and true and false. So the consensus problem I mentioned up here is more general. It's about a value but we can do a lot if we just choose between true and false or commit and abort etc. And that's typically called distributed decision-making. Um and what's going to be very important in all of this is yeah, we can make the decision but if we don't record it down, then nobody will know in the future what it is that we came up with. And so there is a durability aspect to this. So how do we make sure the decision cannot be forgotten? This is the D of typical acid semantics in a regular database. And in a global scale system the question about how to make something durable and long-lasting gets into what we talked about last time, things like RAID, erasure coding etc., massive replication or even blockchain which I'll mention briefly in a little bit. So let's start with an interesting decision-making problem. So this is typically called the generals paradox. You have two generals. They're on separate mountains and they can only communicate via messengers and the messengers are riding horses down one mountain and back up the other one. And the messengers unfortunately can be captured. And so the question is really how do we coordinate an attack so that if both armies attack at different times, they're going to all die. If they attack at the same time, they win. And so, the trick here is simply how do we make sure that everybody decides on the same time? Okay? Now, I did see a chat of SMS here, so we'll assume that SMS is not available because that's an out-of-band communication mechanism. So, let's assume that they have to use horse horse message system, the HMS. So, this was this General's Paradox was originally named after Custer who died at Little Bighorn cuz he arrived a couple of days too early. Um So, let's let's look at this problem for a moment. Um Can messages over an unreliable network really be used to guarantee that two entities do something simultaneously? That's our question. So, notice the simultaneity here is important. Remarkably, the answer is no. Okay? Because even if all the messages get through, you have to allow for the fact that they didn't, and so you you're not quite sure here. Okay? So, here's the two sides. And first guy says, "Oh, 11:00 a.m. okay?" And he says, "Yep, 11:00 works." And then, so 11:00 it is. Yeah, but what if you don't get this ack and back and forth? And it turns out there's no way to be sure that the last message gets through. Um and so, the the lack of reliability of the messaging basically is the paradox here. It makes it impossible to agree on an actual time such that everybody goes through. Okay? Now, of course, um in real life, you could use a radio or something simultaneous or out-of-band communication. Uh in this particular domain where we don't have any out-of-band communication, it turns out you just can't do this for simultaneity. Okay? Um So, clearly we need something other than simultaneous as our requirement. Okay? And what would that be? Um Well, two-phase commit uh is basically an alternative. So, we can't solve the General's Paradox, i.e., the simultaneous action. Let's solve a related problem. So, the related problem is a distributed transaction where two or more machines agree to do something or not do it atomically. So, there're no constraints on time, just that it will eventually happen. Okay? So, the constraints on time have been removed because we're just basically uh saying that eventually something will happen and everybody will agree. This atomicity constraint though is an interesting one that I wanted to say something about, which it says, "Suppose we have 20 elements in the system, all 20 of them will decide to do it or all 20 of them will decide not to do it, but you'll never get some of them doing it and some of them not doing it." And that's our distributed two-phase commit. So, two-phase commit was originally developed by uh uh Turing Award Turing Award winner Jim Gray, you see here on his boat. Uh he was the first Berkeley CS PhD in 1969. And there's a a lot of important database breakthroughs that are also from Jim Gray. Um he is a an amazing alum of Berkeley as well. Uh and unfortunately, uh a number of years ago, he disappeared in his sailboat in the bay and nobody ever found him. So, but um there's a picture of him in happier days. And uh he basically developed the protocol called two-phase commit, and it's sort of the basis for a whole bunch of other protocols. So, I wanted to make sure we all know about this. Um So, one of the most important things we need to start with is we have to make sure that once an entity in the system or a node makes a decision, they won't go back on that decision. And so, we need to have a persistent stable log on each machine to keep track of whether a commit has happened or not. And if a machine crashes, when it wakes up, the first thing it does is it checks its log to recover the state of the world at the time of the crash. Okay? So, the prepare phase of two-phase commit, there's going to be two phases, no surprise there, is that the global coordinator requests that all participants promise to commit or roll back the transition transaction. And participants record their promise in the log, and then they acknowledge. And if anybody votes to abort, the coordinator is going to say abort in its log and tell everybody to abort. And the only way that it will actually commit uh is if all of the participants basically say, "Okay." So, the commit phase basically is after all the participants respond that they're prepared, the coordinator will write commit to its log, and then it'll ask all the nodes to commit and to ack them. And after it receives all the ack, then it can write that it got commit to its log. So, notice that there's going to be the use of the log at several parts of this to make sure that once we've made a decision, we don't do something different later. Okay? And the log is really used to guarantee that all machines either commit or they don't. So, two-phase commit algorithm has one coordinator, n workers, or replicas. A high-level algorithm description could be that the coordinator asks the workers if they can commit. If they all reply vote commit, then the coordinator broadcasts global commit. Otherwise, the coordinator broadcasts global abort. And notice that um there's all sorts of things that could go wrong here such that a uh a worker that we asked whether they want to commit, maybe they just go offline and never come back. If we time if the coordinator times out and doesn't hear from somebody, then it's just going to go ahead and abort. So, basically, what we can do is we can make sure that it's truly atomic. Either everybody commits or everybody aborts, and there's no halfway, and we can deal with all of these different failure conditions, which is kind of what we want to do. Okay? And the workers are going to obey the global messages, whatever they happen to be. And we're using, as I said, a persistent stable log on each machine to keep track of what you're doing. If the machine crashes, then when it wakes up, it checks its log to recover the state of the world at the time of the crash and then keeps going. Okay? And so, the setup is the coordinator initiates the protocol, asks every machine to vote. Two possible votes, commit or abort. And we commit the transaction only if there's unanimous approval. So, preparing again, that prepare phase, the worker either agrees to commit or abort. So, if it agrees to commit, the machine basically is guaranteed it's going to accept the transaction. It's recorded in the log, so the machine will remember this decision if it fails and restarts. So, once it's written in the log that it's decided to commit, then it could crash and come back up and crash and come back up, and as long as it keeps looking in the log, it can remember what decision it made, and it won't make a different decision. And similarly, if a machine has said that it will abort, it records that in the log, so that if it crashes and comes back up, it'll never make a different decision. Now, if if a worker was offline or crashed, it'll come up and it'll notice that it never made any decision. At that point, it can ask the uh coordinator what to do next, or it can just assume abort and send an abort up. Those are two options. But notice that if it actually makes a particular decision, it's going to record it in the log. So, to finish everything up, the commit transaction, when the coordinator learns that all machines have agreed to commit, it records the decision in the log, applies the transaction, informs the voters the voters to go forward. If it aborts, it's because at least one machine voted to abort or didn't respond. It records the decision to abort in its local log, and doesn't apply the transaction, and it informs all the voters that we're going to abort. Okay? And notice that um because no machine can take back its decision, exactly one of these two things happen. Either uh we commit or we abort on all machines. Okay? Questions. Now, this is a fairly simple primitive, but it's very powerful cuz it says I can take a bunch of nodes, and I can make sure they all do the same thing. And um and from that, you can build all sorts of interesting things. Distributed file systems. You can build other types of distributed decision-making, etc. Uh how is the coordinator decided? That's a really good question. We're going to assume right now that the coordinator has has distinguished somehow because uh they've been um compiled with code that says they're the coordinator. In a real system, things get much more interesting where there's a voting process to choose the coordinator. Uh and real systems basically have a choice of coordinator, and then the coordinator goes ahead and coordinates. But that's a good question. So, uh I hate to mention it, but uh oops, here's a question. Um if one machine keeps crashing, the whole system will never commit. Yes, that is absolutely correct, and yes, that's very bad. You have correctly analyzed the uh one of the chief weaknesses of this algorithm. So, um I will say that again later, but you've already preempted me on that. That's right. So, this uh particular algorithm is subject to one machine that's um faulty basically keeping everything from committing. That's correct. So, um there is a midterm last one coming up. Um 5:00 to 7:00 as as uh before. Um materials all the way up to lecture 25, which is uh Monday 11:30. Um that's the last lecture that is going to be on the midterm is the one after Thanksgiving. Um cameras and Zoom screen sharing again, just like with midterm two. And um there will be a review session. We haven't announced it yet. I'm not entirely sure when that'll be, but it'll probably be the week after Thanksgiving on Tuesday or something like that. Um lecture 26 is going to be a fun lecture. So, if there's some topics you'd want to know something about, let me know. Um I will pick a set of topics if I don't hear enough suggestions. So, um you're welcome to email me lecture suggestions. All right, and I don't have a lot. We're actually in the middle of due dates and everything and um we're uh don't have anything else to say. I did want to report repeat one thing I said last time briefly is pre- please be careful of the collaboration policy. If you remember, as I mentioned, explaining a concept to somebody in another group is okay. If you explain a concept, uh discussing algorithms or testing strategies is okay. Uh discussing debugging approaches, all of these things at a high level is okay. Searching online for generic algorithms, like hash tables, okay. Where this strays into problems is if you're sitting working with somebody and you start discussing back and forth explicit details about the homework, that is going to be uh not okay. Okay? So, for instance, sharing code or test cases with another group, um copying or reading another codes uh groups code or test cases, copying or reading online code or test cases from prior years, um helping someone in another group to debug their code or helping somebody else do it to do their homework, these are all things that are not okay. Okay? And we um compare project submissions against prior year submissions, against um internet sources, and against your code. And so, uh you know, just just say no to over collaboration. Um don't put a friend in a bad position by asking for help uh because both of you end up in trouble. So, all right. I just wanted to repeat that. We've got a few cases on the fringe of violating collaboration policy. So, okay. Now, let's before we leave the um before we leave two-phase commit, I wanted to just give you a little bit more graphic detail here just so you can see. So, let's look at um the coordinator algorithm. The coordinator basically says, "Vote request all workers." The workers wake up the after waiting for vote request, and then they make a decision. If they're ready, they send vote commit. If they're not, they vote abort. And they make sure that they record their decisions in on the disk, um in the log. And then the coordinator basically, if it receives vote commit from everyone, it sends a global commit. Otherwise, it sends a global abort. And basically, the workers in that second phase, if they get a global commit, then they commit. And if they get a global abort, then they abort. Now, notice, I'm going to say more about this, but the notion of commit and abort is basically a yes or no decision. And uh what you're saying yes or no to could be arbitrarily interesting and complex. Okay? So, it could be here's a really long, complicated transaction making many changes to a file system that we have previously transmitted to the workers. And now all the workers are doing is making a thumbs up or thumbs down decision on well whether to apply that to the file system or not. So, all we're really doing with a two-phase commit is we're making this this decision of yes or no globally. Okay? So, here's an example of a failure-free. So, the coordinator says, "Vote request." Each of the workers say, "Commit." Let's say uh the coordinator says, "Global commit." And we're good to go. And this doesn't take any excess time. Um so, the coordinator, you could think of as having a state machine. It starts in the init state. Um receives a start from some other part of the software, sends the votes. It waits in the wait state. Um and then if it receives all vote commit, uh from everybody, then it sends a commit. Otherwise, it sends an abort. Uh very simple state machine. Okay? Um the workers have a somewhat similar state machine, but they sit in the init uh phase waiting for a vote request. And then at that point, if they're going to commit, they go to the ready state to start the commit process, which really means that they are going to tell the coordinator they're ready to commit. But now they got to wait to find out what the decision was. On the other hand, if they've decided to abort, then they tell the coordinator, and then they just go to the abort state, and they don't really have to wait for any more information because um they know what's going to happen. It's going to be an abort. So, uh just to give you a couple of failure modes here that are kind of interesting, right? So, um if a worker fails, what happens? Well, the coordinator is sitting in the wait state waiting for the worker, and they're going to have to do something. Well, that point, um you know, you're only how what happens in wait is you're going to get a timeout, and you're just going to treat that like an abort. And so, that's easy. Okay? Um so, here's an example where the coordinator says, "Vote request." Um some of the workers say, "Commit." But this last one ti- it doesn't, either because the message got lost or because the worker has crashed. At which point there's a timeout, and uh the coordinator says, "Well, I didn't hear from everybody. I'm just going to assume there's an abort." And it sends an abort out. Um Similarly, the workers can deal with coordination failure in a couple of ways. So, the worker waits for vote request and init. Uh the worker could time out and just plain abort, and the coordinator will handle that as an abort. Um it could uh basically send off its response and never find out what the global result is. Okay? And um at that point, however, the worker has to wait. Cuz the worker can't just abort because if it sent a commit, it's got to wait to see whether the coordinator is going to abort or not. And so, really, it can't just take a lack of response from the coordinator as an abort because it could be the coordinator crashed. And so, you have to wait. And potentially, the coordinator has may have to crash, reboot, come back up, and eventually tell the uh worker what to do because we have to make sure that all the workers do the same thing. They're not allowed to make a decision on their own. Okay? All right. Now, um the uh here's an example of the coordinator failing, like it didn't send vote request. So, they all time out, and they abort. Um the uh here's another example of a coordinator failure where the vote uh comes in. They're They vote to commit, but the coordinator doesn't receive them. It could restarts. Um if it hasn't If it knows from its log that it's never sent a global request, then it could just or a global uh abort or commit, then it can just send abort to everybody. Um so, how does the worker know the coordinator received their commit? Well, they don't. Um so, there is there is that question. If the coordinator never received their commit, then potentially, the coordinator will treat that as a um as an abort on the part of the um on the part of that particular worker. Now, you could put a retry protocol in here to do your best to make sure that the worker hears from you. Um and that's that's possibility, but you would need to make sure that you didn't violate the atomicity property of this. So, the interesting thing about how does the uh coordinator make sure that each worker got the global commit that it sends out? So, um what's good about that is if the um if the coordinator uh sends everything out, and one of the workers doesn't receive it, the worker uh could time out and ask the coordinator uh what's up, at which point the coordinator could tell it. So, there is that ability there. Um this this example leads to an abort simply because um we're assuming that this crash happened uh and the coordinator didn't properly receive everything. And so, it's treating these all as a timeout, and it's just aborting. Now, what you can do here, and everybody's thinking about this, this is great, is you can figure out how to optimize this in many ways. The The key semantics that you have to make sure that are true are the all or nothing. Basically, either everybody commits or everybody aborts, but never partially. And as long as you maintain those proper- that property, then you can do various optimizations to try to make up for message loss and a few other things like that. Um but and and there are many optimizations, including one where if you haven't heard from the coordinator, you talk to uh other um workers, and they can tell you what the coordinator said because they know the coordinator said uh commit, then commit is what the worker should have gotten from the coordinator as well. So, there is a a way to do a gossip protocol among workers that also maintains the semantics, but the key thing is you got to maintain the semantics. So, and to that end, durability is very important. So, all the nodes have stable storage to to store the current state. Stable storage is non-volatile storage backed by the disk that guarantees the atomicity of the rights. Um, and, uh, and make sure that everybody either, uh, sticks to their decisions, or once they've heard of a decision, they keep remembering the decision so they can apply it. Okay? And that stable storage is going to be something like SSD or NVRAM or disk or whatever. Um, and then on recovery, like I said, uh, there are many you can look at the state machines and you can figure out all the different places to abort after you've recovered based on the information in your log, uh, and what state you think you're in. Okay? So, what does this two-phase commit tell us about? Well, if two-phase commit is, uh, is a famous, very simple first cut at distributed decision making, um, and why is it desirable? Well, it's desirable for fault tolerance. You like the fact that a group of machines can basically come to a decision even if one or more of them failed during the process. Uh, the simple failure mode that it relies on is something that's often called fail stop, which is that when a node fails, it fails by just stopping and not communicating anymore. Unfortunately, if you get into more complex types of failures where a node that's failing, uh, starts, I don't know, sending out corrupted messages or or, um, or worse, a malicious node starts sending up intentionally, uh, bad messages, that's no longer fail stop, and, uh, two-phase commit will not work properly. Okay? The other thing is after the decision's been made, it's recorded in a bunch of places, so there's a a nice replication here that if if a node then subsequently dies, you can always ask other nodes what the decision was that was, uh, that they all came to. So, why is two-phase commit not subject to the generals' paradox? Remember, we kind of said the generals weren't able to make a decision about time. And the answer is two-phase commit's about the nodes eventually coming to the same decision, not necessarily at the same time. So, if you have a node that crashes, comes back up, crashes, comes back up, what will eventually happen when it runs is it will come to that either commit or or abort decision, and it will apply that properly, but it may take a while. Okay? And so, um, we don't care how long it takes. What we care about is that it eventually is atomic. Now, the, uh, again, the question came up here, doesn't this assume the nodes will eventually come back up? Yes. So, this again, this is the simplest decision making, and it has that unfortunate property that a permanently crashed node can bring the decision making to a grinding halt. Okay? So, just, uh, keep that in mind. We'll talk about other options in a moment. So, an undesirable face, uh, feature of two-phase commit is blocking, which was, of course, just came up in the chat. So, one machine can be stalled until another site recovers, so you can imagine site B writes prepared to commit, sends a yes vote to the a coordinator, and crashes, site A crashes, B wakes up, checks its log, realizes voted yes, sends a message to site A asking what happened. At that point, B can't decide to abort because the update may have committed, so B is basically blocked until A comes back up. And so, you have that scenario, you can come up with very one various ones of them where, um, nodes are stuck on other nodes. And so, that's an unfortunate property of two-phase commit. So, a block site holds resources like locks on updated items, pinned pages, etc. until learns the fate of the update. Okay? So, that's a that's a fundamental problem with two-phase commit. What are some alternatives? Well, there's three-phase commit. So, it turns out, I'm not going to talk about that in detail today, but there's one more phase, and it actually allows nodes to fail or block indefinitely, and the rest of them can still make progress. So, that's that's an important, uh, property. You can imagine if you have a system with a lot of faulty nodes, or if you have a system distributed across a geographic area where it's quite possible that the networks are going to go down, or that, um, some of the nodes are going to fail, then you're going to want you're not going to want to use two-phase commit. You're going to want to use at least three-phase commit. Another alternative, uh, which is used by Google and a bunch of others that's, uh, doesn't have the two-phase, uh, commit blocking problem, either, is called Paxos. And Paxos was developed by Leslie Lamport. Um, showed you his picture earlier. Uh, there's no fixed leader in this particular situation, so they choose it chooses a new leader on the fly. So, it can deal with a failed leader that even one that fails in the middle, it can pick a new leader. Um, the interesting thing about Paxos is, uh, the way it's defined, um, I think I I think I put up one of the original Paxos papers is kind of fun. It's defined in as a legislative assembly in ancient Greece. Um, and, uh, it's it's a little bit obscure in the way it was originally defined, and it can get pretty complicated in its normal use, uh, but Google has actively using versions of Paxos called MultiPaxos, uh, and they have been for 10 years now. Um, there is an alternative called Raft, which was developed at Stanford, uh, by John Ousterhout Ousterhout, and, um, he basically thought Paxos was really complicated, and he wanted a version of a decision making algorithm that he could describe to people easily, and, uh, that came up with was Raft. And so, that's an alternative which you could look up. Um, but none of this, uh, helps us with the following, which is, what if a node is malicious? So, we can deal with a node failing, but if a node is actively attempting to compro- compromise the decision making process, we need to do something, and, um, basically, we have a couple of options here, Byzantine agreement and blockchains. I said I'm going to talk about them next time. I'm actually going to talk about them in just a moment. But, um, so, there are many alternatives to distributed decision making, which you can take as a a key indicator that, uh, distributed decision making's important. Okay? So, let's actually talk about the Byzantine generals' problem. So, there are n players. Okay? There's one general, and there's n minus one lieutenants. And, um, the idea is that one of these lieutenants may be malicious. Okay? And what is a malicious lieutenant do? Well, a malicious lieutenant is, um, going to basically do either illogical operations, or much worse, they're going to do operations that are intentionally designed to, uh, violate the protocol and prevent something from happening properly. Okay? And and the, um, commanding general is going to send, uh, attack or retreat commands. And as you can imagine, again, this is like yes or no, or commit or abort, um, all of these sort of two-part, uh, commands. And, uh, basically, the constraints that apply are going to be as follows. All the loyal, non-malicious lieutenants will all do the same thing. So, if you notice, we've got these two lieutenants are loyal, and they've all decided to attack. At the they're both attacking. Now, this malicious one may do who knows what. Um, but the all the loyal lieutenants will do the same thing, and if the commanding general's loyal as well, which means he's not sending conflicting commands to people, then he will also do what all the the loyal lieutenants are doing. Okay? And so, that's the Byzantine generals' problem. And so, the trick here is that we want the combination of, uh, a majority of the players here, in fact, um, we're going to tell you in a moment it's going to be, uh, 2f plus one of them are all going to do the same thing, and, uh, that will be just like our, uh, atomicity property from the two-phase commit protocol where they either all, um, decide to, um, in this case, attack or retreat, or they all decide to commit or abort, and only the malicious ones may do something, uh, you know, totally arbitrary, but they're also going to be participating in the protocol and will not be able to fool the other, uh, participants into doing something that they're not supposed to. Okay? So, that's what's tricky. The question here is, in the presence of a malicious player, is there a way to come to a coordinated decision amongst all the non-malicious players? And, uh, the reason this is complicated is because we don't know whether the general has been compromised or not, either. And so, somehow, even if the general is going to send conflicting orders, we still have to have the, um, we have to have the preponderance of the, uh, non-malicious lieutenants still have to all do the same thing. It may not be what the general asked because the general's giving conflicting orders, but they'll still all do the same thing. All right? Questions? Now, once again, Leslie Lamport came up with the Byzantine agreement problem, uh, in a in a very fun paper, which I believe I also have up on the readings. Um but you might ask yourself how this can help uh us design systems. So, let's talk a little bit about some impossibility results. Okay, so I'm going to get rid of the clip art here and go to something a little simpler. Um so, one of the key ideas is you can't solve the Byzantine generals problem if there's only three players. Okay, and I'll show you why that is. So, here's an example of one general, two lieutenants. If uh if the general says is not insane and says attack to both lieutenants, and then one of the lieutenants is um malicious, that lieutenant may say, "Well, the general told me to retreat." Okay? And so, this lieutenant, this poor guy on the left, has no idea whether to attack or retreat. And then and uh if you look at the situation in which the general is malicious, sends attack and retreat to uh the different lieutenants, so there's conflicting information, and this lieutenant says, "Well, the general told me to retreat." If you notice, the poor lieutenant on the left can't distinguish between those two situations, and really has no way to fulfill the requirements. Okay? And so, again, these requirements are these two consistency things I showed you where all the loyal lieutenants obey the same order, and if the commanding general is loyal, then all the loyal lieutenants do what he is what he requests. And so, in this scenario, um the general is asking to attack, he's loyal, this lieutenant ought to do the attack, but he doesn't have enough information. This case, the general's malicious, but the two lieutenants should be doing the same thing. There's no good way for this guy on the left to figure it out either. And so, this impossibility result turns out is then generalized, and it turns out that if you have F malicious entities, then you have to have a total number of players and that's greater than 3F in order to make this problem work. Okay, and that's an impossibility uh result. Now, good question, are the malicious nodes colluding? Certainly, if they like to. They're allowed to do anything they want. In fact, they can even they can even talk to aliens and uh and uh listen to Elvis if they want uh before they make their decisions. So, there are absolutely no constraints on the malicious players here. Okay? So, um and you know, the whole notion of malicious, as you can imagine, brings colluding in as an obvious possibility. So, surprisingly, at least it was the first time I heard about this, um is various algorithms actually exist to solve this problem. Okay, now um so, the question is if can't you tell who's giving you the message? So, the answer is that um even if you can tell who's giving you the message, you don't know whether they're malicious or not because a malicious player, by definition, can act in a way that you can't tell that they're acting maliciously. So, they could tell lots of different things to different people, and you don't know whether they've told the same thing to everybody or different things to everybody. That's why this problem is really interesting because we assume a maximally evilly malicious player who, the moment you try to see whether they're malicious, they behave nicely. And when you and when they're in the middle of the protocol, they behave evilly, and you can't tell the difference. All right? Now, um so, for instance, various algorithms exist to solve this problem. The original algorithm the paper was exponential in in the number of players N, so that was clearly not practical. It was an interesting proof of concept that it existed, though. Newer algorithms um have a message complexity of order N squared. That's supposed to be N squared. Sorry about that. Um there's one from MIT um back in the early 2000s, uh late '99. And um And even better yet, there are newer versions using blockchain algorithms that are much more linear in uh message complexity. So, um the use of the Byzantine fault tolerance algorithm uh basically allows multiple machines to make a coordinated decision even if some subset of them, less than N over three, are malicious. And so, you could think of this Byzantine agreement algorithm. I'm not going to go into the great detail on it. I'll be happy to uh I think I even put it up on the uh resources page. Let me just quickly look here. Um If I didn't, I'll be happy to to reference it. Yeah, I have the Byzantine generals problem here. Um but anyway, if you think of this algorithm running amongst a lot of different nodes, um what happens is a request comes in, and a distributed decision goes out even if there's some malicious nodes in there, um which are these little red circles. Okay? And so, that's a pretty powerful idea. Uh and the one downside that you might imagine, can anybody think of a downside to this? Assume that we uh have everything working properly. What's a downside to this particular algorithm? Okay, slow is a good answer. Um it turns out that it's less slow than you might think, but certainly speed is a question. What else? N squared messaging, great. Now, it turns out, like I said, there are newer versions of Byzantine generals uh of excuse me, of Byzantine uh agreement that are done with blockchains that are more linear in number of messages. So, that's good as well. Better. Much better. There you go. Good, I like that. Hard to get a lot of good nodes. So, imagine that the reason these nodes are red down at the bottom is somebody hacked into them. Okay? Now, if all of these nodes are running the same operating system, you might imagine that a really clever hacker might figure out where all these nodes are and start uh compromising them one after another. And the moment you violate the uh that you can only have F um faulty nodes, then suddenly this uh algorithm doesn't work anymore. And so, the only way to really make this work, and this is kind of the what's considered the fundamental problem of this, is you have to keep reinstalling these nodes and repairing them over and over again because you can't tell whether they've been breached, but you need to keep uh reinstalling them as if they had, and you try to do that faster than people can be breaching the nodes cuz you got to stay ahead of that F number. And so, that's potentially an issue. Okay. So, let's take a different question here, which is is a blockchain a distributed decision-making algorithm or not? Um and just to say a little bit about what a blockchain is. So, blockchains really uh came up in prevalence in 2009 when um when Bitcoin first showed up. And the idea of a blockchain is pretty simple. If you've taken um any cryptographic classes, like 161 or whatever, security classes, um but I'll just tell you briefly, the idea is that you have a series of records, and they have a hash in them, a cryptographic hash over the previous record, and it's stored in the current record, and so that's where the chain comes from. And the reason that's useful is if I know this uh spot, then nobody can go back and fake out the previous spots because uh they're all hashed together in a way that's uh you can't uh insert arbitrary records in here. And so, these chains, starting from a given head point, pointing backwards, we have the older ones in the back, are basically things that can't be uh altered, even though this data is stored in insecure locations all over the network. Now, um so, the hash pointers, that's these blue things, can't be forged, that's an assumption. The chain has no branches except uh right at the very head, there might be some brief branches. And the blocks are considered authentic when they have authentic authenticity info in it. Now, for those of you that know something about signatures, you might say, "Well, yeah, say there's a signature here, then that signature uh proves that the yellow block here is authentic, and therefore everything below it's authentic." Um in Bitcoin, what happens is in fact, the authenticity information's a little different. It's actually there's some consensus algorithm that's used to choose which one of these is a head. And in things like Bitcoin and at least the first versions of Ethereum, the head is basically chosen by solving a very hard to solve problem. This is called proof of work. So, you have to burn a lot of energy, which they do in um huge offshore uh um server farms these days. But um you have to find a proof of work to solve a problem, and then that will make something authentic. And then basically, the longest chain wins. Okay? And so, um really what's happening is as you're submitting new things to happen to be done, they get added to various chains, and then all of the different miners out there, I'll show you a picture in the world I'll show you a picture in a second. All of the miners are all busy trying to solve the problem first, the first one that solves it, that becomes an authentic chain, and uh and the chains have a tendency to re-merge afterwards. Okay? So, um I don't want to worry you with the big details of this. I'll be happy to point you to some uh blockchain papers if you're curious. But here's a here's a way to think about whether this is a distributed decision-making algorithm or not. So, spread throughout the world, we have these miners with their server farms, and what they're busy doing is they get um they're busy talking to each other about the parts of the blockchain that aren't in question and only the heads where there's a little bit of divergence or branching are the things that are in question. And what happens is various entities submit proposals of new transactions to the miners and the miners try to add them to the head of one of the branches and then they try to solve a problem that takes a lot of power and if they solve it first then the proposal becomes a permanent part of that branch and the other branches have a tendency because they're shorter to die off. Okay, and so what we're really talking about here for decision-making is this proposal could be something like I'd like to commit such and so data to a certain part of the file system. What will happen is the miner will packet up in a transaction, put it inside of one of these transactions in the blockchain, try to solve the problem and eventually it may become part of the permanent blockchain. And furthermore, so the so the decision means that it's in the blockchain and so if I say commit do this right on the file system, it gets committed to the blockchain then it becomes replicated around the world. In fact, we can have observers all over the place looking at it. And now that decision has been made durable in a way that's extremely hard to destroy. And so really you could use Bitcoin to do decision-making of the sort of the sense that we're talking about here. Okay, now the question here is proof of work necessary cuz an individual node has no way to communicate with every other node. So the reason proof of work is required is that we want to try to make sure that uh only people who have invested a lot of time and energy are allowed to add transactions. So it's really a um it's twofold. It's it's an attempt to prevent people from just extending the chain arbitrarily any way they want cuz we want to be restricted to real proposals and they have to invest energy in it. And and then the assumption is that assuming that the number of players is large enough then no one player has the an overwhelming advantage to add things to the blockchain and so that's how we get rid of the Byzantine nature of the fact that these people are all untrusted but they're putting their energy in here. Um and so that's the proof of work is basically making them put work into it. They have to put real dollars into adding things and if they successfully generate proof of work then they also get a little Bitcoin money back as well. And so I would say the proof of work is is the way to try to make everybody behave correctly and avoid Byzantine decisions. So. You can decide whether you buy it or not but that's that's a much more deeply philosophical question. Okay. So I would say yes to is blockchain a type of distributed decision-making. By the way, out of the realm of file systems if suppose this is Bitcoin people proposals that get put into the chain are things like I'm going to transfer a dollar 50 worth of Bitcoin which is like point zero zero zero five or something to buy a cup of coffee and so the proposals are actually transactions of money exchange as well. Okay. So let's let's switch gears a little bit here um unless there were any other questions about distributed decision-making. Take a pause and breath. Okay. So let's talk a little about a bit about networking protocols now. So we know we want to make decisions but we need messages to make them happen. And so networking protocols are many levels and you can take a networking class to find out more but um the uh what what are some good examples of distributed decision-making? Well, I think I just said adding um adding items to a to a um file system is a good example of distributed decision-making. Transaction monetary transactions are good distributed decision-making. Um pretty much anything where you want to fault tolerantly decide on something that's a decision and if you want to do it in a way that's really hard to to screw up, you might want to do that geographically separate with a distributed decision-making algorithm. And so there's a whole bunch of distributed decision-making going on all the time in the cloud and and uh spread across parts of the multiple continents. So it's a it's a pretty common operation anytime you want it can turn something into an abort or commit decision and you want to make sure you do that in a way that's hard to interrupt, that's a distributed decision-making uh system situation. So um so there are many different network protocols. You can take uh networking class to figure out more about this but um you know uh typical levels are the very physical level which are mechanical electrical signals. You know, how are zero and one represented by voltage levels. The link level is typically what happens for packet formats and error control over a single hop in the network. Good example of that would be like in Wi-Fi or whatever there's the you know, the wireless protocols and how how does an actual packet get from your laptop to the Wi-Fi access point. The network level gets us questions about how do I route packets across a whole bunch of link level links to get from here to Beijing. That would be the network level and then finally the transport level is something like reliable message delivery. How do I make sure that when I send something from here to Beijing that it's done so in a reliable way that doesn't have ordering problems, okay? And so many protocols on today's internet and so here the physical link layer is down at the bottom here and you can think of things like Ethernet and Wi-Fi and LTE and 5G and all that sort of stuff. The network layer typically has IP in it. Okay, that's our that's our big narrow waist that we talked about last time that's kind of the universal communication protocol on a global scale these days. The transport layer like UDP TCP, these are the parts of the protocol that both do reliable transmission in some instances as well as transmitting from one process to another process. And then above that's the application layer and those are all the things that use these underlying protocols. Okay? So the simplest type of network is a broadcast network like a shared communication media. You can imagine a bus for instance where processor bunch IO devices and memory are all in the same physical bus. That's a shared medium. The biggest thing about such a medium is you can broadcast so the processor could say something that's picked up by a bunch of IO devices. Wi-Fi is actually a type of broadcast media as well. Um it is interesting that the original Ethernet was used as a broadcast network. So the the lab that I did my research in as a a graduate student, we actually had these troughs in the ceiling where a whole bunch of these cables went all around the whole floor and then they had these taps that would come down to computers that they were attached to and literally we were all connected to the same transmission line between the the router and and all the other computers. And so you know, when you went to communicate, you would start talking on that line and everybody else could in theory listen to it. And that would lead to the need for collision protocols to to deal with that as well. Um and lots of examples of these broadcast media. Okay, so I'm not going to go in great detail about this but one example let's talk through broadcast networks for a second. So for instance, there's a media access address typically 48 bits these days for the hardware interface itself and in principle every device in the world has a unique address. Um and when a sender goes to broadcast a packet, how does it know know it's who it's for? Well, the packet goes to everyone but typically it's addressed to a particular MAC address. Okay, and so the message has a header that includes uh um typically an IP address but it also includes a MAC address on it and a body and that gets broadcast to everybody and the nodes all selectively ignore the packets that aren't for them and only the packet only the node that's supposed to receive it actually receives it. Okay? Um and this is pretty standard certainly for Wi-Fi. You can imagine it's standard for multiple things on the same Ethernet wire and number of other types of broadcast communication. Um now there's a is there a shortage of MAC addresses? Well, 48 bits is a lot more bits than 32. Um you know, the in theory at least, the MAC addresses are supposed to be unique across the whole world. Um and I think that mostly is adhered to, but um a lot of systems allow you to overwrite the MAC addresses anyway. And so, um I don't know. That's a good question. I've never I've never asked whether the MAC addresses were running out, but there's a lot more MAC address space than there is IP space. Uh cuz 48 bits is a lot more than 32. Um You know, uh the check about whether to receive or not is typically done in hardware. So, um when you go to send something on a broadcast media and it's received, the hardware card basically does the selection and only forwards packets that are really destined up into the operating system. So, the operating system in typical use doesn't have to look at every packet that goes by. Now, there is a possibility if you want to snoop on a network to put some put the network cards in something called promiscuous mode, and in that case, you can actually uh snoop in on packets that are going by. Um So, uh So, 168 says that there is a shortage of MAC addresses. Is that what you're saying? Um I I would believe that it's it's possible. Um so, the MAC address uh So, is there any security measure? Uh I'm not sure I understand the question. Is there a security measure about uh whether people are allowed to receive your messages or not? Is that the question that's being asked here? So, uh there's no security on the uh message transmission layer. So, if you think you need security, which everybody should, then you need to explicitly encrypt. This is why you should never uh log into anything unless you're using SSL properly because pretty much anybody can snoop. Uh and you just got to got to realize that's the way it is. So, um So, the MAC address is a unique physical address of the interface. Um you can easily find MAC addresses on your machine or device. Uh for instance, if you um I'm sure you guys have all done this with uh I have config or IP config on Windows, or you pull up about on your phone, you can see what the Wi-Fi MAC address is. That's a 48-bit uh multiple um uh octet basically address. And if you look here, for instance, if you do IP config on a Windows box, you can kind of see where the MAC addresses are right here. Uh etc. Okay? And so, the MAC address is your physical address of a physical endpoint. Okay? Now, um So, why have a shared bus at all? Why not So, you could ask yourself, well, why should we do this sort of broadcast thing? Well, clearly when you're talking about something like Wi-Fi, you pretty much don't have a a choice because it's everybody's bits are flying by. But if you have a physical network, you know, why bother? And the answer is, well, you don't have to. It just It was just that in the original days of the network, it was too expensive to do something other than broadcast media. Okay? And so, why not simplify to have point-to-point links and routers and switches? And the answer is that's the way it does it now. So, point-to-point networks basically is a network in which every physical wire is connected only two computers. And so, here's an example of a switch where you have a bunch of computers attached to a switch. And it's a bridge that basically transforms the shared broadcast media configuration into point-to-point configuration. And so, typically, these are like Ethernet ports. A switch is something you might buy at Best Buy or Fry's or something. And when you plug your machine in, the switch figures out what MAC address you've got. And so, then any communication to your MAC address will be switched automatically uh to you without bothering anybody else. And so, the switch will actually transform what would have been a broadcast media into a point-to-point media automatically. Okay? And it does that adaptively. A router is a device that basically acts between a as a junction between physical networks. So, the switch is is faking out what we would do if we put all these on the same wire, but it's making it much more efficient. A router, on the other hand, is like connecting different wires. And uh when we talk in a second about IP, the thing that distinguishes a router from a switch is a router will take you to different subnets, uh ultimately into the internet as a whole. Okay? Um So, the internet protocol, which is the network level stack, is uh basically provides a best effort packet delivery. And so, when you take um messages that are going from here to to Beijing, for instance, um they'll have an IP address for your destination. They'll have a lot of MAC addresses along the way, but those MAC addresses are only good on the local wire. Okay? And so, yeah, they'll be MAC MAC addresses of your source computer and a MAC address of your port into the IP network. But really, this green thing, which is the IP address, is the part that gets it from source to destination, not the MAC address. Okay? And the other thing is these packets, you put a bunch of packets into the network, they may come out in opposite order. They may come out duplicated. They may come out with one of them showing up and other ones dropped. Okay? And so, this is what we call a datagram service, which basically takes packets from one side and mostly transmits them to the other, but without guarantee. So, it's a best effort service. And so, that is what the current internet is, and we're going to have to figure out how to turn that into something that we can actually utilize for real packets so that we can do our decision-making protocols on top of it. So, um there are two spaces these days of IP addresses. There's IPv4, which is still by far more common than IPv6. Um which I'll tell you about IPv4 for a moment. So, these are 32-bit integer addresses. Um and they're used as destinations for packets. Um they're often written as four dot-separated integers, like this: 169.229.60.83. Okay? So, together, these are um 32 bits. So, this is for instance, this used to be at least the CS file server. I'm not sure if it still is. Um you could also write this in hex as 0xA9E53C53. Bottom line is this is 32 bits. Okay? Um a host is basically computer a computer connected directly to the internet. Um it typically has one or more IP addresses for routing. Some of these may be private, uh and some of them may not be public. Um It's interesting to note that not ever um Why don't we talk about IPv5? I don't know that that exists. Um if it did, it's uh buried in the annals of history somewhere. Um The uh Not every computer has a unique IP address. Um groups of machines might actually share share the same IP address. So, um this is going to be very common these days in everybody's staying at home in the pandemic. They have a I don't know, their Comcast brings a an IP address into the um into your house, and then you have a router there, and you have a whole bunch of phones, cell phones, and uh laptops, and computers, and all that sort of stuff are all behind that one public IP address, and you have a bunch of private IP addresses. And so, basically, uh all of the computers in your house right now uh are sharing the same public IP address with the rest of the world. Okay? And the way that that works is something called network address translation, where um even though your each computer has a unique local private address, uh all of the traffic that goes out of the um router and into the Comcast network all gets translated into that single public address. Um Now, the subnet uh is a range of IP addresses. Okay? And it's identified by a 32-bit value um with uh the bits that differ set to zero. So, for instance, here's a 128.32.131.0/24. This basically says that um all the computers on that subnet share this prefix 128.32.131. Um and so, that allows up to 254 or three, probably 253 machines that are uniquely on there. Okay? Um same subnet is also like this. I don't know if any of you've ever actually done any configuration of your home networks or whatever, but uh 128.32.131.0/255.255.255.0, that's called a mask. What that also says is all of the addresses in this subnet share these top 24 bits, but the lower eight are um assignable in any way you want. Okay? And so, the mask is basically this uh set of prefix bits. So, why am I telling you about subnets uh at all? The answer is that when we're trying to route a message from point A to point B, we're typically targeting a subnet, and the subnet has some we're targeting some prefix of the address we're going to for the next hop. Okay? So, routing within a subnet by mask address by MAC address and the rest is IP. So, I also just briefly wanted to say a few ranges here just so you know, so like a class A address is one that the top eight bits of map to class B is the top 16 bits, class C is the top 24. It is interesting that organizations used to own say all of the addresses like this. So, MIT for instance I know is is 18. And then 24 bits are free. So, the MIT address range is quite large. Berkeley has two 16-bit at Berkeley the University of California has two 16-bit class B addresses. So, let's see what else did I want to say here. So, organizations often own these. So, why did I mention this? Well, these addresses are often handed out and so you can imagine that one of the reasons we're running out of addresses in the 32-bit address space is really because big ranges of addresses are already owned by organizations whether they're not in use. So, in addition to the fact that 32 bits is really not a lot of addresses, there's a bunch of them that are just already owned and not necessarily available for anybody else. Okay? Um So, uh just to get this moving forward a little bit, our packet format is like this. So, a typical IP packet has data of course which we want to transmit. There's a bunch of things in the headers which we won't go into great detail, but I did want to show you here is a 32-bit source address and a 32-bit destination address. So, when you're sending some data or sending a packet off, you build this packet, you put in your address which is a source address, you put in where you want to go. Um and then you put in what protocol for instance if you're doing um TCP or UDP that would be in the protocol type. And you send it off and it's up to the rest of the network to route it from point A to point B. Okay? Now, this is a datagram. So, it's got data in it. It's got a header and it gets sent off into the network and it either makes it or it doesn't and there's not a 100% guarantee from any of the hops that it will make it. So, it's the function of the network is to deliver datagrams as well as possible. So, wide area network now is basically a network that covers a broad area. Often called a wide area network could be like the whole world for instance or it could be you know, kids state of California what have you. The WAN connects multiple physical multiple physical networks. Okay? So, or local area networks. So, if you look here each one of these links could potentially be a subnet and the set of MAC addresses in there might be unique and used to route. So, pretty much everything connected to a subnet in here would all have a unique set of addresses, but what actually happens is host A wraps up a um an IP packet and it kind of works its way hop to hop to hop till it gets to the destination. Okay? And so, these things in the middle are routers which I mentioned earlier and they're basically taking you from one subnet to the next. So, each one of these hops is typically another subnet. All right? So, a router forwards packets from the incoming link to an outgoing link. So, for instance if we looked at any one of those router points, we see a bunch of incoming links, we see a router which is typically a special piece of hardware that is tuned to transmit these packets in and out as fast as possible. You could think of this as a sorting network. So, you know, comes in on one side it gets sorted to the next hop and goes out. And if these are 40 gigabit links or 100 gigabit links or whatever you're currently transporting here, this needs to be extremely high powered hardware to do this very rapidly. Okay? And and some combination of hardware and software. Um so, that's the forwarding idea. So, if you notice isn't that great? So, watch. We're starting here. We've got our IP address of B where we're going and it's just going to get forwarded through the routers to the destination. And the magical thing about this is if you think about all of the hosts in the world, okay? Billions and billions of hosts in the world, um this works. Okay? It actually routes packets and it mostly works. So, that's actually pretty amazing to think about every now and then when you think about scale, how big things actually are, how many addresses there really are out there and the fact that this all mostly works is is uh I I think it's astonishing. I mean, you can easily figure you know, you can easily understand all the mechanisms in there, but when you look at it at scale, the fact that it actually works is pretty cool. Okay? And so, you know, upon receiving a packet the router reads IP destination address, picks the next port and sends it out. And that just happens over and over again. Um often times there's a default route which is if a if a router doesn't know where to go next, it'll send it on to a router that it thinks will know where to go next. Um So, I wanted to say a little bit of a distinction between IP addresses and MAC addresses. So, if you remember the MAC addresses are used locally, the IP addresses are used for these long haul communications and the question might be why? Well, if you look here, um you can imagine a person this person is defined by their social security number and that's a unique person and they're at some address in Washington D.C. and then they come over and they're they become they're in California for a conference or something. Okay? Maybe they've moved to Euclid Avenue in Berkeley. So, why don't we just use MAC addresses for routing? So, you can imagine that we just route packets to to the MAC address. If it's truly unique, it'd be like routing all mail to a social security number. Okay? And so, the question might be why not do that? And the answer is it doesn't scale. And so, the analogy really of MAC addresses to social security numbers and IP addresses to home addresses hopefully is a good one for you. Right? Because when you're routing to this person, basically you're using their mailing address which is in Berkeley, California and so the this is hierarchically routed just like IP would be first to California, then to Berkeley, then to Euclid Avenue and then to 1051 and and that's how you get to the this address of that person when they happen to be there. Okay? And so, the MAC address is uniquely associated with the device for the lifetime of the device. The IP address changes as the person moves. Okay? I don't know if that helps or not, but this is why we use IP addresses typically to route. So, why does packet forwarding use IP address? Why does it scale? And the answer is because if you look at what I talked about with subnets, really there are prefixes and what you're really doing is as you're trying to route from point A to point B, you first route some early parts prefix of the IP address and then you route more detailed prefixes until eventually you get to the subnet that has the actual final computer on it. And so, it scales because we can route all of the addresses at MIT for instance could get routed by just matching 18 in the first eight bits and then you get to MIT and then let MIT worry about routing it the rest of the way. And they the analogy here is give this letter to person with social security number blah versus give this letter to John Smith 123 First Street Street LA US. This latter one is much more of a hierarchical routing and it's a much more scalable. So, how do we set up these routing tables? Well, the internet has no centralized state. So, no machine knows the entire topology. So, you need a dynamic algorithm that acquires the routing tables. Um you ideally have one entry per subnet or portion of address. Uh possible algorithms for acquiring routing tables, you can take a networking class to hear more about this. But for instance, there's something where that works kind of locally. You can have a routing table has a cost for each entry and what's the fastest path from point A to point B. Neighbors keep telling each other over and over again who they know about and you have this dynamic algorithm that converges. Um In in reality, that particular algorithm doesn't scale beyond local subnets really. There's many different levels at many different scales. There's a protocol called BGP that handles uh global routing and it has a way of exchanging routing tables that adhere to certain policy reasons and so on. And so, that that process of making the routing tables so that the routers can do their jobs is in itself a really interesting distributed algorithm which is occasionally unstable. Um there have been some really interesting outages in the internet over the years where BGP got stuck with some loops or there was some key uh link in the network that went down and there was no way to route around it. Um and the routing tables became unstable. Um and so, this is this is in itself an interesting problem that we're not going to study anymore, but I wanted to mention it. Um and so really if we just say that in another slide back here, really when we look at this slide, we're trying to get from A to B, the question is at each hop, how does the router know what the right next hop is based on where you're trying to go? Those are the routing tables and those routing tables uh are the big dynamic algorithm uh that I just mentioned. Okay. So the last topic I want to see if you guys give me a few more minutes and then we'll uh we'll talk uh we'll pick this up on Monday is um naming is a big issue, okay? So if you look um people like to use names for things, but addresses are what the underlying system likes to use, okay? And so when I'm trying to send something to this guy, I want to find out I have to find out what his address is. I got to look him up somehow. Um and basically the way that works in the internet as you're well aware is you're taking names like www.berkeley.edu, transforming it into an IP address 128.32.139.48 and um things like Google actually when you uh look up google.com, you get a different address po- uh possibly if you do this several days in a row, you're going to get a different address or you're going to certainly get a different address if you're different parts of the world or the country because uh that common name gets mapped to a bunch of different servers. But anyway, this process of mapping a human readable name to something that can can actually be routed is something that needs to be done um and because IP addresses are really hard to remember and they also change. Okay? Um and so the mechanism is the domain name service, DNS, which you I'm sure you've heard of. Um it's a system that's been around for a long time uh and it basically defines uh domains hierarchically. So for instance, uh this machine um eceecs.berkeley.edu is a domain. There's the www.eecs.berkeley.edu which is a particular machine and that domain eecs.berkeley.edu is uh referenced off of the berkeley.edu domain, which is referenced off of the edu domain, which is referenced off the top level. Okay? And so there's a hierarchical lookup process for DNS to work your way down, turns out backwards, right? If I'm trying to find www.eecs.berkeley.edu, I start at the top, I go to edu, then I go to berkeley.edu, and then I go to eecs.berkeley.edu uh referencing the lookup, right? And so DNS is a hierarchical mechanism for naming. Each domain's owned by a different organization. The top level's actually handed out by an organization called the Internet Corporation for Assigned Numbers and Names or ICANN. Um and you typically have to get assigned these domains at the top level and you have to pay for them. Um and the resolution of this is if I'm over here or I'm somewhere else in the world and I'm trying to look up www.eecs.berkeley.edu, I go through a hierarchical set of queries to the DNS system to get that number and then the network takes over. Okay? And um because this is a long process, uh DNS is cached in lots of ways and so if you uh look something up because you're browsing the web, that result will be cached in your machine for a while uh until until the cache expires. So remember everything in operating systems is a cache. You guys can quote me on that um because it's true. So how important is it to correctly resolve a mapping from name to IP address? Well, you can imagine the answer is very. Right? So if an attacker manages to give you an incorrect mapping and get somebody to route to a server thinking they're routing to something else, they might do the wrong thing, okay? And probably many of you have at one time or another gotten a complaint that uh the certificate is not valid when you were trying to go to a website and you probably all said, "Oh, just ignore it." But in fact, there is a real attack problem here where uh somebody manages to convince your local DNS server to give you a wrong machine and they're redirecting your attempt to log into the bank to the wrong server and they're trying to get your password and ultimately your money. So this mapping between names and IP addresses is uh a security hole. Um now you might ask is DNS secure? Mostly, it's it's a weak link um and uh it turns out that there's been various holes in it over the years. There was in fact a really famous one in two 2008. You guys can look this up, look up Dan uh Dan Kaminsky. Um he discovered an attack that basically broke DNS globally uh because what it was was it was a way of responding from pretending to be a DNS server that somebody was querying and doing it fast enough that you could convince a whole chunk of an ISP to give the wrong mapping to uh to a lookup and then everybody that happened to be logged into the ISP at that time would get the wrong lookups and you could do this regardless of the security on the DNS servers. And um needless to say uh this was bad, but what Dan did was he actually contacted all the major vendors uh of software and explained what was going on and got them to mostly patch it before it was announced in a paper. Um but if you if you Google that, look it up, it's uh you know, it gives you an example of what could happen. All right. So um I'm going to end for now. Um we've run out of time, but uh we talked about two-phase commit as a good instance of decision distributed decision-making. Um first you make sure that everybody guarantees that they will do the same thing. Um they'll commit if they're asked uh and next every ask everybody to commit. If that doesn't happen, then everybody's going to abort, okay? That's the important part. We talked about the Byzantine generals problem in some detail, which is a distributed decision-making with malicious failures. One general and minus one lieutenants, some of the number of them may be a malicious. We often call that F. And uh we need to have a total number of uh general plus lieutenants that's greater than 3F plus 1 to make this solvable. We talked a little bit about blockchain protocols. Um they basically are a cryptographically driven ordering protocol and we talked about how blockchain is really a type of distributed decision-making. Um we uh started talking about the IP protocol. We'll finish up the little bit that I'm going to talk about in this class next time, but it's a datagram packet delivery service. Use it route messages uh across the globe. 32-bit addresses, 16-bit ports. We'll get to that a little bit more um when we go forward, we talk more about ports. DNS is a system mapping from names to IP addresses uh which needs to be secure because humans uh aren't that good at remembering IP addresses in general. All right? And we'll talk about uh ordering, reliability and TCP next time. So um I hope you all have a great weekend. Um those of you that are in the Berkeley area, I don't know, I think it's going to be cold and rainy, but uh anyway, stay safe and we will see you next week.