CS162 Lecture 26 (Optional): Key Value Stores (Con't), Chord, DataCapsules, Quantum Computing

well welcome back everybody to uh the last lecture 162. this is kind of a a special lecture um i did get some requests for more information about distributed storage and quantum computing and so i think we're going to do that and i want to make sure that we talk through the chord algorithm since that's a i think relatively simple thing to understand and is uh very cool and applied pretty much everywhere so if you remember one of the things we talked about uh last week was basically this cap theorem which was really a conjecture that eric brewer put forth back in the early 2000s and basically said that you could get consistency availability or partition tolerance you couldn't get them all three at once you might be able to get two of them at once and so that's the so-called theorem and we've talked through a number of reasons why that might be true but certainly you can imagine that if you have to be tolerant to cutting the network in half then it's going to be very hard to be both consistent and available all the time all right so oftentimes the cap theorem is a good way to understand global storage systems as a result now um at the very end of uh last lecture we were talking about key value stores and uh the cool thing about key value stores is they're very simple in interface excuse me so basically uh you can have an arbitrary key although that's usually a hash over some value um and you can have a value associated with it and if you do put a key comma value that goes somewhere into the ether and then when you do get of the key you get back the value that you started with and so this interface is extremely simple it's certainly an interface uh many of you have used in languages on a single machine what's interesting is if you use this in a global storage system it turns out that the interface is simple enough that you can have some pretty interesting um implementations okay and if you remember we started talking about key value stores with this notion of a distributed hash table where what i've got in yellow here is really the key value um table that we might think about on one node except that in reality what happens is this gets distributed over a whole bunch of nodes and so the question is really many parts to this question one is how do we actually do that distributing another is when some client does a get how does it figure out which node to go through clearly we don't want to have a single routing table in the middle of the network that's going to be really expensive and then you know what happens if one of these storage nodes fails okay and so there's many failure modes you can imagine there's performance problems and uh scalability issues where we would like to increase the size of the system by just sort of adding more nodes down at the bottom here and um so far we haven't really talked about how to even make that work okay and so today i want to tell you about the cord uh algorithm which uh has been turned into storage systems of many sorts including those used by amazon et cetera okay facebook so um before we get there i wanted to remind you of this notion of recursive versus iterative lookups so um here's an example of a recursive lookup which is like routing so what we're doing so our recursive our routing so basically if i say i want to get uh whatever key 14 has got it goes to the master directory and then that directory forwards it on it routes it to the particular node that's got the results and then the the node returns to the directory which returns back to the original client that's recursively routing its way through an iterative uh approach is one in which the client basically talks to the directory then they talk to the individual nodes and um we're not routing queries through anywhere every individual client is um doing that particular lookup okay and you can imagine that this second example here might be more scalable because we can have many clients all driving the lookups it gets a little tricky to maintain consistency though and so that's one of the reasons we might want to have recursive another is that this is just faster because we're basically just routing the shortest path to the results and back whereas this iterative one potentially um is twice uh the twice the latency okay if you think about this randomly so let's see keep those two implementation technologies in mind they're really interchangeable um and are more about what you do with the control plane portion of this than anything else so um the challenge of that central directory is really that it's got many entries that are sort of key value pairs or at least uh key node mappings and you could have billions of entries in the system and so um i would say that anything that thinks of a directory here like a single server is bound to be a bad idea okay because it's just not going to scale the billions of entries very well all right and back in the early 2000s myself and a bunch of other researchers started looking at how do you deal with peer-to-peer technologies as a way to solve this problem and the solution uh one solution here is consistent hashing which i'm going to tell you about um we did tell you about it last time but i want to uh reemphasize what it is and the idea behind consistent hashing is it's a way to take your keys and figure out a clean way to distribute them throughout the system without having to know pretty much all of the nodes that are participating so this seems like a strong ask when you think about it if you look back at this diagram for a moment if there's hundreds or thousands or millions of servers down here and we have to somehow um consistent with consistent hashing figure out uh which node to go to without going through a master directory and such that all these nodes don't know about each other that seems like it's pretty difficult and that's one of the reasons the chord algorithm is so interesting all right and so this is basically going to be a mechanism to divide our space up and we'll talk you through that in the next slide and then i'm going to show you how the chord algorithm lets you get by with only knowing essentially a logarithmic number of nodes in the total system and you can still do this well so we're going to associate each one of those storage nodes is going to get a unique id okay and that unique id is going to be in the hash space so imagine you take their i don't know their ip address and their owner and whatever you concatenate all those things together and you hash them and you get a single 256-bit id out of that now we're going to talk more about secure hashes a little bit later in the lecture but so every node has an id and it's going to be in this ring space this unit dimensional space from 0 to 2 to the m minus 1 where m is going to be big okay and so let me just show you the picture here so here's an example of the ring uh the ring to rule them all and for the sake of class i'm only going to talk about m equals six okay so really there's only 64 possible spots on this ring two to the 64 to the six i mean it gives you 64. in reality m is probably uh 256 okay because we're using sha 256 to do our hashing and so uh let's just say there's a lot more slots on here than 64. but let's use that for our illustration here and first of all notice on this ring are a set of servers that are they have their id that's been acquired by hashing their ip address and their name or whatever so this node here has an id of four and that means that we think of it as in position four on the ring this one has an id of eight we think about as position eight this one has an id of 32 we think of it as position 32. now hopefully what you can see here is these are not evenly distributed in fact probabilistically they're evenly distributed but they're really a random hash over um over some data that's associated with the node and so they're they're distributed through the ring but they're not equally distributed okay and it's going to be important um in fact that we have a good security hash here a secure hash that can basically pick these positions in a way that's uh hard for anybody to fake okay um and then once we've put these on the ring now what we're gonna say is uh take for instance node eight we're gonna say that node eight stores all hashes uh with keys from five which is just after four to eight and fifteen is gonna store everything from nine to fifteen and twenty is gonna store everything from sixteen to 20. so the way to think about this is we put a bunch of storage nodes on this ring and then we're going to decide where to store our key value pairs based on where the key is on this ring okay now there's a lot of stuff i haven't told you yet like for instance what does this mean physically well i haven't told you physically because since these are randomly hashed um these nodes are going to be spread physically all over the planet potentially the other thing i haven't told you about is how much do each of these nodes need to know about each other okay now so just to emphasize here so key 14 value 14 is going to be stored on this server and why is that because server 15 is the uh closest one that uh whose own hash or own id is is bigger or equal to the thing we're storing okay now i want to pause uh here and see if there are any questions and like i said in practice m is really something more like 256 and so uh this ring is really big and um these nodes are much more sparsely distributed around the ring okay questions we only have a very small class today so you guys are likely to get your questions answered anybody okay no questions all right should we move on now is a system that was developed uh with a group of researchers at mit and at berkeley um and you can think of it as a distributed lookup service uh and it's in my view i like to teach about it because it's the simplest and cleanest algorithm for distributed storage that i have seen and it's a comparison point for all sorts of other uh algorithms okay and the important aspect of the design space for cord is we wanted to decouple correctness from efficiency so we want to figure out what do we need about that ring and the storage servers on that ring so that this the algorithm i'm going to describe to you is correct and then we'll talk about how do we make it efficient okay and the thing that's interesting about chord is we're going to combine that central directory and the storage nodes together and spread them all amongst all the nodes and so we no longer have a single lookup directory and a set of storage servers instead we're going to have a set of storage servers that are just going to talk to each other to make this work and the properties uh are as follows so correctness we'll make sure that each node knows about neighbors on the ring so it needs to know how to go forward and how to go backwards a predecessor and a successor on the ring and as long as the ring is connected the ring is going to perform its tasks correctly and then from a performance standpoint then we're going to start adding some more neighbors and so we're going to start learning about a logarithmic number of neighbors uh across the ring and that's going to help us get a much more efficient lookup okay now there are many other structured peer-to-peer look-up services like this um tapestry is one that i worked on here at berkeley bamboo is another one i worked on there's pastry that was a microsoft uh product there's cademlia there's a lot of interesting ones several designs here at berkeley and so this problem of how to look up a key value pair got a lot of study in the early 2000s okay and let's look about the way to think about chords lookup mechanism is once again routing so it's going to be we're going to describe this in a recursive fashion to start with and then of course you can do this uh in an iterative way as well i think the recursive version is a lot easier to think about so every node in the system is going to know who its successor node is and so here we have an example where some client talks to node 4 and says here look up key 37 for me okay and so what's going to happen well we're going to start routing packets from the point at which we enter until we find the right until we find information about what the right node is that's going to store 37. and we can figure that out if you look ahead which we can't do if we're a distributed algorithm because we don't know about all these nodes but we're looking down from above and you can clearly see that no lookup for a t37 is going to want to get back node 44 because that's what's going to store key 37. why is that well 37 is going to get stored on the node that is the closest one clockwise uh on the ring okay and so 37 the closest one clockwise is 44. so how does this happen well 4 says well i don't know what it is so it routes to 8. it says i don't know what it is that's 15 rounds to 20 32 35 this point 35 knows that it's uh successor is 44 and so it just responds back and says hey i happen to know that node 44 is responsible for key 37. and at that point uh node4 can talk back to the client and the client now knows just to talk to 44. okay now if we wanted to be fully recursive we could have 35 pass a query on to 44 and have 44 send the key back that would be another option okay so if you notice here in order to make this correct so how did we find the first one again that's a great question so the answer is that any clients that talk to the storage server need to know at least one node in the system okay so that one node they need to know doesn't matter which one it is in this case the client which i haven't shown separately out here happened to know about node four and node four serves as a gateway into the ring all right did that answer that question now you can see that this doesn't seem very ideal because if i've got a thousand nodes that are storage nodes i may have to take many hops to find out uh what i want here um it turns out that the worst case lookup here is order n so that's probably bad but we're going to show you how to get login in a little bit it's going to be a dynamic performance optimization and so on that's going to be pretty interesting now what i want you to see though is from a correctness standpoint as long as every node knows who its predecessor is and successor and in this case just its successor then we can always find the server we're looking for okay now what does this really mean okay so here's this ring and here's you know key 14 stored on node 15 let's say what it really means is something more like this right so these nodes since we we're doing hashes over their ip addresses and some metadata it means that um they could be anywhere in the world and then we're connecting them together based on their hash name so fort talks to eight eight talks to 15 and so on so that um for instance key 14 happens to be stored here on the east coast node 4 is up in alaska so um based on what you see here that uh what i just showed you on the previous slide if somebody were to ask node 4 for key 14 we would go from alaska over to the east coast over to the west coast then we'd get the result okay so really because of the hash being a randomizing function uh we've scrambled the geography of this ring okay now that's actually good okay and the reason it's good is because it means that no particular part in the in the world here might be a hot spot it means unfortunately though that we don't have the most uh local of look up because if we start at node four it'd be nice if we could just go down to 15 and back okay now this is a really good question here about redundancy how do we get redundancy out of this for the moment uh suspend that question for just a second certainly we could put raid servers or what you know raid storage on each of these nodes and that would be great if the disks fail but uh we would like something even more powerful because i don't know if there's a big earthquake and california falls off into the ocean it'd be nice to know that key 14 survived somehow so in addition to the raid redundancy that we've been talking about in class there's some other sort of redundancy that we want here okay yeah by the way if you've ever seen the original one of the original um superman movies basically the the plot is the bad guy buys up a bunch of soon to be beachfront property in nevada and then has a plan to basically cause uh california to fall into the ocean and therefore have really expensive properties fortunately superman uh saves the day and it doesn't happen so um okay so if we move um forward with this by the way i'm showing you these clients now to make this a little more clear the clients need to know one gateway into the system in order to talk to the system okay so that's going to be part of the initial lookup and by the way that's pretty similar to what happens with dns you need to know how to talk to local at least one dns server somewhere before you can start resolving names okay so the first thing i want to talk about is how can we make sure this this ring stays connected even though nodes are failing and coming back okay and so how we can make sure it's connected is we're going to have this dynamic stabilization procedure so every node can run stabilize okay in which it asks its successor its current successor node who the predecessor was and figures out you know is there something wrong with who's connected to whom and then if it finds a problem it can run notify to help reconnect the ring okay so let's uh these are the kind of things that are a lot easier to see with um animations and so let's suppose that we have this ring and what i want to show you here for instance is here's a new a new node or it's a node that crashes coming back then suppose that what i want to do is i want to join the ring so what do i do well just like we've been talking with clients presumably what i know is i know one of the nodes in the system and if you remember this ring has nothing to do with locality that node could be i don't know 8 or 15 or something okay and so what i need is i need this new node needs to know one gateway node i'm going to say 15 just for the sake of argument and what are we going to do to join well we're going to send a join message to the node we happen to know about okay and what's interesting about this algorithm is all that the ring is going to do is it's going to figure out who is responsible for storing key 50 as if this was just a regular key value lookup okay and so we're going to work our way through and eventually 44 is going to say well i know about 58 here you go 58 is where key 50 would be okay and notice what we've done now all of a sudden uh no the new node 50 knows that it needs 58 to be its successor and 44 to be its predecessor so just by asking the ring where key 50 belongs it now has some information about nodes that it can talk to okay and so 50 starts by updating its successor 58 so now it's technically connected somewhat to node 58 but you know 44 is also connected to 58 so we now have a kind of a weird partially connected ring okay and let's look through what happened so node 50 is going to run stabilize and so it's going to talk to the successor that it knows about and ask it well what's who's its predecessor so when it does that what does it get back node 58 says oh your predece my predecessor is 44. okay and at that point now things are getting interesting because at that point um we can notify node 58 and say hey you know what i'm actually a person you should know about for your predecessor and um we can also uh take this connection at some point 44 is going to be running its own stabilize stabilize is running continuously 44 is going to ask 58 who it thinks its predecessor is and it's going to say well i think it's 50. okay and at that point what you know is oh 44 says something's wrong here so it's going to change its successor to 50 and then finally it's going to notify 50 about itself at which point 50 knows its predecessor and when all said and done we have the the node 50 has joined now what i want to point out about this joining operation i went through it pretty quickly but you're welcome to go back to slides and animate it through is really what happens is we have this continuous stabilized procedure that everybody's running all the time it's at they're asking their successor who the successor thinks the predecessor is and they just run this over and over again and what happens is the ring keeps converging into something connected and what i'm that will happen even if nodes fail and come back up and so on it'll converge to a connected scenario here okay and um but what you can think about pretty easily i think is if you lose two nodes in a row then what i've just described to you is no longer going to work so there is a way to completely break the ring such that the stabilized procedure won't reconnect it can anybody think about what the right thing to do there is in that scenario how do we how do we make sure that two failed nodes in a row can't prevent the ring from re reattaching itself anybody thoughts yeah perfect we need to know more than just one successor and one predecessor okay and so what that's called typically is the leaf set okay so the leaf set is multiple nodes if you look at any given node multiple nodes forward and backward called the leaf set as long as we maintain that leaf set then we can reconnect in a way that's going to be stable against all sorts of uh failures okay and one thing i posted last time i could move it to today i guess if you want for reading but there one of the original chord papers talks you through about how many of these leaf set nodes you need to make the probability of a permanently disconnected ring so small that you wouldn't care about it okay all right good now questions are we good now one of the things that i will point out is so far we still have this pretty um expensive lookup process which is order n now we have figured out how to make this stable so first of all as long as we have a fully connected ring we can always find the storage uh for this for the data and therefore we have a correct algorithm now um the question that's uh in the chat there is is a good one which is suppose that we had some key stored on node 50 and node 50 disconnects then all sudden key you know a key stored on that node or the set of keys stored on there are suddenly unavailable i'm assuming that's what you're thinking about and uh that's correct so we'll have to we'll have to fix that problem right now we're just interested in the lookup process of figuring out which node should hold our data we'll worry about making sure the data doesn't go away in a moment okay so oh okay um not exactly let's see oh i see if you have two if you have um somebody you mean to like disconnect every other one it turns out that that will uh converge pretty well especially if you have multiple links but try going through the the process and disconnect one and another one uh and skip one in the middle you'll see that uh pretty much what's going to happen is uh you can you can eventually send um let me think about that yeah so you you can you can eventually get this to stabilize and reconnect okay now the multiple the really strong part about keeping things connected is to have a leaf set with more than one node by the way though okay now um and what you should do is you should take a look uh take a look at that paper because they describe this in more detail but um basically what you want is a stabilization procedure that can work even when nodes uh several nodes in a row are failing and what you'll see is that that there's a way to do that as long as you have multiple links and what we're going to do right now for performance is going to make that even harder to destroy the connectivity okay so if you look here the question is sort of how do we make sure that we have better than order n okay and better than order n is uh the following what we're going to do is rather than just keeping track of nodes forward and backward what we're going to do is we're going to keep track of uh our current position plus uh 1 our current position plus 2 plus 4 plus 8 plus 16 and so on and what i mean by keep track of it is here at node 80 the question would be what node would store 81 well that would be 96 what node would store 82 well that would also be 96 what node would store 84 that'd be 96 at some point we get to what node would store you know 80 plus 32 so 112 well that would be 112. okay and we're going to keep track of a logarithmic number of these pointers and of course the way we find out about them is we just query the ring and ask it oh i want to store each of these keys and what will come back from the ring is which node is responsible the power the powerful thing about this is once i've got all these nodes now i can do a really fast routing process to figure out how to find which node is going to store the key i'm interested in okay and one thing that's very helpful here i think in this context for everybody is to think about this as bit correction so i am at a certain position and i'm interested in a certain key and what i'm going to do is i'm going to correct the bits one at a time using this finger table so my first my first routing hop is going to say well if i'm at 80 and i want to get somewhere over on the ring i'm going to connect i'm going to correct the bit i've got in this case it would be a 1 in the high point i'm going to turn it to 0 by taking a long hop and then i'll take a less long hop and so on and i end up with a logarithmic number of hops to get me to my destination and you can view that like i'm correcting the bits from my starting point to my ending point i'm correcting them one at a time by taking these various hops okay and that's how we end up with logarithmic routing time and furthermore this forest of additional pointers plus the extra pointers from the leaf set together make it really hard to be uh unable to reconnect the ring okay and so if you read that chord paper it talks about how you make use of all the information you've got to keep the ring connected okay questions okay we're good now let's think a little bit more about data okay so um so basically first of all we're going to have um more than one forward and backward link called the leaf set um and uh in the predecessor reply message node a can send its k minus one successors and so on and so you can see what's going to happen is during these heartbeat process of looking things up you know asking well hey my successor who's your predecessor during that process the stabilized process we're going to get back multiple nodes which is going to help us get a forest of connection connectivity forward and backwards and that's going to allow us to keep our leaf set uh as as correct as possible and i will point out by the way that these these links are really uh just an approximation of what we need so if it turns out i try to take a hop that's long and that node is down the one that this happens to connect to then that's okay it's going to connect to 20. i'll just take the next one okay and so i can always revert to taking the order n uh routing path until i've got some of these long hops available to me okay and so that that it's a very um it converges very nicely on a performance version of things but it can always fall back on the circular routing process if some of these fingers aren't correct and we just keep refreshing them over and over again and so there is a finger table look uh lookup process that just keeps renewing these pointers over and over again and the good thing about that is as new nodes come in the finger table adjusts as new nodes leave or as old nodes leave the finger table adjusts so that we keep ourselves with our log n lookup all right now um and you end up with really high probability even if half of the nodes fail so you can if you have log m where m is the number of nodes of the system you can end up with a situation where you can find data even if half of your nodes fail you can find data with the right number of leaf nodes and that's kind of what's proved in that chord paper and that's not that many because it's a logarithmic number okay so uh before i go on to uh storage fault tolerance for the data does anybody have any questions on this we good okay so um now let's look back at what we had a slide before right so we had key 14s stored on node 15. and the downside of this is of course that um the way i've described this first of all the only place for node 14 is uh for key 14 to be stored as on node 15. now if you look at the uh consistent hashing what it says is if node 15 weren't there key 14 would be stored on 20 right that's just the next node up from 14 since the only copy of key 14 it's currently stored on node 15 if 15 dies or goes away we don't have the data and so so uh it's fine that the consistent hashing tells us where it should be stored but we can't store it there because we've lost our data so we got to do something else here okay and the way we're going to do that is we're going to take the forward leaf set or you can do both forward and backwards up depends on the algorithm and what we're going to do is we're going to store 14 on the successive nodes that we know about because of the leaf set so we'll store it on 20 and 32 and now what's good about this is if node 15 fails which is the point that's supposed to store it we've already got a copy on node 20 and node 20 can notice oh 15 went down therefore node 20 can start the process of making sure that 35 gets a replica and we always have three copies in our leaf set okay so if we think of the leaf set as not only for keeping the ring connected but also for how we replicate then we can now come up with a dynamic process that automatically adapts as nodes fail by replicating on successive nodes and making sure that we always have a given number of copies in the system in addition to the ring being connected okay so if node 15 fails now what we'll do is we'll uh we'll add an extra copy to node 35. okay questions and the ring is going to stay connected because of our connectivity algorithm and so what's good about this is like i said you store the data in the cord ring and it it's very hard to destroy okay why are they called leaf sets that's a good question the reason they're called leaf sets is because uh in some sense you can view the uh if you take any given um starting node like 58 and you view the set of fingers that's a tree and so eventually you get to the leaf set and uh and so it's like a tree with leaves so that's where the leaf is coming from um and here's an example of that uh so if you look at what happens um in with leaf sets so i'm going to show you here is here for instance is a starting node i've got its leaf set is in green the the finger tables are in red and suppose that i'm trying to get from here over to here okay and so what i'm going to do is i'm going to start bit correcting so i might take a long hop first and now i can check all of the all of the fingers okay or i guess you could call them branches if we don't want to mix metaphors too much and the leaves and none of those quite have what i want so i'll follow one of these branches it's a little shorter and then eventually i'll get to a node that's this one where that node knows because of the leaf set which node is the one i'm looking for which is going to be the one that's just bigger counterclockwise or excuse me clockwise from the id i'm looking at okay and so this leaf set not only serves to help us with our replication but it also serves as uh as part of the last couple of hops we can use the leaf set to basically find who's supposed to have our data all right um now so let's look at replication from a physical standpoint right so if you look again at this ring i showed you a little while ago that ring is mapped physically to things that are spread widely and now we can see another big advantage of the randomness introduced in chord and that advantage is that these copies are actually stored in geographically separate places and so when the big one happens in california it's not likely to take out you know uh things over here in minnesota okay and so we um the randomness is helping us to avoid correlated failures where yeah we have a bunch of copies but they're all in the same machine room and the building got struck by lightning so that doesn't happen in a chord algorithm it's sort of geographically distributed by nature okay the downside of course is performance uh might hurt if you happen to be too far away from a copy um and so i will tell you that there are subsequent versions of cord which uh when you're doing this routing and you have a lot of options here see how we have many places we could go we can actually uh take places that advance us the furthest along the ring while keeping locality as short as possible and so we can actually take locality into effect to some extent in chord and um and make our routing less like bouncing back and forth across the planet randomly and more like working our way uh physically toward the thing that we're interested in all right good last but not least um and and i didn't have slides for this but i want to point this out one of the things we can do with chord is we can use chord to store locations of data rather than the data and so think of this like a dns built out of cord and so what the client does is the client doesn't know where the data they're interested in is they ask the cord ring the cord ring tells them who to talk to and then they can talk directly to them and exchange data over the shortest path possible using tcpip or whatever and so you can now get the best uh of both worlds and that you have very hard to destroy lookup process and then you can choose here's the client and it's using some data you can choose to replicate uh that data on close to the client and maybe a couple other places close to the client even though the initial lookup might be geographically separate once you start using the data and know where it is you can have good locality out of it and that's pretty much what we did with the the tapestry lookup process back for ocean store okay so i did want to point out that what i've just described to you this chord ring is actually used in lots of uh cloud services these days the idea at least so for instance dynamodb and i have a paper for that up on the reading from last time uses the chord rings and you can look down here but it uses them rather than spreading them around the planet it uses them within their machine rooms as a way to distribute load uh and so when you're ordering things from amazon and you're ordering you know you're putting things in your cart all of that data is actually stored in something like cord that's in a machine room okay and the applications uh because they're worried about people and uh not um pissing them off when they want them to buy things uh what the cord ring is really about is making sure that they can get their performance uh for retrieving something within a small number of nines okay and so the availability is an important aspect here and so um basically you have a service guarantee that says we'll get a response within 300 milliseconds uh for say 99.9 percent of the requests okay and so that's part of the way that the chord algorithms are adapted in uh in a read real cloud service okay all right and um notice that this is very uh in contrast essentially to what we've been talking about a lot of the rest of the term uh which is focusing on mean response time instead we want to have guaranteed performance okay and this is again thinking i want you to think back to when we were talking about we were talking about real time scheduling and what was important there was keeping the uh predictability of the scheduling time uh low or keeping the predictability high and keeping the timing tight rather than worrying about making it as fast as possible so s3 is actually using something slightly different but there's lots of different schemes out there what's good about the various things that are using chord like uh chord like algorithms is this is scalable as you can imagine if you don't have enough performance you can just start adding more nodes and it adapts automatically which is pretty good okay so what i wanted to do next uh i'm going to leave that there a little bit i want to talk a little bit about security and then um talk through a couple of things and then i want to uh try to get to quantum computing as well so we can i know there was some of you asked some questions about that so i'm going to leave this topic unless there's more questions okay so i'm going to talk through a couple of things that i'm pretty sure i'm assuming everybody kind of knows but i want to make sure we all have the same terminology so um you know security is an interesting thing it's basically computing in the presence of an adversary so i'm assuming several of you have all taken 161. um i don't know if that's true or not we have a very small class tonight but um you can start worrying about things like um can that adversary uh prevent me from making forward progress or can failure prevent me from reliability robustness fault tolerance etc security is kind of dealing with actions of a knowledgeable attacker who's really trying to cause harm and we want to make sure that uh they can't really screw us up okay and we talked about byzantine agreement uh a couple of weeks ago that's one example of trying to prevent a decision-making process from working but in general security is kind of dealing with situations where there's an adversary uh there's a security problem okay and there's been many problems okay where people have broken in to systems and um you know it's a it's a constant arms race uh preventing people from breaking into things you care about by using new techniques and the distinction between protection and security i think is an important one because protection is the set of mechanisms that we talk about in this class security is basically using those mechanisms to prevent misuse of resources so for instance virtual memory is a mechanism that can be used for protection security policy would be making sure that when we use virtual memory we don't let malicious processes or different processes owned by different people uh use the same memory and have a potential for screwing each other up so that would be a security policy built with our protection mechanisms okay so i wanted to point out something interesting i don't know if you've ever seen this before but here is a car in the ditch and what's interesting about this particular car in the ditch is that back in july of 2015 there's a team of researchers that took complete control of a cheap suv remotely exploited a firmware attack over the sprint cellular network and they basically caused the car to speed up and slow down and and veer off the road and uh totally wirelessly so this is a little scary uh to think about now fortunately no humans were harmed and the people that whose car was driven off the road were researchers as well but um you know this is something that one might hope our security policies could prevent and the thing that is getting in the way of preventing things like this is that there's an increasing amount of machine to machine communication where it's really machines are talking to other machines controlling each other and making sure that a malicious person can't get in the middle of that and cause unexpected behavior is very tricky and there's this term cyber physical systems which i don't know if how many of you have heard of that but the idea is computers controlling physical things using policies and algorithms and the problem is that if somebody manages to get in and mess with those cyber physical systems uh they can cause physical harm okay and that's a problem so part of this question is the following so let's talk about the data so there was firmware in this car so one might argue that one of the problems was that firmware was accepted as uh authentic even though it came from a malicious third party and so one of the questions that's important is do you know where your data came from that's a provenance question another is do you know whether it's been ordered or changed or altered in any way that's an integrity question and really this is a question of the rise of fake data which is kind of much worse than fake news which is about corrupting the data and making the system behave very badly so you know we have several security requirements that people talk about so authentication is making sure that a user who's making changes to the system is really who they claim to be data integrity is making sure that the data hasn't changed okay so that's important confidentiality is making sure that the data is read only by authorized users so that often involves encryption of some sort and then non-repudiation is a surprisingly important thing that people don't often talk about which is that if one sender makes a statement and they uh send a message or whatever they can't later claim that well i didn't really send out somebody malicious did and so that's basically making sure that you can't repudiate things that you've previously said and so i'm hoping that if you haven't taken 161 it's on your list because there's a very interesting set of things that people can talk about but cryptography is one of the central points of many of these mechanisms you just have to use it correctly and this is communication that's in the presence of adversaries uh it's been studied for thousands of years there's actually uh something called the code book which you should look up which talks about you know thousands of years of cryptography and the central goal has always been confidentiality about encoding information so an adversary can't extract it the general premise is that there you know there's a key and if you have the key you can decode things if you don't have the key it's impossible what's gotten more interesting over the years of course is public key cryptography where there's really two associated keys and you encode with one and decode with the other and that really leads to all sorts of really interesting authentication problems okay so basic uh cryptography which you've probably heard about is you have a secret key and you take the plain text and you encrypt it with the secret key and you send over the internet something called ciphertext which is encrypted and you can decrypt it the other side and um assuming that uh the key hasn't been leaked then it's not possible for an adversary and and you have a good algorithm like aes it's not possible for an adversary to send a message that the receiver will treat as real because you have to have the secret key now one thing you do need to do in order to make this single symmetric key encryption work which symmetric because the same secrets used at both sides is to prevent a adversary from holding on to an old message and sending it later is you have to start adding what are called nonces which are things like timestamps and so on so that every time you send this it's unique and if somebody sends an old version you can detect it but i'm assuming everybody understands the idea of encryption with uh with a symmetric key and the other thing is i mentioned hashes earlier and so the idea of a secure hash function is one where you take data and you run it through a hash function and you get a bunch of bits out of it and if you change the data even slightly you end up with a good hash function with something that essentially roughly half of the bits change so um this you know the change from fox to the red fox runs across the ice will give you something very different if you take fox and you add a few uh things after it it'll also change it uh drastically okay and so the hash we often talk about is the hash of a message is a set of bits say 256 bits and this is a good example of what we used on the chord ring where that ring was two to the m possibilities well that might be a uh the result of a hash function like sha-256 okay and what makes this secure is that it's not possible for somebody to come up with another source that matches the hash function okay that's one uh example of something that's not possible in fact it's not even easy with a good secure hash function to come up with two different items that you come up with yourself that have the same hash function okay and so that's why we can kind of use hashes as a proxy for the data itself and a lot of the things you hear about in in secure security literature using cryptography assume that the hash function is a is a reasonable proxy for the data itself okay so sha 256 is a good example so here we can for instance if we share a key okay what we can do is we can and that key is secret we can take a plain text something like a contract and we can run it through a hash function where we take that key and an append m and that's called a digest now we can send that across and the data and at the other side we can verify by re uh computing that hmac okay and if they match the one that was sent across versus the one that you computed yourself then you can know that the message is not corrupted otherwise it's corrupted and so we can use hashes to prove later that you know after the transmission has happened that the data is authentic okay so hashing is pretty powerful and i'm not going to have a lot of time to go through this with you that's a 161 topic but just you know keep that in your lexicon about hashing being a good way to ensure the integrity of data at the other side and so for instance in that firmware problem with the car we could have a key that only came from the manufacturer in a secret way and we could check the integrity of that firmware against the manufacturer and if it wasn't uh you know if the integrity wasn't high you know it was basically didn't match then we could know that that firmware is probably bogus and we shouldn't be using it okay now the downside of course of everything we've talked about is both sides share the same key and so if you leak the key then you got problems okay and furthermore you have to somehow share the key and so that requires you to go in a dark alley and you know hand the key over and so this seems like only part of the solution and um the interesting thing about that is this idea of public private key pairs and public key encryption which again the cool thing about that is that now you can distribute the public key let's suppose that somebody over here wants to have anybody send them a secure message they generate a public private key pair they give the public key to somebody else they pro they can broadcast it uh you know to the world and uh then anybody who wants to send a message just encrypts it with the public key and the only way to decrypt it's private key and that private key is something that i hold uh secret but the public key i broadcast and so this is basically uh this is the the basis for all sorts of modern algorithms okay among other things if i were to encrypt uh the hash over data and then uh encrypt it with a public key then i can know for a fact that that data has made it through um and only could have come from somebody okay so that's part of uh how we actually sign things all right so for instance here's alice and bob let me show you a fun algorithm here bob sends his public key out in to the wild to alice um now alice can encrypt messages and send to bob and only bob can decrypt him alice can send her public key and now bob can send things to her and what we're done with is now we've got a secure channel between the two of them given public information all right and now this is another mechanism we can build all sorts of stuff about okay now the uh the question about how to know whether this is a valid public key requires public key infrastructure but that's another story so now i'm i'm going i went through this very quickly how many people have never seen anybody uh never seen this kind of thing before or is this all pretty familiar okay good oh great this is in cs70 great so let's talk about a project that i've been working on so again you could view security as trying to protect things with a firewall or you could view security as it's all about the data and if you can protect the data then you can protect everything okay and so if you think about the internet of things really uh one way to look at the internet of things is that we have a whole bunch of devices and compute elements all over the world and it's really a graph of services that we want to connect and so distributed storage is everywhere every arrow represents communication we've got storage everywhere and really what we want to do is we want to make sure that the data can only be written by authorized parties and only read by authorized parties okay and these secure enclaves um are a topic for another day as well but this is a special um virtual machine that's in modern hardware that basically allows you to set up a secure channel and do some secure encryption in a way that um not even a um not even the local operating system can see the data okay and so if we have these secure enclaves stored everywhere and secure encrypted data then perhaps we can do some interesting things okay and we can do them securely and so um let me see i'm running low on time here i wanted to say something a little bit interesting here about why data breaches which we've heard a lot about in the last four years are so prevalent okay and if you look the problem is that people who are trying to build secure systems kind of think of it this way they say well i've got a secure network on the left i've got a secure cloud in the middle i got a secure network on the right and they're so secure that the only thing i have to worry about is securing the communication between these uh parties and if i do that then the system's secure okay and so this is what i like to call as border security rather than data security and so if you think well i'm going to put some firewalls and now i can say look this is a trusted computing base that's secure this is one as well there's one around the cloud and then you know the only thing left is cell phones which i make secure tunnels with and this just is fine um the problem with this point of view which you've probably heard about everywhere is the moment that we have any breaches inside the trusted computing base then all of a sudden not only is the data breached but somebody who is inside that firewall can produce data that looks authentic uh even though it's not because people are trusting well if it came through the firewall properly then it must be authentic and if you think back to cyber security you know um if you think back to what we've been talking about with that car suddenly that might be that you could have firmware that looks like it's from the manufacturer even though it's from an adversary and now we suddenly have this issue that physical devices that are trusting on this security suddenly start performing things they're not supposed to okay so the real reason we get these data breaches everywhere is because people think that they can put these boundaries up in a way that don't um can't be breached and of course we know that's not true and basically uh the problem really is not only are things breached but the integrity and the provenance of that data is not known so what do we do the data centric vision which is one that um i've adopted in uh my research group is one in which we think about shipping containers full of data so if you think about uh down the port of oakland you've probably all seen these shipping containers um this was a a great invention back in 1956 so before 1956 what happened was we had uh longshoremen who would take a bunch of things and they would go to a ship and they'd play tetris with it to try to fit all of these things onto the ship and then the ship would go to its destination and then there'd be people there that would unpack them and then you'd have to figure out how to put them on trucks and so on and it was a mess and basically one person that said well why don't we just make things that are all the same size and shape and then all of a sudden we've got ships trains cranes all of the the uh infrastructure for handling these things are the same across the planet and now i can ship something from my house in lafayette to beijing the outskirts of beijing just by calling the right trucks to come pick up a shipping container which gets taken to the port of oakland put on a ship and then it goes across the ocean and it's unloaded and and so on and why is that that standardization of the container so the idea that we've done in our group is to say can we use this idea to help in some way and the idea is very simply that we think of shipping containers full of data which we call data capsules and the reason i've got this little green bound around here is because it's a it's a data capsule and inside the data capsule is a bunch of transactions that are hashed so remember those hashes we talked about and signed where we uh we use a private key to sign a hash over something and as a result we trust that this really came from the person who said it did because only they could have the private key and as a result of these data capsules this gives us a cryptographically secure way of moving data around to the edge to the cloud and back again in a way that nobody can fake out okay another way to look at this is this is like almost a blockchain in a box okay and so what we're doing in our group is we're looking at how to take these data capsules make them a standard in a way that everybody uses them and on top of them you can build file systems and databases and everything you're used to but underneath the network knows how to ship these things around and route queries to them and so think of this again the underlying network is like the ships and trains and cranes and planes that handle this standardized metadata and what is the standardized metadata well it's a hash over an owner key and some other metadata about who created this and that forms a unique address that you can route to in our system unlike um not unlike an ip address but it's a unique hash over the data and you can imagine these things being small so they could be on phones or really large so they could be you know terabyte size databases but that standardized metadata is really what allows them to uh be shared uh securely across the planet pretty much okay so why is this idea help the networking effect okay i'm actually pun intended here so standardization makes it possible for the infrastructure to be put everywhere and it benefits everyone federation you can actually build a market of service providers the data becomes a first-class entity so your data basically can float pretty much anywhere so you could put a data a data capsule server in your house and all of a sudden your local data capsules could be stored there or if you're doing some communication with somebody else you could get a copy of their data capsules and again because it's like a blockchain in a box it's not possible for somebody to fake data that doesn't belong in there okay and so think back to that firmware issue with the car in the ditch okay and the other thing is that metadata we're looking at actually has details about what the network should and should not enforce and so you can even start talking about privacy where if you had a bunch of cameras in a local edge domain and they were taking a bunch of data and putting them in data capsules you could make sure that the network would refuse to route those say outside of the house or outside of your building if that was disallowed all right so the vision here is really the following it's you have a bunch of resources underneath these are spread in the cloud and through endpoint places all over the network you've got data capsules that have the ability to float anywhere they're allowed and that's what we call the global data plane okay so the global data plane is something that is uh spans the globe just like if you remember just like the cord ring spanned the globe okay it's again it's a peer-to-peer system uh just like ip as well that does routing and multicast it has things we call trust domains and accounting below you can have many utility providers kind of like comcast or at t that all provide service and above there's an api that allows all of these apps to access their data in the data capsules okay and so this is like me and my house calling a truck to pick up a shipping container okay and so this vision if this uh is ultimately complete is one where you instead of paying for ip service you'd pay for data capsule service and um you'd be able to store your data in a way that was secure okay and could be used anywhere you want and you'd own your data okay so physical view just one last little slide here and then i'll move on to to the uh quantum computing so i want to make sure we cover that but if you think about ip the way we talked about it briefly in a couple of weeks prior if you look at the physical view of ip there's a bunch of routing clouds and there's also transit providers okay and so this is exactly how we get ip working and so in the global data plane we do the same thing where we have global data plane domains we have routers that route global data plane traffic and they're tied together just like we get with tcp ip okay there are peering arrangements just like with ip and as a result and we have name resolvers that help us find our data capsules and as a result we could actually have uh forgive me building all this up but we can actually have clients which might be compute they might be little robots they might be smart cars or teslas can all tie into the global data plane and access data that they're authorized to do uh anywhere it happens to be and if they need high performance or privacy they can pull it to their local domain and so the physical view of the gdp is really um instead of thinking about packets you're now thinking about data and its integrity and its provenance okay so it's a it's a switch in viewpoint on how we want to be dealing with data all right sorry if that's a lot of information but i wanted to see if there's any questions there before i switch over to some quantum computing all righty give me a second i'll be right back and then we'll see if there are any questions that came up one moment okay so good so we have some good questions here so first question is how do we know the data is secured so um just like with a blockchain let me just back up to the picture here which i think is a is a good one to be talking about um what we know is the following the metadata is uh among other things the public key of an owner hashed okay and so all of these signatures have to be signed by the owner and anybody can verify that um the data that's in here was put in there by the right owner okay so that gives us integrity and providence it means that we can know that none of the data that's in here could have been put there by an adversary so that's the first um thing that we know and the second thing is of course we can put arbitrary encryption on top of this as well to make it uh private so really the signatures are about integrity and who put the data there and uh the encryption would be about privacy and there are many ways of uh deciding kind of which keys to use for that encryption and how to share them with people you want to decrypt okay and so that's the that's the um the security of this and uh what you know is when you get some data from the network you can immediately verify that that data is uh what it's supposed to be so you can you can check that the signatures are correct and if you have a signature only at the end of a chain of data you can essentially check the rest of the chain by checking the hash pointers so these are all of the things you get out of a blockchain by the way for those of you that are familiar with bitcoin or whatever you get it here with the data capsules and so i like to call these cryptographically uh hardened bundles of data and if somebody tries to put garbage in there a legitimate person who's trying to look at this can just throw the garbage out because there's no way that that garbage could have been put in there uh in a way that meets the integrity constraints of the data okay and so it's not forgeable um it's uh it maintains its integrity the the transactions can't be swapped or whatever and so it's a it's a unique umly uh high integrity kind of bundle of data and if you build file systems and what have you on top of this really what you're doing is you're appending data to that and it becomes a secure log on which you can build pretty much databases you can build file systems all sorts of stuff okay so this linked structure within the data capsule is really um is just think of this like git you guys are all familiar with git now so this is like a get tree uh with signatures and uh integrity through hashes okay and the signatures can't be faked again because only the proper owner knows the private key to produce the signatures okay and so if you breach the private key of course that's a problem but potentially every data capsule could have a unique private key which leads to an interesting key management issue but that could be another topic okay did i answer those questions so the vision here really is of pretty much everybody using data capsules everywhere okay and um if you can get that to happen then uh you know basically you potentially have um a very interesting scenario here now i just wanted to share uh another uh point here really quickly so for instance the way we're looking at our routing plane is really um the data plane itself is a is a series of routers that all know kind of where the data capsules are and have some very interesting properties where if any of you want to come work on this project come talk to me uh separately we have plenty of uh places we can talk to you okay now i'm gonna i wanna i promised you some um i promised you some quantum computing i did wanna show you one other interesting slide here potentially uh which shows you kind of an idea of how we can build things up um here so uh the data capsule infrastructure is it spans the globe kind of just like tcpip does and so in that scenario what you get is you get potentially these gdp switches which are just overlay network on top of ip you can have location services and storage services for storing data capsules you can have secure enclaves which lets you do secure computation and then you can have lots of uh interesting clients and part of what we're doing is we're working with roboticists and machine learning folks to put their data and their models for grasping and so on inside of data capsules and as a result they can reside securely in uh in the edge in say your robots or whatever in a way that can't be uh breached okay and so this is uh really targeted at uh secure edge infrastructure in addition to the cloud so these data capsules can move back and forth but certainly you need something like this on the edge because these pieces of hardware are easily breached and you want to make sure your data is is uh secured and unforgeable all right good so let me say a little bit about using quantum mechanics to compute and since there's only a few of you tonight if you're uh willing to hear me out i can talk for a little bit longer just to get through a couple of other things on quantum computing um but uh you know what does it mean to use quantum mechanics to compute so it's basically using weird but kind of useful properties of quantum mechanics two of them quantization and superposition i don't know how many of you have taken a quantum mechanics class but uh what you find out is for instance back in chemistry if you remember from chemistry you had the orbitals right and so only electrons were only allowed in certain rings or spheres actually around atoms and that was because of quantum mechanics that's quantization that says that the uh the electron could either be you know at one point the s equals zero or the s equal one or s equal two but nowhere in between and that quantization really gives us the ability to talk about something like a one or a zero so we've got the idea of digital data varied in that quantization but because it's quantum mechanics we can do the second thing which is superposition and this is having uh a bit which is both a zero and a one in certain fraction of uh between the two and that's where things get interesting okay it's like it's fifty percent zero fifty percent one or something in between that's called superposition and um what's interesting to me so i've you know designed computers in various times in my life is that most digital abstractions that you might learn about in 151 or pick your 141 some of those uh various vlsi classes is you're spend a lot of time trying to get rid of the quantum effects you want a zero to be a zero and you want a one to be a one and you want them to stay that way and it's when they don't stay that way that you got problems so then you put error correction codes and all that stuff that we talked about uh last week and the week before quantum mechanics however if you're willing to allow things to not be always a one or always a zero what you can do is you can just start doing quantum computing and that's basically using quantization and superposition to compute okay and so some interesting results just to tell you uh quickly here is for instance shore's factoring algorithm factors uh large numbers in polynomial time even though the best uh known classical ones are sub-exponential um in the number of bits and so you know if you could get a shores algorithm running on a quantum computer pretty much all rsa cryptography would be broken because you could factor okay so other interesting results here are for instance grover's algorithm um is is not as spectacular but it's still pretty interesting so imagine you've got an unsorted database of millions of elements okay so what is unsorted means if it's not sorted right so if you wanted to find a value uh what you know on average how many elements would you have to look through in a million items before you found the one you want well on average you'd have to look at half of them and however grover's algorithm using a quantum computer lets you find items in an unsorted database in a time that's a square root in n rather than half of n okay that's pretty interesting right um the other uh so uh 191 is mentioned in the chat that's a good class to take if you're interested in quantum computing um another one that's my favorite i think best application of quantum computing is what i like to call material simulation this was kind of the original uh the original application of quantum computing that was uh thought of and basically the idea there is if i want to design a brand new element or brand new material to build things out of and i want to take into effect all the quantum mechanic effects then exponentially i or classically i'd have to build something that was exponentially hard but it'd be linear time in uh in a quantum computer and so if i'm really interested in designing exotic new materials to build interesting things i probably want a quantum computer so there are many other algorithms out there now these days they've been slowly working on them but these are some pretty good ones that give you an idea why this might be interesting okay and furthermore we've got google we've got ibm it's very popular these days with big companies uh microsoft is in here as well looking at building these quantum machines both of these two both google and ibm are super conducting bits so these parts of the machine you see here are normally put into a doer and they're running you know at four degrees kelvin or something really cold this particular type of quantum computing technology is not going to be in your laptop at least not in any laptop i'd want to put on my lap but there are other types of technologies including ion traps that potentially are pretty interesting that there have been some thoughts over the years might be able to run at something closer to room temperature not there yet the current goal of google and ibm and and there's been some notion that maybe they've shown this is to do something which they call quantum supremacy which is basically to prove that there really is uh a possibility that quantum computers could be faster than classical ones and so the the issue here is that um these computers by being built by google and ibm have you know maybe have order 100 bits maximum it's very hard to do anything interesting with 100 bits but they're focusing on demonstrations that show that with those 100 bits they could potentially do something a lot better than a classical machine so that's called quantum supremacy so what i wanted to do just to give you a little flavor for quantum computing that you can go away with here is here's a here's a version of quantization that's particularly simple to get once you got it and that is there are certain particles so protons and electrons and neutrons those are good examples that are what are called spin one-half particles and physicists treat these things like they're spinning like a top okay except um what's interesting about that is that they can only spin with the axis pointing up or down nowhere in between okay that's the quantization thing and what i'm showing is this is the spin relative to a magnetic uh pole north and south and what's interesting about that spin upper has been done down is that now i've got zero and one okay so suddenly i've got binary that's interesting right and so these are particles like protons or electrons have this intrinsic spin and so now i got one and zero or up and down okay and a representation called the heisenberg representation looks at this uh messy physical situation like this which is either a zero or a one in these brackets and that represents spin up and spin down okay or vice versa depending on how you want to whether what it's looking like if you're with the field then that's a lower energy so that's probably spin zero it's probably zero now one proposal for building quantum computers from way back when was called the cane proposal and those spins were actually what you got when you um embedded phosphorus impurity atoms into silicon and then those phosphorus impurities would have a spin up or spin down that could be treated as one and zero and then you could actually use these electrons to manipulate okay and that was one of several sort of uh what i like to think of as scalable solutions built on top of silicon which are you know exciting because maybe you could get moore's law out of them and this is an example of something people were looking at okay but the temperature here was less than one kelvin which is really cool okay but let's suppose now here's where the quantum computiness gets pretty tricky okay and and uh bear with me just a little bit i know i'm going a tiny bit over here but um if you think of the zero and the one thing okay this is actually a wave function if you take quantum mechanics representing spin up and spin down and what's interesting is the wave function in quantum mechanics is actually a complex uh function um that i can add together c zero plus c one as a complex coefficient and all i need to make sure is that the um c zero uh squared plus c one squared is equal to one so what happens is these actually end up being probabilities that if i actually tried to look i would see a zero or if i actually tried to look i'd see a one and so what you see here okay with this psi function is actually a superposition of zeroness and oneness together okay now you know i realize this looks a little weird we don't normally get a wave function notation in 162. but um the thing that's uh like i said is very interesting about this is that this is a description of a combination of zeroness and oneness where the probabilities can be adjusted anywhere any way you want such that they their squares their norm squared adds up to one okay and if you measure the bits you actually said well do i have a zero or i have a one what's funny is you find out you don't have this thing because when you look at it you either find up or down with a given probability okay all right now bear with me so those of you that are skeptics out there would say oh really i don't know whether it's a zero or one so these these c zero and c ones really represent uh my lack of knowledge but once i finally looked i found out what it was okay i'm sure that there are several of you that think that that's the case um but that's one option the other is that this is a real effect in the proton or whatever we're looking at here is actually sort of in one state and sort of in another okay and those are those are two options and it turned out that there was there's a set of famous bell uh inequality experiments that were done that showed that reality is actually the second choice so in fact as weird as it is uh that proton is is a combination of zero and one at the beginning and it's only when we look carefully and force it to be one or the other when we actually try to measure it then it gets forced into a state okay and so if you think about this in terms of building a quantum computer there's a couple of interesting things here so one we got to make sure that the environment never measures before we're ready because otherwise we'll destroy this interesting superposition and maybe we need that to compute okay and just to get a better notion of how weird this really is okay so if i have a bunch of bits and bits together there's two to the n possible values of n bits you know that right but here's an example of a three bit example of a superposition in which there are eight options and i can simultaneously have one of those eight or many of those eight values in different proportions as long as the probability um sums up to one okay so as long as c zero zero uh norm squared plus zero zero one norm squared plus this plus this positive this sum up to one that's a real physical situation which represents a single register in my computer that has a superposition of all of those values and the moment i take a look then i force it to be one value okay and so if you only measure one bit for instance you can say that the first bit will be a zero with probability what well which ones have a zero in the first bit this one this one this one this one so the probability of finding a zero in the first bit is this sum probability of finding a one in the first bit is this sum and you can go from there okay so we really don't want the environment to measure this before it's ready so in fact we can have quantum era correction codes believe it or not which can protect this quantum information from being measured by accident by the environment and as a result really we can we can hold these quantum states for a long enough period of time to actually do something interesting with them so let me show you this uh simple two-bit state okay this is called an epr pair for einstein pradonsky rosen it was produced by einstein and pedonsky and rosen as a thought experiment and the idea is i've got two bits but i don't have all four options i only have a zero zero or a one one okay those are my two options and i separate the two bits so this is the two spins and in fact what i do is i maybe send one on a rocket ship to go light years away and so now these two bits represented by this state are light years away and if we measure one of them like let's suppose we measure and find that there's a zero back on earth we know instantaneously that we got a zero on the other side okay and so that looks like we had faster than light travel in fact instantaneous travel of information from the earth out to that redu that far planet einstein really didn't like this he called it spooky action at a distance okay but in fact uh what's interesting about this is you can prove that there's no actual information transferred okay so however we can use this to do what's called teleportation um which is take information uh at one side do some measurements send some data to the remote side and recreate the data recreate the quantum state at the other side that's called teleportation okay all right so i'm about to lose a bunch of you but let me just show you how you factor with this because i think this is interesting so the way we build a computer is we take a complex state like i just showed you and then we put it through a bunch of adders whatever you want to call it which are really all unitary transformations they're things that make sure that that probability always adds up to one and then we measure result and the output is our answer okay so basic computing paradigm you input register with superposed values you do a bunch of computing on it such that the probabilities are kept and you measure okay and the way it looks is that you take uh let's say you put an input with all possible combinations of the input input of the inputs being equal values all possible probabilities it looks like you're doing computation on all possible values at once but then when you measure you pick up exactly one and that's the answer you get okay and uh if you don't do anything very interesting here this is going to look like you randomly picked some input and computed on it so basically what we're talking about here looks like a random computation like you get in cs70 or 170 where you randomly pick an input you compute on it you look at the result so that's not very interesting right because we already know how to do that what we would like is we'd like it to be such that if you take this input state and you put an input that's a complex combination of possible inputs you run it through a quantum state a quantum computer and you measure the output is with high probability some answer that was hard to find that's what we would like okay and so if you look here um you know if the two n inputs are equally probable there could be two to the n outputs that are equally probable and what we'd like is the probability of the outputs to be piled up high on the answer we want and it turns out that something like fourier transform does the trick okay so if we can do a fourier transform on some input we can actually get an interesting output so if you bear with me i'm going to show you shores factoring in one slide so this is something that would break rsa okay we can basically say the difficulty of factoring rsa this is the type of cryptography that you might use with your bank across the internet is figuring out how to take a large number which is publicly known and factor it into two large factors that are primes and if you can do that you break the cryptography so classically this is an exponential time algorithm and so as long as these are big enough nobody's going to break it quantum computer can do it polynomial time and let me show you how here's how it is in a nutshell you pick a random x between 0 and n that's easy you say if the gcd the greatest common divisor between x and n is not 1 you just found a factor you win let's assume you didn't do that we find the smallest integer r such that x raised to the r is is congruent to one mod n okay so that uh you know basically is doing modulo multiply that's really hard to do well and easy if r is odd we got to repeat if r is even then we can say well i know because x to the r is equivalent to one mod n i know that x to the r over 2 mod n is equal to a and so then i can find this a minus 1 times a plus 1 is a factor of n and we have another failure mode here where a is equal to n minus 1 but if it isn't gcd of a plus or minus 1 n is a non-trivial factor so if we could somehow figure this out what r makes this equiv equation satisfied and we could do that quickly then um we win and that's something that uh you can't do easily classically but with a quantum computer what we can do and unfortunately i guess i don't have time to do this because we're running out of time but i can set up a situation where my input to my algorithm is all the possible k's uh if i take a bunch of values and i compute uh the the value x to that value and i add them all together as a superposition and i do a fourier transform what i'll find is that x to the r congruent to one as i have r go through all its possible values is going to be a periodic function why because if x to the r is equivalent to one then x to the two r is equivalent to the one x to the three r's equivalent to one and so i can do um i can essentially do a fourier transform in uh in a quantum computer i can get these peaks and that fourier transform will tell me what the frequencies are and that will give me that value that i need which i can do this i have to repeat this a polynomial number of times and then voila i've just factored that number okay so that's the essence of the shortest factoring algorithm and it all hinges on the fact that i can come up with this superposition state where it's all possible values of x to the k where k varies from 0 to n okay and i put them all together in a superposition state i do a fourier transform i get the result now the interesting question is is this something to worry about the answer is well so far no but it's looking like um it's getting closer and closer okay and so i would say there's been a lot of very interest interesting effort in quantum computing in the last five years enough that i did a lot of research on quantum computers um in in the early 2000s and and also the 20 up to 2010 2011. i think it's looking more promising now one of the things that we did do and we don't have time to talk about this but we actually investigated if you were to build uh that factoring algorithm and you could do it as quantum circuits that could run on a quantum computer what would that look like and we actually investigated ways of optimizing that and we could actually look at performance of different options for the shortest factoring algorithm as quantum circuits and so we built a cad tool to do that so um i i don't know i think it's a pretty interesting area right now and there's a lot of interest in it all right so um sorry i kept you guys way over but this is the last lecture i figured if anybody was interested we talked about key value stores we talked about chord um hopefully i gave you an idea about chord because chord is the root from which pretty much all the interesting peer-to-peer algorithms come and it's used in a lot of areas right now we talked about uh briefly went through some cryptography and then i talked about how data capsules are all about the data and that's a new model where the data can flow to the edge and in the cloud and back and um i think it's it's pretty exciting project we got working on it if anybody's interested in that and then we told you a little bit about quantum computing and uh feel free to come ask me or also look at 151 or 191 excuse me um which is an interesting class on quantum computing all right well thank you everybody sorry for going way over today thank you for those of you that stuck around and uh i hope you have a good uh finalizing of project three and those of you listening in cyberspace later as well you are all great and so i'm gonna miss you guys and i hope you have a wonderful holiday have a good rest of your semester and i hope you don't have too many finals in a week bye now