Computers keep changing the world, but their power and safety is limited by their rigid design. The T2-Tile project works for bigger and safer computing using living systems principles. Follow our progress here on T Tuesday Updates. This is the 36th T Tuesday Update. Let's get into it. There are four more weeks to the Episode 40 deadline when we're going to have a ring lotus, a hundred and thirty-three of these T2-Tiles mounted up on a wall or on a frame or something, ready to be benchmarked to find out the first world record average event rate of an indefinitely scalable computer. We'll see what happens. We're going to get there. Last week, we were focusing on the physical frames, how to hold the tiles together so that we can mount them as a group and slap them around as a group. If you do more work on that, that's going to have to wait for next week or a little bit beyond. This past week, what it's been about is MFM-T2. Taking what had been the code base for the simulator to demonstrate how the T2-Tiles might work, well, how any of these tiles might work, and instead fork off a copy of it that's not going to be the simulator, but it's going to be the actual engine running events on the T2-Tiles as part of an indefinitely scalable computer. Today, I came across a sort of a fun story about how programming can work and how if you take non-determinism into consideration, or not even if you take space into consideration and locality, and all these things that we've been talking about being good, that on the one hand it seems to make programming much more difficult, but here's a case where I just observed where it actually made something work better kind of for free, and that's the goal, that if we respect natural physical space, if we try to align our computations with the real, then we'll start getting payoffs that we didn't even expect, and that's the flip side to robustness, and instead of thinking that all the robustness has to be engineered in, if instead we make it so that we follow the contours of the land, we have our computation follow the physical space that it is embedded within, we'll start to get these benefits automatically. And in the coming week, what I want to do is get the MFM-T2 code base communicating with copies of itself on adjacent tiles. That doesn't mean it's doing the full cash exchange protocol, there's a lot more work to that, but right now, the way the underlying packet exchange code is written, only one user level program can be talking packets at a time, and at the moment that's the common data manager, so the MFM-T2 can't actually get in to send packets. So what has to happen in the coming week is that the underlying kernel module will be rewritten, so that it accepts multiple user clients from user space at once, and they can inject packets in their own order, and it'll all get sorted out and sent, and then in particular, somehow they'll get, the DMUX, they'll get sent on the receiving tile, they'll get sent to the common data manager, or MFM-T2 or something, all of that's going to happen this week. Okay, let's get to the news for Zedling67, who wants to see us, let's do the news. Okay, the top stories for this T-Tuesday update, the board assembly is complete. This goes back a long way. At first, we got a shipment of 60 boards, this is the picture of it, we pulled boards out of this to make our Lotus that we tested. Following that, there was another 120 that were available, we went and got them, plus one that had had a problem, got reworked and so forth. So this past week, then we got the last 19 units, so that's 60 plus 121 plus 19, that's full 200 stuffed boards that we don't actually have quite enough Beaglebone greens and LCDs to assemble these all into tiles. We'll either get some more of both of those or we'll just build however many that we've got for now and save the rest of the boards for repairs and replacements and so forth, we don't know. Oops, but there it is, the last 19 boards have been picked up and, I don't know, yeah, there. We also got back the spare parts that we had sent over that were more than, they didn't need to use quite all that we gave them. So that is the end of, I mean, that's a real landmark, that's something that's a very long thing going.  I'm really happy I picked ETS and worked with Robert Evans and the folks that we've met. It's been great and it certainly helped my education to understand how all this stuff works as well as to understand the business relationships that get these things done. I mean, it's all just a matter of this guy's got a machine who can do this thing at certain speed, at certain price that nobody else could do if you didn't have that machine and so on. And I didn't have the machine, Robert Evans did. So that's great. In other news, we still have more parts that we need. In particular, we have the intertile connectors. We have the intertile connectors that, and they're all plugged in at the moment, that are doing the DPs, the data plus power that are used within a ring, but we have a different kind of circuit board that's going to get assembled into a similar little board, a similar little connector called the DO, the data only, that will be used between the power zones so that they can still talk to each other, but they won't actually share power. So this is a saga that's been going on for quite some time that I haven't really said much about, but I need to talk about it today. So I put in an order with PCBWay to make 165 of the data only connectors, plus finishing up the rest of the DPs that there wasn't enough stock for to do it to begin with. That order shipped a week ago Sunday, June 2nd. It was supposed to arrive on Tuesday. It was supposed to arrive a week ago, this Tuesday, T Tuesday update. That didn't happen. In fact, what happened was it got to Shenzhen. It really didn't get anywhere and there was a clearance event. Something stopped it. I haven't seen a clearance event before, didn't know what it was. Googling was suggesting that it was probably you needed to pay some tax or there was something going on. For the clearance process, additional details required for clearance. So I thought, did I have to get involved in this and tell them what it was for? And some people were saying you'd have to give up a tax ID and all this stuff. I don't know. So I didn't worry about it for a couple of days. I thought maybe it would come loose. Well, you know it right. So I signed up for shipping notifications and I just get getting every day Tuesday, Wednesday, Thursday. I was just getting clearance delay clearance event and so forth. Finally, I called up DHL. I said, you know, what's going on? And they said you need to talk to the shipper while it's still in the shipping country. You need to talk to the shipper about what the problem is. So I sent mail to Yolanda my contact at PCB way telling me I need to contact the shipper. This seems to be stuck in Shenzhen. Can you help me with this? And of course, if you've been a longtime T Tuesday update watcher, you know the next plot development that it's going to be. I hear back, oh yes. Well, but there's a festival. There's some other Chinese holiday that, you know, of course every country's got our holidays. We got our holidays. I never heard of any of these and they all seem to hit whenever I'm trying to make something happen. So it turns out that Dragon Boat Festival is specifically last Friday and I was getting in touch with them on Thursday. So, but over the weekend, it apparently started moving. It somehow disappeared from Shenzhen and showed up in Hong Kong and the custom status was updated. And great. So now we're moving and right. So we're in Hong Kong. It's been given a release. It goes on. Yolanda tells me, please check. I did check and it's processed for clearance in LA. It's reached America, the United States of America now. Great. But immediately after I checked it, when I checked it again, no such luck. Now it's a clearance event in Los Angeles. So what is this? I dialed into DHL again earlier tonight to see what was going on. And it told me there was no problem. It was processed. It had been cleared. So I went back and I checked it again. And sure enough, the clearance event was cleared and now it was processed for clearance. And that was great. But every time I reloaded this, it seemed it was changing from being processed to being cleared from being cleared to being processed. So I put a clock up just so I could tell. And I, you know, all right, back in a clearance event, now it's waiting. Now it's cleared, ready to go. Now it's in a clearance event. I mean, it's as if the fact that these are all happening at 2226, like the sorting is coming out random and it's telling one thing another. I don't know. But that's where it is right now. You know, it all by rights. It should be here today. I assume I'm going to have to call them up again and we're going to see whether I'm actually going to have to pay some kind of tariff, you know, because the Chinese are getting really hammered by this or I don't know. Back and forth. That's it. In other news, scientists report, given that we're going to have this gigantic field of tiles that are going to extend arbitrary distances in every direction up and down, left and right. How are we going to replace a tile that fails? Well, the whole idea was that we need to be able to remove a tile from one side without having to go all the way around and come up the other side to loosen something up. And we've been designing stuff. We talked about it last week. Well, and so here's what we did. Scientists have said, well, couldn't we make some kind of little prongs that would fit over the thing that would let us get in there and pull it out nice and cleanly. So I gave it a try. And here's how it works. So here's a tile. Here's a tile. Here's the thing. You put it on. Bam. It latches on and you just pull it right out. It's not a genius. Or, well, maybe not. You know, when the science meets the real world, here's a slightly bigger example. Here are three tiles that have been ganged up with. So I've removed the intertile connectors here because that's what you would do to pull the thing out. But you'd still have the framework holding it from the back. And of course, doesn't fit at all. Can't get it in. And it's not even close. There are other versions of this that actually did fit through. I mean, they'd be fitting through from this side, from this side. But the problem is the gap between the boards down at the bottom. And anything that I can get that goes through that gap does not latch on hard enough to actually pull. So once again, what looks like a breakthrough in the lab, not necessarily a breakthrough in the real world. So we'll see. And that's it for the news. All right. Yes. So in the code, what happened this past week, I forked, took a copy of the repository, just made a whole nother copy and changed its name. Well, that's not true. I didn't do the whole repository. I made a copy of the driver that ran MFMS, the movable Feast Machine Simulator, made a new driver called movable Feast Machine T2, MFM T2, that this is running over here on the grid if we've got it going. And if you're a long time watcher and you see that this is the statistics display here, it's changed again. In fact, this in this week also the statistics display has been completely rewritten in C++ and not in Pearl. That was primarily because the Pearl code that a Pearl package that I was using to do the graphics display on this, I wasn't very happy with. I mean, it was amazing for what it did. But it was still, you know, sort of very low level and there was a lot of stuff that would have to have been built up on top of it. And I already had that built up in this separate library called the Simple Direct Library or something like that, SDL, which the simulator has been using all along. And there's a lot of structure that's been built up. So this is now running a program called T2Viz. And once again, still there it is. This is MFM T2 running in the background. Well, now running in the foreground. And it looks a little bit different. I've cleaned this stuff up. I've reset this, all these things going around, which I can do because this is custom for the T2 tiles. And actually, and this thing right here, I don't know if you can see it, this 20.32, so we got a bunch of information here. We've got the grid voltage, the temperatures, the amount of light that we've got coming in here, the 720 megahertz, the speed of the processor, 18.1 age. This thing has the uptime of 18.1 hours and 20.03a. That's the average event rate of the MFM T2 happening in the background. Whoops, there he is, happening back here.  Dave has been saying he'd be happy if there was one air, if there was epsilon air, but this is 20 air. Why isn't he thrilled? Well, because we're going to lose a ton of that. We're going to divide by 10 immediately once we start having to actually communicate and coordinate between tiles. I have no idea how much of that 20 air when it's running independently will be left once we get all the coordination going on. So that doesn't mean anything at the moment. But what it does mean is that the fact that we have MFM T2, that we can customize it to our own purpose and not worry about things happening with the simulator, means we can make closer couplings between things like T2Viz and MFM T2 so that we can be displaying information about the engine in the display. So now, let's see if we have time to do this. This tile here is turned off. What I want to do is start a new bit of code coming out here. Let's go over here. And I'm going to remake this one particular MFZ that is a few hundred k bytes when it goes. It takes a few minutes to spread around from one tile to the next. But hopefully we can get it. All right, so CMD T2. We'll copy it to CDM Common. We'll overwrite the thing. And so now, once again, CDM should notice that the modification time on that particular file has changed. Load it up, reparse it, discover that it's new, and so forth. Install it itself on the Keymaster. That's this white tile here. And then announce it to the neighbors and start shipping it out. Now, at the moment it looks like, in fact, there it is. It's going. All right, so this is step one. It's now being pushed out. So it didn't work over here because the logs rotated. We lost our tail. All right, there it is. So now we're shipping it out to the northwest, to the northeast, the east, and the southwest, but not to this guy. So let's start booting up this guy. And what I'm trying to do here is to get the data that's getting pushed out to the tiles to have somebody who's fallen behind. And so we'll see what happens. Is this thing booting? It probably is. What's going on up here? Now, one of the things that I have learned this weekend is that, especially with 200 tiles, there's going to be hardware issues. And in particular, I've had cases where if I tighten the screws down on the case too tight, I don't know what's going on with this guy. I'm doing another chance and then we'll try to reboot.  It's just he's not listening one way or the other here. But okay, we'll believe that the key master is still actually sending this stuff. So this guy is going to come up and hopefully pretty soon, he'll start drawing from, he'll pick up the announcement of the new version of CDM DT2 and he will start downloading it as well. And I can see that we're not going to have really not going to have enough time to get to the end of this almost surely. So I'm just going to tell you what the observation I made was that I was quite pleased with. So you can get the idea and then we'll see if we actually get it before time runs out. So what I saw was, let's get this guy over to show the display. He's still booting up the content, common data manager so he hasn't started pulling it yet. But what happened was, was that the key master is where I'm always doing this stuff. So he's pumping it out to everybody. And what happened is, is that like this guy, all right, so now it's complete. Oh, all right. Well, so unfortunately it's not going to work as this guy is, he's completely done. So what happened in the particular case I observed was, the key master was feeding it out in five directions. And one of the directions happened to finish and it installed it and was getting ready to redistribute it to others. And one of the other tiles that was still in the middle of getting this stuff, heard the announcement from the guy that just had it and he sent a request to him too because the way the common data manager works is these announcements get sent out when you see there's a new thing and everybody checks saying, oh, do I need that? And the other tile discovered, oh yeah, actually I'm halfway through that. I currently need whatever, some particular offset in the file. And it sent the request off to the second guy and got a reply back before the key master was able to even give a reply to that same one as well. And what happened was, was that this guy switched from pulling from the key master, which was heavily loaded and therefore was responding slower to this guy who was responding quicker because he had nobody else to feed it to. So what it looked like happened, and I'm not 100% sure of this, but what it looked like was happening was that we had an automatic load balancing taking place just because the guy that was less heavily loaded won the race to reply to the, do you have this particular piece of the file so that when the other guy came in saying, yes I have this piece of the file as well, the guy who was pulling for it didn't need it. So he didn't ask the key master for the next piece and the next piece and the next piece and he automatically switched to feeding from a less loaded machine. Now that was pretty cool. We're out of time. So what did we skip? Oh well, so that was the story about racing. We already did it. Four weeks from today. Ring, let us run on the wall. Benchmark ready. It's going to be great. I will see you in another week. Have a good week.


Hello everyone, I'm Weiqiang, and in this talk, I'm going to present a faster enumeration-based lattice reduction, which can be used to reach a low-time effector k to the 1 or 2k in time k to the k over a plus a small order of k. This is a draw-all with Martin Albrecht, Shibai, PLM Fugler, Pocke-Snatt, and Demonstrate. In more details, we give a new enumeration-based lattice reduction, and compared to the Pyro ones of the same type, we can reach the same quality while with a smaller-time complexity than before. And when the input lattice has a large enough dimension, we can prove this improvement under a heuristic assumption. And when the dimension is small, we can still sort in our estimation that this improvement still works for varying algorithm. I will give more details about this later. And to continue, I will need to first introduce some necessary background about this lattice. So lattice is a set of regularly distributed points, as you can see the blue points here, which can be generated with a set of linearly independent vectors like B1 and B2 here. And this is also known as a basis of the lattice, and the same lattice can have arbitrarily main difference basis, like C1, C2 here, from another basis for the same lattice. And there are also two important invariance in lattices like the first minimama, which is used to denote the norm of the 390 vector in the lattice, and also the volume of the lattice, which can become 50 as the determinant of any one basis of the lattice. One of the most interesting and important problems defined in lattices is known as the shortest vector problem. So we are given a basis of the lattice, and you are asked to find a saw vector with norm equal to the first minimama of the lattice. And in this one, we consider a variant of this problem, which is called approximate Hermit SVP. So again, you are given a basis, but now you are asked to find a saw vector with norm upper bound by the normalized volume of the lattice up to some vector gamma. And by Minkowski upper bound, we know that the first minimama can be upper bound by the normalized volume of the lattice up to a vector square root n. So whenever you have size n SVP saw, correspondingly, you have same size approximate Hermit SVP saw with approximation vector square root n. And to solve this problem, the best known solution is to reduce the given basis to obtain a good one. And to quantify the quality of the basis, one can use the so-called Hermit factor, which can be computed as the norm of the shortest basis vector, normally the first one, divided by the normalized volume of the lattice. And once you can reduce the basis between a smaller Hermit factor, then you can use it to solve the approximate Hermit SVP problem with a smaller approximation factor. In practice, the best known algorithm for reducing the basis is known as the BKZ lattice reduction. And to quantify how good a lattice reduction algorithm is, one can use the so-called root Hermit factor. It is a normalized version of the Hermit factor normalized by the dimension of the lattice. And this also introduced a quantity which is independent from the dimension of the lattice. And if you are further interested in the concrete effect of a lattice reduction, you can further look into the grand-smith orthogonalization of the basis. So intuitively, lattice reduction helps to reduce the basis, such that for the resisting basis, it has the grand-smith vectors like B1 star and B2 star here, with norms closer to each other than before, so then the norms of C1 star and C2 star. And next, I'll write to first recall the BKZ lattice reduction algorithm, and then see how it differs from our new algorithm. And to continue, I'll need to introduce another notation called orthogonal projection. So here, for example, I will use B3 to D2 to denote B3 after removing the projection over the space span by the first two basis vectors. So now here comes the BKZ algorithm. The input in Kruller basis B denoted from B1 to BNR, and also cos prime dot K denoting how strong the lattice reduction is going to be. And the BKZ algorithm starts by running an SVP over the first block from B1 to BK, and then use the found solids vector in the first block to update the first basis vector and then move to the second block. And again, use the found solids vector in the second block to update the second basis vector and then move to the next block and so on and so forth by saying the second block, I mean the second block after removing the projection over the first basis vector. So the BKZ algorithm run SVP from first block to the last block and also repeat this process of suffixion to remain in time until for each block, the first vector reach the first minima of the corresponding block. And to evaluate the cost of the BKZ algorithm, one can instead look at the cost of the underlying SVP solver, which is the most costly step inside BKZ. And the two most practical SVP solver families are implemented by sieve and enumeration respectively, and the ones implemented by sieve take an exponentially larger space, while for enumeration it's just a small polynomial space. But for enumeration, the running time is super exponential, while for sieve it's just an exponential, even though the dominating constant as you can see here for enumeration is smaller than the one for sieve, but the locate factor will anyway eliminate this one teacher, once case is large enough. And in this world we focus on enumeration based SVP solver, so we are in the region of using a small polynomial spacer, but super exponentially larger running time. And in our simulation, we always refer to the Yidrin Pooning by Gamma and Guyan and Regate 2010 for an efficient implementation of the enumeration. And for comparison between our results and the prior ones including like BKZ or SDBKZ. So SDBKZ is a variant of BKZ, you can very roughly like to run BKZ not only over the given basis, but also over the dual basis of the given basis. So for BKZ or SDBKZ relying on the enumeration-based SVP solver, to reach a quality like Luham factor equal to K to Rihwan or 2K, the time complexity is dominated by the underlying SVP solver, which is given as K to the K over 2E plus a small over K, as mentioned before. And in this work for reaching the same quality, so the same Luham factor, we achieve a smaller time complexity, which is K to the K over 8 plus a small over K. Before I go into more details of our new solution, I write to first review both quality and time complexity in more detail about the prior ones and then step by step to see how our new algorithm differs from the prior ones. First, let's review the quality of the prior ones. So here suppose this is the grand-smick log norm of the reduced basis after running SDBKZ with the size K's SVP solver. In this case, this quantity.i denoting the proportion between two successive grand-smick norms is well studied by the paper of Missensio and Water in 2016, which tells that this quantity, data i, is fixed for different index i outside this last block, so it introduces a straight line here outside the last block. And in this case, I will also call this data i as the slope of this line. And in this work, we consider a slightly different variant of this result. So we replace the underlying SVP solver with the same size, but approximate Hermit SVP solver. Again, if you want SDBKZ with the approximate Hermit SVP solver and again with size K, then you will again obtain a straight line here outside the last block. And we also know the slope of this of this line in this case is equal to the square of the root time effector achieved by the given approximate Hermit SVP solver. But this is not the case for BKZ. So for BKZ, this quantity, data i, is not fixed for a different index i, so it does not give a line. And we refer the audience to the appendix of our paper in ePrint for more details for the case of BKZ. And also because of this good property achieved by SDBKZ, we choose it as a slope routine in our new algorithm for reaching our new result. But it does not mean that it is impossible to use BKZ for reaching the same result as what we can reach using SDBKZ here. And we leave it as a future work. And next let's move to the cost. So let's focus on the last block. To ensure the first place of the last block reached the first minimum of this block, one need to run an integration over this full block. And this is known to be realized by the Kanan's algorithm. So one need to first reduce this block so that, except for the first place, each place from second place to the end reach the first minimum of the corresponding block from this place to the end. And the last step is full-immersional over this full block. And the time complexity is well analyzed by our host delay in 2017. It's given as k2k over 2e plus a small order of k. And this is also known as the worst-case immigration cost over size-case lattice. But this worst-case cost is not the case for each block. For example, for the first block, over a straight line, the immigration cost is only k2k over 8 plus a small order of k. And this difference also introduced a conjecture for a long time that it seems possible to achieve the same quality, like the one achieved by SDBKZ, but with reduced overall time complexity, like k2k over 8 instead of k2k over 2e. And in this way, we give a positive answer to this conjecture. And before I continue, I'd like to make one more remark over this last block. So in the following, I will always assume for this last block, each place reach the first minimum of the corresponding block from this place to the end. And this corresponds to the so-called HKZ reduced basis. So this is why also why I will also call the corresponding block here, the curve here as the HKZ curve. And there are two remarks. First, this is not promised by the SDBKZ reduction. And second, this additional assumption also does not introduce a larger overall time complexity. So now let's move to our solution. So how can we do better? So we know that the main obstacle is from the immigration cost over this last block of size k, which take k2k over 2e. So instead of run SDBKZ with the size ks SVP solar, now we train to run the SDBKZ with the reduced size SVP solar. So that the immigration cost over this reduced size is well controlled reading this aesthetic cost. But this also introduce a straight line outside the last block with a larger slope such that for the first basis vector node, it has a larger norm than before. So it achieves a worse home effect and look home effect. So we have to continue to reduce this basis such that for the resisting the first basis vector, we achieve the same norm as before. So achieve the same home effect and look home effect. So this is our target. In more details as we promised, now we train to run SDBKZ with the reduced size SVP solar. And here I'm going to denote the reduced size by k0. So equal k times 2e over 8 approximately equal to 0.67 times k such that the worst case immigration cost over this reduced size can well control reading this aesthetic cost. And as you can see here, and also you will see in the following, different block size like k0 will get involved in our new algorithm. And k here we only serve as a cost parameter instead of a block size. And again by Minkowski-Uppermount, we know that k0 dimensional SVP solar implies the same size approximate Hemi-SVP solar with approximation factor square root k0. And this implies actually for a k0 dimensional attest, we can already reach a home effect square root k0 and also the corresponding root home effect here. And together with the relation between k0 and k, we can derive our starting root home effector, so k to the power of 1.36 times k. And this is for sure much larger than our targeting root home effector. So now we already have a starting approximate Hemi-SVP solar with reaching this starting root home effector in time k to the power of 8. And next we aim to construct from this starting one, construct a new one, approximate Hemi-SVP solar with a new approximation factor over a new dimensional, still in time k to the power of 8, while reaching a smaller root home effector. If we can achieve this, then we can repeat such processes sufficiently many times until we reach this target root home effector. So this is the general idea of our new algorithm. And in the following slide, I'm going to detail the first step. So here for example, I'm going to take k equal 1000. So we can start with the SVP over a reduced size around 670. And we can track the worst case immigration cost over this reduced size, as we are reading this is a expected cost. And also make a note on the starting root home effector. Now here comes the first step. We are going to fit the sdbkz oracle with our starting approximate Hemi-SVP solar. And this helps to reduce a basis of larger dimensional. And for the corresponding grand-smick log norm, it has one straight light outside the last block with slope equal to the square of the root home effector achieved by the given approximate Hemi-SVP solar. And knowing the slope and also the restriction of the immigration over this regional, we can note the largest size that we can iterate over this straight line over this green region. And together with the starting dimension k0, we can know the next dimension k1. And again by Minkowski upper bound, we can know the upper bound of the norm of the solution returned by the immigration over this straight line. And together with the waller of the whole it is, we can compute the new home effector and the new root home effector. And as you can see here, it's getting smaller. And again with this new approximate Hemi-SVP solar, reaching a smaller root home effector, we can feed it to the SDB KJ oracle. And this can help to reduce a basis of even larger dimensional. And for the corresponding grand-smick log norm, you can see a new segment of lighter with the even smaller slope. And this even smaller slope can help to introduce an even smaller root home effector. And once you can repeat this process sufficiently many times, then we can eventually approach our targeting a root home effector. So this is our general idea in more details. And next, I would like to first give an intuition about the overall cost of our new algorithm. So here first we know the immigration cost at each iteration is well bounded by k2k over 8 as we decide. And once we only need to run a logarithmic number iteration for approaching our target root home effector, then the overall time complexity will be k2k over 8 plus a small order of k. And actually we can prove this is indeed the case. And next, if we look closer into the grand-smick log norm of the reduced basis by our new algorithm, we can see there are different segments of lighter with the different slope here. And this is different from the one generated by SDKZ, which only get one straight line with one global slope. And together with the picture below, so as the algorithm procedure you can see the slope is getting smaller and smaller. Actually this matches our intuition about the reduction, that is reduction, which helps to reduce the basis such that the grand-smick norms are getting closer and closer to each other. That's why the proportion between two successive grand-smick norms is getting smaller and smaller. And as the algorithm procedure will eventually reach one segment of line with slope approaching the one generated by SDKZ. And this slope also helps to reach the root home effector, the expected root home effector. And last I would like to make one more remark about the root home effector after 10 times our iteration. So 10 here equal to the logarithm of the cos lambda k k equal to 1000. So after the logarithmic number of iteration, the root home effector already converges very well. So this matches our intuition that we only need the logarithmic number of iteration for approaching our targeting root home effector. And next I would like to give the full description of our new algorithm, which we call fast-in-nume algorithm aimed to conjure an approximate Hermit-SVP solver with approximation factor gamma i. i is the number of iteration level. Other input include cos parameter k and also basis b. So once if you are in the first iteration or you just run the worst-case iteration over this reduced size, we cost within this expected cost. And if you are not in the first iteration, then process with SDKZ with the approximate Hermit-SVP solver from last iteration, and then run an iteration over this region corresponding to the first segment of line. And for the analysis, we need a heuristic assumption which needs to assume that each gamma approximate Hermit-SVP solver between an answer with normal is exactly equal to the normalised one of the corresponding block after effector gamma and not smaller. And formally indeed we can prove that the omega-1 iteration will be sufficient for approaching the expected root home effector up to effect 1 plus the smaller one in the small nana in time k to the k of a plus a smaller of k times some polynomial other besides an input basis b. And if you still remember for each iteration, we need to work over a lattice of the dimension roughly size k larger than before. So with omega-1 iteration, that's why we need the overall dimension to be roughly like omega-1 effector larger than k. But this is not satisfiable for an assist for cryptosystem like this candidate, where we require the dimension n to be relatively close to k, like an over k is constant. So instead to run an iteration over this 100% lighter, we propose a new practical variant where the inpatient journal also covered the HKG journal. So for the practical variant, now we inmate also over the combinational of the straight line and path of the HKG curve. So now the question becomes how can we distribute the proportion for the straight line and the proportion for the HKG curve? To answer this question, we try to inmate the costa for different distribution. So for example when c equals 0, it means to inmate over the HKG curve, so this is the worst case costa. So when c equals 1, it corresponds to inmate over this 100% lighter. And as you can see here, when c equals 0.25, we reach the lowest costa, that's why we choose this value for our practical variant. And the second issue is about the terrain block. So for each middle block, you can always be possessed to have this straight line plus HKG curve and then you can inmate over this this pre-sumed strapper. So 25% or straight line and rest the HKG curve to reach the lowest costa. But for the terrain block, you can no more inmate over this pre-sumed strapper. So the inmate cost can be much larger than the expected costa in this case. So we have to reduce the size of this block. And this will certainly introduce the worst quality for this local block. But in the simulation later, as we will see, this modification will not affect the global quality a lot. And these two modifications together introduce our practical variant in the simulation. And we can see the similarity costa of the practical variant fits the 1 over A curve very well. And also you can see there's a desalite even below this 1 over A curve. And this desalite corresponds to the last step iteration cost without considering any pre-processing costa. And it will give more discussion about this later. And in the picture below, you can see the quality. So the root home factor achieved by the practical variant is at least as good as the one achieved by the standard BKZ. To conclude, for reaching the same root home factor, we achieved a smaller time complexity, k to the k o A plus a small dot k, instead of the o 1. And considering the counter-acceleration, we can get a further effect of two improvements. And this improvement is supported by a different evidence for different regional parameters. So when the dimension is large enough, like in our case omega 1, we can prove this improvement under a heuristic assumption. But when the dimension is small, like in our case constant 2, this improvement is supported by our simulation analysis of the practical variant. For visual works, so first it will be interesting to remove the heuristic assumption that used in our analysis. We know that it is possible to follow the works of on-hospitalate 2007 plus either on-hospital study 11 or newer 17. So in their works they managed to remove the heuristic assumption in the analysis of time complexity for BKZ. And second, it will be interesting to see an extension of our works to other lattice reduction algorithm, like to BKZ or slide reduction. For BKZ, as we already mentioned, it does not introduce a straight line outside the last block. So it will introduce an additional complication for the analysis. And it will be more interesting for slide reduction. So the expectation is that reaching the same improvement for the time complexity, so from K2K2E to K2K8, while maintaining the same quality is the one achieved by slide reduction. And further, without preprocessing cost, the last step inration cost can be even below K2K8, so it seems possible to do some trade-off between the preprocessing cost and the last step inration cost so that the overall cost can be below K2K8 while maintaining the same quality as we can achieve for now. Or in other words, using the same cost here while approaching even better quality. And last is about the cryptography relevance of this work. So in this way, we already have some tries for this small nvok region, which corresponds to the KMN assist for cryptosystem like the next candidate. But in our works, we only have a simulation result with our former NNCESA, so it will be very interesting to see a former NNCESA to confirm that we indeed have this improvement from K2K2E to K2K8 for this small nvok regional. And after that, it will be interesting to continue to see the concrete, the new concrete cross-over point between our new algorithm and the state-based voltage reduction like the joystick-based voltage reduction for concrete cryptography parameter in both classical and content setting. And this completes my talk and thank you for your attention.


Welcome back everyone. Today I'm going to show you how to add a known good hash database to autopsy. So I'm currently running autopsy in Windows. It's autopsy 420. This is the latest version of the time of this video. So once you open up autopsy and you don't have to have processed a case or anything, just open up autopsy and go to tools and then options and then you'll probably start on this autopsy page. So go over to the tab that says hash databases and you notice that autopsy by default does not ship with a hash database. We are going to be including the NSRL list from NIST. Basically the NSRL is kind of known good hashes that we can more or less safely ignore. So we're going to be adding the NSRL hash database, but I also use this quite often to create my own hash database of interesting or just known bad files. So sometimes known bad. If we were working on child exploitation cases or maybe malware investigations, we might have hashes of known bad files. Child exploitation, it's usually images, videos, things like that. And hashes are a very fast way to do filtering in your cases. So they're really powerful, pretty easy to manage and do once you get used to it. But for some reason, a lot of people don't really use hash databases very much. So yeah, I strongly recommend using them. They're a very useful tool to help us. So from the options menu, let me go back. So tools, options from the options menu, you click on hash databases and I've already downloaded the NSRL database. Right now it's three gigabytes. It's a very large database. I'll go find it here, NSRL. So we have this NSRL. Basically it's all the information related to NSRL and I've already verified it. I've already extracted the database. The database file is actually here NSRL file dot txt. Let me open up, let's say. So if we do NSRL head, you can see the structure of it is basically first a SHA1 hash, then an MD5 hash, then a CRC32. Then the file name of the file that was hashed and then the file size. The product code, which we would need to look up what the product actually is if we were interested in that. The operating system code and the special code, which there's no special code, at least in the head version. So we would need to look up exactly what op system code relates to and product code relates to. But file size, file name, CRC32, MD5 and SHA1 I think are all pretty self-explanatory. What we're really interested in here are these. So the SHA1 hash and the MD5 hash. So that's what it looks like. So in Windows here, I have this NSRL file. It is, I think, about 13 gigabytes whenever it's unpacked. So it is quite large. That's just hash values. So it's a lot of hashes. So that means it can filter out a lot of potentially uninteresting files. So in the hash databases tab, we could create a new database. But we won't do that now. New database, you might want to create if you want to potentially add things that you find with autopsy into the database. Make a new database so that way you can save them inside your new database. But I'm going to import the database. So I'm going to click on import database. And the first thing it asks for is database path. So I'm going to open it up. It's for me inside my eDrive NSRL file txt. Hash set name, I'm just going to call it NSRL. And then type of database known, NSRL or other. So NSRL is so popular, they even just refer to it as NSRL. If this was a list of, let's say, known child exploitation images or something like that, we would click on known bad. But instead, it's a known file, kind of known good, or something we can filter out. So I'm going to click on known instead of known bad. Click OK. Now, you see that it added it and it's in red right now. So we have basically the option now to import or delete. We can delete it, but we don't want to. Now, what we haven't done yet is indexing. In a prior video, I showed you how to make an index from the command line. If you made an index from the command line, the index should be detected automatically. But we haven't indexed this yet, so we just need to click on index before we can use it. So we have to create an index before we can use this database. That's very important. So that's why it's currently showing up in red. So I'm going to let that index, it will take a while and then I'll come back whenever it's finished. Okay, so now that NSRL database, the index has been created, we can see the index path, the index has been created in the same directory and we can see that it's an MD5 index. So the default sleuthkit indexing is the MD5 value. And then we have the index status indexed. We can re-index it. Yeah, we could re-index it, but yeah, we just index it so we don't need to. So sometimes, well, especially if you add new hashes to the database, you'll need to re-index it again. But yeah, right now we don't need to. Okay, so you can just click apply. If you select the database again, then we can't, here we have add hashes to database. This is grayed out. And I think it's because of the type of database. So if we create a new database, for example, we just say test database path. We can say hash databases, test.kdb, save. And then let's say that they're known bad. Okay, so then you click OK. And because we've created a new test database and it's KDB type, whereas NSRL is just .txt type. KDB, we can add hashes to the database. So if we had basically a list of hashes. So for example, if I had, let me go back. Imagine that I have these hashes in a file. So let's just do that. Head, NSRL, awk, awk is used to basically filter out commands in Linux. Or filter out text in Linux. We can print. We want to print, let's say two. $2. So this awk f basically says to make this the file delimiter and then print $2. So go find the second thing after the comma, which is the md5 hash value. So we can just print that out. But now that I look at it, I just realized that basically all of these are the same hash anyway. So I'm just going to copy one of them. Go back and then paste from clipboard, paste that hash in and then add hashes to database. One hash added successfully. Okay. So basically, there's a couple different ways I'm going to delete this database. There's a couple different ways we can create databases. There's a lot of hash databases that already exist that we want to import in. So for example, the NSRL, the known hash databases. There's also a lot of, let's say child exploitation hash databases or peer to peer file sharing hash databases or virus hash databases. So we could get those hash databases, import them, index them and then use them to automatically process our case. We can also keep our own hash databases locally. The problem with that is that no one else can say, let's say share our hash databases directly. What you might notice is, well, I don't know if you didn't notice or not, but whenever you click save as, I actually have these on a, it's a virtual box server, but basically this eDrive is a network share. So what you could potentially do is share this database on a network drive. I'm not sure how it would work with multiple users trying to access the database at the same time, but it's possible. Autopsy also has a multi-user mode and I'll be talking more about that later, how to set up multi-user mode. But anyway, we're talking about hash databases now and this is how you can set up some of them. So we've already added NSRL, we can apply, click OK. And then I've already processed this case, but now I want to basically rerun. The hash database was not included whenever I processed this disk. So I want to rerun the hash comparison module basically. So I can go to tools and run ingest modules, select the disk again, and then recent activity. Oh, I'm not sure if I'll be able to do this. So basically I'm just going to deselect everything, deselect all except hash type identification. Yeah, let's see if I can actually start this or not, I'm not sure if I can. Yeah, OK, so now it's basically ingesting again or it's running the ingest module again, just for hash databases. So I have deselected everything else. You can see that it's accessing not only the disk but also probably the hash database. So that's it for adding known good and known bad hashes to autopsy and then making the index and then rerunning any modules. Now whenever we start a new case in autopsy, if we select the hash data hash tests as an ingest module, it will automatically run. So that's it for hashing. Thank you very much. If you like this video, please subscribe for more.


Hello Columbia! The City of Columbia and our partner organizations want to make sure you and your kids are ready for summer activities this year. Once again, we are preparing our Youth Services Guide, which will help you select summer camps and activities for your children to enjoy throughout the city and parts of Richland County. If you are a local youth organization and would like your information included in this year's guide, please send us the following information to youthprograms at columbiasc.gov. The services or activities you are sponsoring will be highlighted in our Youth Services Guide so that families across the community can participate and learn more about your program. The deadline for submission is April 14th, so please get your information in so you don't miss out. Also, if you're interested in volunteering or would like to donate funds for any summer program, this guide will also help you determine which programs and activities best fit your interests. Thank you and let's get our youth positively activated this summer!


Hi and how are you all today? My name is Priyanka and the question says if the little surface area of a cylinder is 94.2 centimeter cube and its height is 5 centimeter then find the radius of its space and then its volume. We are also given that we need to use the value of pi as 3.14. Before proceeding on with the solution we should be well versed with the formula of lateral surface area of a cylinder and that is equal to is 2 pi r h that is the lateral surface of the curved surface area of a cylinder. So the knowledge of this formula is the key idea to this question. Now we are given that the lateral surface area is equal to 2 pi r h. The lateral surface area is given to us as 94.2 centimeter square. Right? So this implies 94.2 centimeter square is equal to 2 pi we do not know the value of r and the h is 5 centimeters. So this implies 94.2 into 7 the whole divided by 2 into 22 into 5 is equal to r after simplifying we have 3 centimeter as the radius of base. So this is the answer to the first part. Now we need to find out for the second part that is its volume that will be pi r square h 22 by 7 r square means 3 times 2 times 3 into h h is 5. So the answer comes out to be 141.3 centimeter cube. So for the first part the answer was 3 centimeter and for the second part it was 141.3 centimeter cube. So hope you understood it well and enjoyed it. Have a good day.


Ocrow and County has partnered with Bridges of Hope in an effort to create what they call a self-healing community. The self-healing community's project was started earlier this year and has the goal of bridging the gaps and connecting people to resources to improve health and social outcomes. Their aim is to reduce and ultimately prevent adverse childhood experiences or ACEs and work towards safer, healthier communities. What they found is if we do this on a community-wide level ACEs tend to drop simultaneously. Too often we just go after one slice of the pie. Let's go to child abuse or parental addiction but if we work as a community together all that tends to drop simultaneously so we're going after it all. The project is starting by focusing on the areas surrounding Garfield and Lowell Elementary schools in Brainerd. Bridges of Hope held a community conversation this evening at Lowell Elementary to gain insight from the public but what they think are the most important issues to focus on. Working together everyone's voice matters and that's what we're here to start tonight is the community conversation to hear from people living in our Lowell and Garfield neighborhoods to talk about what's going on and to build solutions together. Bridges of Hope plans to hold future community conversations and events to continue gaining insight on the self-healing community's project from the public. If you enjoyed this segment of Lakeland News please consider making a tax-deductible contribution to Lakeland PBS.


Thank you Carlos. Hi everyone, I'm Sabina. You're designing at the MOPIS team in the educational solutions department I am going to cover briefly the Uxs stages and progress of the course hierarchy project that the MOPIS could be working or Mostly implementing on the 4.4 radius. So if you go to the next slide, Adrian, please Yeah, so during this last month We've been able to continue with the design and the testing phase of this project and we've been conducting two phases of usability testing The first phase was conducted remotely through Uxsum And we were testing with seven model teachers and content creators and four non-model teachers And then finally with five non-model students Based on the first research findings We improved the prototypes and conducted the second testing phase during the global mode this year Where we talked to eight model community users who were mostly content creators and Educator support And you can have a read on the findings report of these two phases in these slide links at the end of the slide as you see here If you go to the next slide Adrian Yeah, thank you. So the key findings of the second research phase Were mainly positive and we found the majority of same points around the new functionalities that were added Specifically the option to add sections or subsections between already created content Or also the ability to open individual and isolated section and subsection phases The most of the key the rest of the key findings were very very positive And now we are in the after analyzing the results of the second research phase We are working on the high fidelity prototypes for the educators and the students users If you go to the next slide slide Adrian please Um, yeah, so uh in the right side you see um like a screenshot of how the prototype is looking in high fidelity right now And we are going to be working on these uh prototypes For this week that will be ready for ready for the new increment planning meetings. Um And yeah, I think in the next showcase will be showing a demo Of the functionalities, but for now this is what we have for the uh, uh updates. So that's that's it from me


Okay, thanks for the introduction. So my name is Winnie, I'm an open education ambassador at Spark and prior to this, I worked in an education nonprofit that served underserved students and connected them with post secondary opportunities. And before that I was the student body president at the University of Houston. Hi everyone, my name is Haley Bob. I also work at Spark's open education team as an open education coordinator. I'm based in Edmonton, Alberta, Canada, and I'm a former student union president at my university, the university blood bridge where I studied psychology. So we wanted to share a few facts before we jumped right into our presentation. The first is that the average cost of college has risen four times faster than the rate of inflation over the past 10 years. Another fact, 63% of students have actually skipped buying or renting a textbook yet 90% of students have worried that foregoing these materials would negatively impact their grade. Yeah, so I was the student body president at the University of Houston, as well as the director of the Texas Student Government Coalition, which spanned across 26 student governments in Texas. And one of the priorities for my administration was absolutely focused on textbook affordability. And with that came the interest in open education and establishing an open pilot program here at the university. So the very first thing that I did when I got into office was send out a survey that would help us understand what the student body costs of textbooks are on our specific campus. I noticed that sometimes, you know, when you go to administrators with national statistics, there is a moment where administrators can be like, well, this is happening nationally, but we don't know if it's happening on our campus. So there's kind of a gray area to deny that potentially this is happening. And it's also good for you to know as the person who's going to be, you know, pushing for this for textbook affordability from a student perspective where students are at. So I sent out a survey to the student body and what we found were some really interesting statistics that I'll share in a minute. The second thing is we went to the provost with those statistics and we discussed, you know, look, we think that we need to bring an open pilot program get faculty interested. Start start a committee. What can we do to get open education on our campus and our provost was amazing and reached out to the dean of libraries to start a pilot program that was funded for $20,000 to 20 professors to try in the fall semester, a year later. So in that year, we actually spent a lot of time, you know, bringing faculty to the table and asking questions, you know, this kind of common questions around open ed and why faculty with the common questions that faculty have. And then also I was able to be a part of all of those meetings. So I was able to provide a student perspective as to why things were necessary. And then understanding and navigating the faculty concerns and issues came throughout the year. The first thing is that student voice has leverage and power. So many times faculty and admin are restricted and what they can say, and what they can do about initiatives they're very passionate about but students are the end consumer of any textbook affordability initiative or any affordability initiative in general, and students have a lot more leverage and power and are not really controlled by the administration. At all at the institution to say what they want to say and to implement what they want to see happen right to correct wrongs on campuses. So student voice has a lot of leverage and power on the campus. The second is that it's critical for faculty to hear from students and to be proactive about textbook affordability. So in that survey I mentioned earlier, 60% of the students said that their most expensive book was above $200 40% of students actually responded that the textbook alone has caused them to take fewer courses, not register for class they wanted to take and or earn a poor grade. And the biggest stat to come out of it that shocked me was that, despite all of these concerns, 78% of students responded that they had never had a conversation with their faculty member about textbook affordability. So there's this gap between okay there's an issue, and then potentially a feeling of student powerlessness like oh this textbook is decided before I enroll in the class there's no way I can do anything there's nothing I can say or. I'll just have to, you know, change courses or whatever it may be, or bite the bullet so it's critical for faculty students to hear from students, a faculty to hear from students and also be proactive. And then knowing your audience is key figuring out what open means for them.  A faculty member is going to still have a lot of questions right so you need to know when you go to faculty member what it is that's important to a faculty member and changing their text or introducing open to their classroom and then what's important in an administrator. What did they want to know that's important for them right. Fourth is that data is important when speaking to administrators, you need specific data that other specific data of your campus and data of what other institutions have done to transition to whatever program you're trying to bring to the campus. In this case, open. So not only do you need that national piece or similar institution piece so like if you're a big university finding finding a big university that is able to match this this date the data or match your campus statistics so that they can see okay this is another institution that's similar that's done it, but you also need campus specific data that works so hard because they're not able to really contest your campus statistics right if you survey the students, this is a problem, there's no way to deny campus. And then last is change happens fast and the right pressure is applied so this is more of a motivating statement for students. There is always a way to get to the table with an administrator or faculty member always. And if you find yourself oftentimes ignored, or felt like you're just not heard or you can't find the community that wants to start open. You have options other than just constantly sending emails or trying to get a meeting. Go to your school newspaper and say I want to do an opinion piece on open education. And that that is very, very quickly you'll see change right away if that if that happens. Okay, on daily. So I'm going to go next and just sort of talk a little bit about my experience. The reason we wanted to structure the presentation like this is kind of just to highlight that there is no one student story there's no one student advocate story. And there's no one way to mobilize students on your campus. So in our context, from institution to institution and between when he and I even country to country when he being American and me being Canadian we both had very, very different experience in our roles as advocates. But we've come out with a lot of very similar, I guess sort of lessons learned or strategies to engage others in this work. So hopefully, you know now that we are sort of both of us straddling a little bit the both the student world and now being in the professional world in the first few years. Hopefully we can share some of those lessons learned with you.  When I ran for student government I was first elected in Canada in 2016 as vice president academic and my students union and in Canada those roles are structured as a full time job. So we have an office and we work 40 hours a week which is you know usually a bit more than that. But it's a full time job in which, you know, especially for my role the VP academic is very internal focused and for a student coming in.  And particularly for, you know, myself, being an undergraduate student at the time and as well I was the first person in my family to go to university. These were some really big challenges that I sort of needed to navigate right away and one year was barely enough time to do that. So I didn't go into my role knowing about OER. It was actually other student government leaders, notably from from BC, who, you know, introduced me to this idea at a conference. And it really grew on me and it became something that I wanted to incorporate into my platform. So alongside some other student government leaders in Alberta. We ran a provincial campaign called textbook broke Alberta, you know, based on what we knew at the time the textbook broke BC campaigns but which also originated out of US Perg. And it was had a huge impact on my campus. We were a campus that, you know, had a few advocates sort of sprinkled around, but really didn't have a dedicated channel for making this work happen. And that was something really big for us to kind of, you know, I actually was approached by, you know, staff in our university teaching and learning center. There was a faculty member who reached out to me, and then as well and I know that this doesn't happen to everybody but I actually had a representative from our bookstore reach out and say, you know, we know that we are is something that's gaining in popularity and we can work, you know, with you to make sure that this is something that you know we can be on top of but also be supportive of students and in Canada our bookstores are part of an ancillary service so it's not a private entity so I know that that makes the dynamic a little bit different. But it was that student that campaign that really sort of brought all these like unlikely allies together and got everyone in the room for the first time to chat about this work and and what we could do. So through there we were able to do a lot of lobbying institutionally we were actually successful in implementing a grant fund for faculty to start adopting these materials. And then through some of the organized student networks in Canada both at a provincial level and at a federal level we were able to lobby this issue to both provincial and federal policymakers so that was very very exciting to be part of. And then after that, you know, it just became very important to me that I felt like there were already some very established people who are doing this work and I thought that was fantastic and I so admired them but in my mind I was like you know if we really want to spread this further and make a change then we need other students to be on the board, and we need students to realize the power that they have to do this work. So I, you know, kind of took it upon myself to, you know, speak at a couple conferences and try to, you know, motivate not only students to advocate for this work but to try and help faculty librarians other institutional allies to help students to do this work. So on the next slide. These are just sort of some of the strategies that I've learned in my time specifically targeted at institutional allies who want to mobilize their students. I know especially this year. It's been an incredibly challenging year all the students that I've talked to. It's very different to feel, or very hard for them to sort of feel ownership over their role or to feel like they can do everything that they set out to do under such strange circumstances. So hopefully some of these, you know, will will help you to be able to work with your student government. So I'll just run through them really quickly. The first is establishing strong relationships with them. And just because you know students aren't lobbying for this already doesn't mean that they don't care about this issue. Absolutely. So something that you can do is identify, you know, are there students who are already advocating for open education at my institution. So what is your student government. Are there, you know, clubs organized around this. Are there specific students who have brought this up to their instructors or or to the library that you know of that you can pull in, sort of identifying what students are, you know tapped into this already. And what others are in a good position to do so and how can I connect with them meaningfully so one thing that I sort of like to recommend to people as to how the government isn't able to run like a full blown textbooks campaign, encourage them to communicate to students to talk about course material affordability in their course reviews. This may not specifically connect to we are. But it's a way to sort of, you know, shift something in students minds that say, you know, these books are expensive, but they don't have to be this way.  So identifying what or who represents institutional memory for the student movement on your campus here in Canada are student unions have the majority of them have full time paid staff. And Canada is usually a great avenue for you to go to sort of, you know, maintain longevity through turnover year after year. And also thinking about how we can solidify goals through policy so whether it's a resolution, whether it's you know just a policy statement saying this is something that we support and something that we want to continue working on into the future. So even if the council that comes after you, it's not one of their top priorities it's still solidified and you're in your governing documents and it's something that you can come back to year after year. And then amplifying impact thinking about how you as somebody who has a better understanding of the campus community, how can you bring students to the decision making tables.  So what's all about helping students realize their power and opening doors for them. So, again, how can I help student leaders especially undergraduates navigate the bureaucracy, what do they need to know who do they need to talk to who's in a good position to receive this information. And then lastly how can we publicly celebrate champions of open education. You know the way that it worked out for me when I ran that campaign and sort of you know being the person to stand there and and hold up the flashing light and say you know this is an issue I care about that helped attract other people to me and it brought more people onto my team to be able to do that work. So how else can we be sort of like waving that we are flag and attracting our people on campus and maintaining a sense of community who can be working on this issue together. Yeah, so. That was awesome. So we have some common questions which I think you know we've had some questions in the chat already so you know we can kind of start answering this question from James. How can faculty admin encourage student governments to take up or when there are many other issues competing for their attention. So, Haley and I get this question a lot after any sessions, the sessions. So the number one thing is that student governments often there may be a more pressing issue on your campus every campus is so different and every, you know, every campus has their own different struggles so even though your student government is not working on it I promise you there are a million and one other students that are interested about textbook affordability or want to be put on a committee or want to be in the room when these conversations are being had so if you are reaching out to the student body you just can't seem to get to them, try the senators as well or other, however their structure, each of them may be different sometimes their senators or executive cabinet members whatever it may be. You can try some of them as well, you can try reaching out to the administrator that usually oversees the student government or is their admin person. If that doesn't work, you can find other students on the campus so it doesn't have to be someone from student government, as long as there is always a room for a student. Next to you, then there should be a student next to you is kind of the idea. Okay. So any other questions. I feel like we can talk about this forever. 20 minutes is such a good time to try and get this to and it's something that, you know, I and I know when he feels so passionate about so happy to take, you know, follow up questions through only global connect. So we've got two minutes I'll try to answer one question there's what are the other reasons and affordability that students have to engage in we are plenty. I'll try to give my one minute elevator pitch but there's tons of research I know I know many of you as advocates, you know, are aware of most of this already but tons of research that says that, you know, by by adopting these resources students feel more compelled to. I don't really know how to put this. I guess research aside anecdotally like when I'm a student in a classroom and I see that a professor has taken the time, you know, to acknowledge my situation as a student and say you know here's something that I want to do to ease the burden on you. I'm way more likely to really appreciate that prof I'm way more likely to want to show up at their class every day. I'm way more likely to want to put in the extra effort for them if they're going the extra mile for me. And also the diversity perspective, where, you know, open books are more likely to reflect and be diverse and how they're written or change to be that way, whereas we've seen examples of Pearson and sing a text that are, you know, wildly either accurate, you know, there've been quite a few scandals per se about that so open texts reflect diverse populations more and overall is more equitable tool for students as well.


Hi there all, welcome and thank you so much for joining us. We're gonna be talking about scaling Apache Spark on Kubernetes. We're Amanda and Holden and we're so delighted to be here at KubeCon EU. So first and foremost, we're gonna tell you a little bit about ourselves. Then we're gonna talk about what is Apache Spark and why it matters to Kubernetes? What is Yarn and Mesos? Spark standalone mode, so get ready for that one. Why you should put Spark on Kubernetes? What worked well while we worked through this process? And what didn't work is good. Best practices for doing this kind of transformation. New features that have been implemented and upstreamed in areas for improvement. So who are we? So you'll see two of us in this picture, in this collection of pictures, work for Apple and that is me and Holden. And you also see our two pups, Timba and Jack. They support us throughout the day as we get our work done. Both of us have worked for Apple for over a year. I think Holden is getting close to two years. And both of us have been a part of the Apache Spark community. Holden much more so, she's an Apache Committer. She's written books on Apache Spark. She's been with it pretty much from the get go. I came to Spark a little bit later, but I've been involved with it for quite a few years. I've done quite a few talks on Spark and it's a technology that I enjoy. I like teaching other people about and using myself. So all right, so let's talk about Spark and what are these things? So what is Spark? So Lightning Fast Unified Analytics Engine is one of the tag lines you'll hear quite frequently. But Apache Spark is really used to do large scale data processing on large data sets. It's used by data scientists, data engineers, machine learning engineers, basically anyone who is working with large data sets, basically regardless of title. So Apache Spark allows for batch jobs, streaming jobs, the ability to use Spark SQL, R, Python, Scala, or Java. You can do machine learning using Spark and you can also do graph analytics with Spark as well. So some other tag lines you may have heard about Spark, which is it's Hadoop MapReduce, but with seven cups of coffee. Of course we have a little disclaimer there, check with your hardware vendor first. But I mean there's been so many numbers thrown around the years, but essentially Spark jobs because of their ability to utilize memory and large and do that large processing anywhere between 10 to 100 times faster than Hadoop, regardless of that's a big range, but it's faster. It is, Spark is a good way for folks to learn functional programming, which is true since Scala is a functional language. Me, myself, I know this much about Scala and I prefer to use Python. That's my language of choice when using Spark. So I did not take this opportunity to learn functional programming. And it's a great way to use a lot of compute resources, right? Because you're doing extremely large jobs across super large clusters, using a ton of memory and CPU. So let's talk about how Spark works. So basically what Spark does at the TLDR is it spreads out compute across a cluster, most specifically a Spark cluster, right? There's two main components when you launch a Spark job, the driver, which contains a Spark context. And which works to transform the user's code that I've written, maybe in Python, right? It splits it up into tasks, these byte size chunks that can be sent to be performed by the executors. And the executors reside on each node. So from there, it's very easy to scale up and scale down, depending on the workload, because you can always add more nodes and more executors. Especially when you're working in a cloud native environment in the cloud. It's really easy to add those extra resources. So Apache Spark has abstracted away from the user's any need to have to deal with orchestrating data processing parallelism or worrying about fault tolerance. This is all taken care of them, for them. So because of the architecture and knowing that Spark would be spread across multiple nodes on very large clusters, it was known that nodes would fail throughout this process. And so the executors are able to handle those failures because they know that they will happen and they can just recompute results. So the executors are long lived, especially when compared to MapReduce. And the executors store data in a mixture of memory and disk. So it utilizes both of those to run faster. With all this said, so now we know what Spark is, right? So Spark can be run either in a standalone mode with just Spark and a JVM on each machine, or you can use a custom resource management system. And that's what we're gonna talk about next. So what is Yarn? Yarn is yet another resource negotiator. So Yarn was released in 2012 and was a rewrite of MapReduce, the MapReduce engine from Hadoop 1.0. So MR2, which was the informal nickname, even though it really means MapReduce 2.0, which is an application that is actually managed by Yarn. So it all gets a little bit confusing. But it is the de facto standard for big data workloads. So Yarn supports a variety of process engines and applications. You can run Hadoop and Spark on the same cluster. You can do isolation and dynamic allocation of resources. So Yarn actually keeps track of the available resources. So memory, CPU, storage, and includes multiple types of scheduling methods. So it supports lightweight isolation and it allows to share local disk. And so with all this talk about resource allocation and managing resources, what does this remind you of KubeCon? Kind of reminds you of Kubernetes, doesn't it? So what is Mesos? So Mesos is a distributed system kernel. So Mesos is very similar to Kubernetes, but it's a bit more flexible. Not only can you manage containers, but you can also manage applications that are not containerized. So it does try to be more than just analytics, like maybe Yarn, which is being able to manage Hadoop and Spark. There's a private company now that is dedicated to working on it, and they are a bit more Kube, Kubernetes focused than in the past. And it also allows for local shared disk as well. So let's go into standalone mode. So are you tired of doing your actual job, which is writing Java or Python and doing data analytics?  Then this is the mode for you. So standalone Spark essentially a way to create a Spark cluster and manage that yourself. So there's no support, dynamic resource allocation or resource management and scheduling. This is the more painful option for sure, but it is possible. Maybe you have a use case where this works better for you. I would love to hear it actually. So it does not support dynamic scaling. So that's what you are for. So maybe some awesome scripts that you wrote and pager duty as well. So let's get into why we should put Spark on Kubernetes. So I think we've made it pretty clear that you need a dynamic resource cluster management system to help you manage your Spark workloads. But what was wrong with Yarn and Mesa is why I moved to Kubernetes, right? So there's a layer of reasons, right? Well, first, this is KubeCon, right? So we want to focus on Kubernetes, but all jokes aside, right? So one true ring to rule them all. We'll talk about that more in a second. You can use your spare capacity for analytics and the cloud. We're gonna talk about Python and what using Kubernetes allows you to do with Python. We'll talk about security and what that gives you by using Kubernetes. And of course, it's all about learning new skills, right? So just from our quick review of Yarn and Mesa, it's easy to see the benefits of needing a container management platform. When putting Spark on Kubernetes, you can add Spark and any other types of workloads. So it doesn't have to just be Spark or Hadoop, etc. So you can better utilize your cluster's resources because you can have all types of workloads from across your organization on one Kubernetes cluster. So and then just to point this out, right? So many of us in our, where we work, we may have just a little bit of everything doing, every type of technology there is, we have spread out across our companies, right? So you could have three cluster management systems, right? Mesa, Yarn, standalone, Kubernetes, that's actually four, right? But managing those all, that leads to a sad team, sad engineers, because that's a lot of overhead for them to have to try to switch between platforms and troubleshooting, etc. So of course, the solution would just be turn or two or three of them off, right? That'll just make all the workloads better, right? Well, yes and no. You want to definitely try to converge on one and Kubernetes seems like it's the direction that so many of us are taking. And so it gives you all the benefits of Kubernetes, which we'll talk about here in a second, and it just makes your life a little bit easier to just standardize on one platform. So it also, so like I said before, that you can run different types of workloads within that one Kubernetes cluster, so it allows you to use that spare capacity. So what's nice about Kubernetes, again, is that multiple types of applications and services can be all running on the same cluster. You don't need a dedicated Spark cluster that would be managed by Yarn or Mesa's to run your Spark jobs on that same cluster. You can actually run them on the same, so Spark jobs that may be analyzing your services, you can actually have the Spark jobs running on the same cluster as that. So like I said, they're kind of choppy. The Spark jobs you're doing can be analyzing anything from the very services that are running on the platform for doing any other kind of data crunching, right? So additionally, when we're talking about preemption and Kubernetes, so Kubernetes allows the ability to preempt workloads based on priority classes, which is really powerful. So workloads that are less time sensitive than other jobs can be rescheduled when resource demand is lower.  The power of Kubernetes allows for resources to be redistributed once a Spark job is complete and the pods have been released. So that resources can be given to other Spark jobs or to other services. So next year, so talking about containers and Python and security. So the ability to easily move workloads from Dev to Prod to add new libraries are, you know, that is because of things like isolation that Kube has. So data engineers and scientists are always trying to find new Python packages to add and ways, you know, new workloads that they want to be able to utilize the latest versions of these libraries and new versions of Spark. So with a single yarn, mesos, or standalone Kube cluster, standalone Spark cluster, I should say, you're absolutely tied to only using one version of Spark or Python that's on that cluster. With Kubernetes and containerization of Spark workloads, one data scientist can be using the latest version of Spark, so 3.1.1 with Python version 3.0. While your data engineer can continue to use Spark 2.4, why not, with Python version 2.5, all along the same cluster because it's all containerized and isolated. So anyone who has had to deal with Python dependencies understands the importance of having the ability to abstract using containers so that their jobs can do and use exactly what they want to use. Also, the ability to add increased isolation when dealing with data is very important and Kubernetes allows for this where yarn and mesos just didn't the same degree. So also just to add, when moving from yarn or mesos, Kubernetes has a lot of custom configurations that makes it a bit more flexible than yarn, per se. And last but not least, learning a new skill, right? Verholden and I personally, adopting to Kubernetes, has allowed us to pick up one more tool for our tool belt and of course now we're so much more popular, right? Because now not only do we know Apache Spark, we also know all about Kubernetes. So with that said, I will pass this off to Holden to tell us more about what worked well, what didn't work so well, making the transformation from Spark on yarn, Spark on mesos to Spark on Kubernetes. Thank you. Awesome. And thanks for that introduction. So now I'm gonna talk about sort of the second half of the presentation, namely what worked well and where we had rooms for growth. So small to medium size ETL jobs worked really well and migrating them to Qube was relatively easy. The only thing that we really had to do was increase the resource requests to match the reality of what they were actually using because yarn and mesos weren't enforcing the resource limits quite as strictly as Qube ended up enforcing them. There were some challenges around integration with the different data sources and that mostly comes back to some networking configuration choices that were made. And I think we could make some improvements there, but that's sort of just something to keep in mind, like make sure that you can easily access your data sources, but it was a relatively easy fix. Large and long ETL jobs were a bit more challenging. Long enough running jobs at low priorities tended to run into over commit issues. They'd still succeed, but often they'd take a lot longer than they would on mesos or yarn. And the primary room for growth here is more efficient resource utilization and more effective handling of over commit issues. Multi-language jobs are where things started to get a little challenging. So one of the really great things is that dependency management improved substantially compared to yarn. In the yarn world, all of the dependencies had to be managed by a systems administrator, whereas with running on cube, it can be very much more self-serve. The initial migrations often ran into resource difficulty and unplanned exits caused large amounts of recomputation. And this is, you know, the recomputation that is sort of expected, but it was more than the amount of recomputation that we were seeing running these jobs in other cluster environments. Most of our opportunities for improvement are around memory allocation and specifically sort of how we share native and JVM memory. Complex ML jobs did not work well when we tried to migrate them, primarily due to much more expensive recovery costs. So in all of these situations, Spark handles executor failure by recomputing data loss. With the complex ML jobs, the cost of recomputing that data is really, really quite expensive. The opportunities for improvement are around checkpointing. And so one of the things that we can do to sort of deal with this more expensive recomputation is when we get to these really expensive points, is checkpoint to persistent storage, but we had difficulties connecting to persistent storage, specifically the kinds with TTLs that can do automatic cleanups. And so this is one of the rooms for growth that we have in complex ML jobs. Streaming jobs had a lot of room for growth and just many areas of opportunity for investment. They just frankly don't work very well right now. And a lot of that is around the connection to the different data sources. It turns out that our connection to the streaming data sources has even more room for growth than our connections to the batch data sources. Also checkpointing is especially important in streaming. And so the same problem that we had from ML is even more present with the streaming jobs. So, okay, that's about our experiences moving to Kube. What are the best practices that we learned from this? So one of the things that we learned is not to just cash everything. Caching was never free, right? But now it costs even more. And that's because when we decommissioned an executor, we now have to migrate the cash data. And also now for caching stuff to disk, disk is actually a metered resource. So be careful.  If you're done with it, tell Spark you're done with it, right? Especially for users in no quick environments, the garbage collector isn't able to handle this as well. So you need to explicitly tell Spark that you're done with the data and it can get rid of it. Timbit, of course, is not done with the bone and he would prefer that we never get rid of the bone. Using disaggregated storage is super important. The big thing is there's no stay resident block manager anymore. And yeah, okay, data locality does matter, but it's not enough to try and co-locate HDFS. It's not worth it. Another really interesting thing is that using cloud storage from on-prem doesn't have as much overhead as one might think if you structure your network correctly. And so initially in a lot of situations, we assumed that we had to use HDFS, but after we did some benchmarks, it turns out that it was actually perfectly reasonable to use cloud storage from on-prem. So definitely don't just assume that you need to co-locate HDFS, take the time, run the benchmarks and see if it's actually gonna be worth it for you. One of the other things is that you're gonna need to increase your resource requests. And we talked about this a little bit with the job migrations. Essentially, yarn containers are very fuzzy definitions of containers. We have much stricter resource requirements in cube. So you're gonna need to allocate more memory. Femoral disk starts mattering, that wasn't tracked at all previously. Another one is don't set quota for the sake of quota. Default Spark uses config maps. We ended up doing a large rewrite of some code because of a config map quota. And it turns out that config maps weren't as expensive as we had assumed. So this is very important. When you are starting to set quota, definitely take the time to see if this is actually a constrained resource or if you don't actually need to have a quota here and it's perfectly fine to let things run wild. So in addition to the best stream practices for your jobs, let's talk about what things we changed. So we added a new mechanism for dynamic scaling in Spark. I'm really excited about this. This is actually based on the design that I came up with five years ago. And it just didn't make sense back then, but we'll talk more about it in a little bit. If you remove the commit fig map requirement as we talked about, we essentially added an alternative because of our quota system. Persistent storage for fallback on out-of-disk events. And we were really hoping that was gonna trigger more frequently what it turns out that, because of how ephemeral disk quota works, we don't actually get the out-of-disk events in the same way. So we also added some additional hooks inside of there. Integrations into PVCs, some templating. We also gave users the ability to explicitly remove unneeded shuffle files. And there were a bunch of sort of corner cases in Spark's understanding of pod state that historically hadn't mattered, but once we started to add dynamic scaling, did matter. And so we added graceful decommissioning and we made this to support dynamic allocation on Spark on Cube. And this is really important because historically Spark on Cube has not had a good dynamic allocation. Only recently, a restricted dynamic allocation was added where if there was no data on an executor, we could get rid of it. But by adding graceful decommissioning, if there is data on an executor, we can still get rid of it. We just migrate the data away first. There are some alternatives proposed by other people in the community of adding a truly external shuffle service. And there's a few different ones and we're not sure which one is gonna land, but it'll be interesting to see those things. And I think even once one of those things land, we'll probably still keep graceful decommissioning and we'll still leave it turned on because the truly external shuffle service only handles shuffle files. And Spark also has this concept of cache blocks and I think it makes sense to migrate cache blocks. Just while we're talking about this, one of the things that was a little counterintuitive with the configuration that we found was that we went from this sort of initial configuration of an executor idle time and a cache idle time of 120 seconds. And then we increased those idle times and we actually got better scale up and scale down with the higher idle times. And this is because essentially Spark doesn't do a great or really perfect job of keeping track of sort of if an executor is likely to have a job scheduled on it. And so we will get into the situation where we would start to see executors coming up and going away, essentially flapping very quickly when we tried to set tighter timeouts that we thought would actually cause better scale up and scale down experience. But by relaxing these timeouts, we actually got a much more reasonable scale up and scale down experience. We added external shuffle storage. This allows scaling beyond with executor to executor migrations support. There are alternative proposals for doing essentially more on top of this. But this is really important because with executor to executor migrations, we can only scale down to the point that we still have enough FMRL disk available for the data. And if you have a lot of data, but like let's say your data scientist goes home at the end of the night, really it probably makes sense to go ahead and put that data in some kind of external storage while the data scientist is taking a break from their job, hanging out with their family. So what were some areas for improvement? So is specifically in graceful decommissioning and dynamic allocation. I would say our biggest area for improvement here is documentation. It is possible to turn on, but really right now, as we saw from that configuration example, it sort of involves a lot of fine tuning and playing with things. So we haven't documented it because we don't know what the right settings are generally. We know what the right settings are for our cluster, but we haven't had enough other people sort of play with it. So we don't have good recommendations here yet. And so if you do want to play with graceful decommissioning and dynamic allocation on Spark on Cube, I would really, really appreciate your feedback on sort of what's working and what's not working. And if you can contribute that to the documentation, that would be amazing. Another thing is not all data is equal, right? And Spark has some internal heuristics around what kind of data is more likely to be used or not. They're not perfect. We could start by applying those heuristics to block migrations or we could try and come up with better heuristics for what kind of data is worth migrating. Another one is avoiding cascading failures. We have some work on this and it essentially can come to the point where quota can trigger cascading failures as we do migrations and we force executors over their quota limits. We have sort of a hacky solution, a longer term though, I think this is an area for better investigation. Lazy write back support I think is also really interesting. And that's this idea that like, yeah, we still want to try and store data locally on the executor, but we can start writing it back to persistent storage as soon as it lands on the executor. I'm not sure if this is gonna like give us good performance or not, but I think it's an area that really has a lot of potential and I'd like to see some more folks investigating it. So more generally, Spark on Cube has a lot of areas for improvement. Documentation is still, there is some documentation for Spark on Cube, but I think this is an area where we can once again improve a lot. Another one is sort of Q mechanisms and better understanding of the different kinds of jobs that Spark is scheduling and integration with the Cube scheduler so that we can actually get faster spin up. Another one is better communication for failure reasons. This is something that I've been working on a little bit because there's all kinds of reasons why things can fail and it can be difficult for a user to get at that information. It's not populated into the Spark web UI and so I think finding ways to better communicate to users what's going on is really important. Dynamic preemption priorities, this is really complicated in the Spark world and that's because we definitely have this concept of pods that are maybe more important but the problem is which pods are more important is going to change a lot while our jobs are running and even as we change resource profiles or even within the same resource profile as data ages in and out. So we don't have a really good way to communicate that to the Cube scheduler right now. Another one that is kind of maybe, I don't know if this is a good idea but I think it's worth exploring because it's a sort of hack that we've used in Spark on different systems and essentially it's where we use a shared local volume when we have multiple executors scheduled on the same node and this allows us to sort of pass data back and forth without necessarily having to go through the JVM on both sides of it. Another one is handling of jobs with changing priorities or deadlines. So we might have a job which is very low priority but it really does need to complete by the end of the month and so we don't have a good way to express that right now. In fact, like a user would actually probably have to cancel and reschedule their job at a higher priority if it was getting close to a deadline. I think having a good way to express this in Cube or in say like volcano or something could be very useful. So in conclusion, Spark on Cube migrations, they're not something that you can just set and forget. And yes, we can preempt Spark more than API servers. It has less impact on end users but there's still a lot of work that we can be doing to make the Spark on Cube preemption experience better. The increased isolation does come with some overhead. I think it's well worth it for the benefits that we get, the security improvements and the additional flexibility around Python and native libraries. And also we really like cake and docs, you know. So thanks for coming. We really appreciate it. I hope you are having a wonderful CubeCon and please stay safe. Thank you.