7th HLF – Lecture: Concurrent Connected Components Algorithms
Tarjan, Robert Endre
The problem of finding the connected components of an undirected graph is one of the most basic in graph algorithms. It can be solved sequentially in linear time using graph search or in almost-linear time using a disjoint-set data structure. The latter solves the incremental version of the problem, in which edges are added singly or in batches on-line. With the growth of the internet, computing connected components on huge graphs has become important, and both experimentalists and theoreticians have explored the use of concurrency in speeding up the computation. We shall survey recent work. Even simple concurrent algorithms are hard to analyze, as we discuss. This work is joint with Sixue Liu of Princeton. The opinions expressed in this video do not necessarily reflect the views of the Heidelberg Laureate Forum Foundation or any other person or associated institution involved in the making and distribution of the video.
 So, our next speaker will be Bob Tarjan, who is a professor at Princeton University. He belongs to a very distinguished group of scientists who has received a award from the computer science community and the math community. We heard, as far as I know, the only other member of this distinguished group, Leslie Valiant, talked yesterday. And Bob Tarjan received the Neville-Lenna Prize in 1982 and the Turing Prize in 1986. So Bob, the floor is yours. Good morning. Thank you. I'm hoping for a little audience participation. There will be a few places in my talk and at the end I would love to get some questions from the young researchers on my talk or any other subject that you're interested in. Terry Pancake mentioned in the opening ceremony that the Turing Award is given for work with a 25-year horizon. So John Hopcroft and I got the award in 1986 for work on, fundamental work on data structures and algorithms. How many of you young researchers were alive in 1986? Okay. So 25 years before 1986, that was 1961. I did not do this work in 1961. In 1961, I was in the eighth grade in junior high school. But I had a wonderful math teacher who was teaching us pianos, axioms, and abstract algebra, which was kind of the new math, but this was before the new math got introduced in the U.S. and completely failed, but it was a catnip to this cat. But so now I'm going to talk about concurrent connected components. But let me be, so I've been in this field for a long time. This is going to be recent ongoing work, hopefully us old fogies can still contribute a bit. But before I talk about this, I want to make a few observations based upon my own experience. So computer science is quite a young field, especially compared to mathematics or physics. It's been running for maybe 50 years, maybe a bit longer. We found a number of beautiful, theoretically efficient algorithms, developed beautiful theories of complexity. But there's a gap between theory and practice. Many of these algorithms have yet to be used because they're complicated or for other reasons. And if they're not correctly implemented, they can fail. If the engineers who are trying to implement the algorithms can't implement them correctly, and this is a subject that Leslie Lamport, for example, knows all about, disaster happens. And furthermore, our theoretical notions of efficiency do not necessarily correlate with what happens in the real world. Often very simple methods suffice, even though they may have worse theoretical performance. So what is going on here? Well, we know that software developers' human time is much more precious than machine time. If you're faced with a deadline, you choose the simplest solution that works, or that seems to work. And software developers may have learned some theory in school, and they try to apply it, maybe, but then maybe they oversimplify it and they get it wrong. Or they may build their own solution based upon ideas that they've seen and then provide some efficiency analysis, and maybe that is wrong because they're not theoretically trained and they don't have the time to work out the details. Now what is our challenge as theoreticians to try to respond to this real world phenomenon? I think it's very important to develop and analyze simple methods. The algorithm has got to be simple enough that somebody can actually program it and use it in practice. The analysis, the justification, even the proof of correctness can be arbitrarily complicated, but the algorithm has better be simple. So my research goal, generally speaking, especially these days, is to try to develop simple algorithms, I'll call them reference algorithms. Paul Erdos was a famous mathematician who had many interesting ideas, but one of them was proofs from the book. This is the book Up in the Sky, the perfect proof, if you will. So can we develop algorithms of the same type, algorithms from the book, as simple as possible, provable resource bounds for important input classes and efficient in practice. Now computers, notwithstanding the tailing off of Moore's law, keep getting faster and faster and memory sizes keep getting bigger and bigger, and this creates a massive design space for choosing possibilities for algorithms. Computer science, again, is a young field. People have plucked the low-hanging fruit, but there are places where maybe they didn't find the best solution. So let's try now to look at some of these important basic problems, systematically explore the design space and see if we can say something. This something like this quote was attributed to the design sign. Let's make everything as simple as possible, but not oversimplify. All right, so let's take an example that I hope will illustrate some of these points, the connected components problem. This is perhaps the most basic problem in graph theory. We've got an undirected graph, which just consists of a bunch of vertices connected by edges. Two vertices are connected if there's a path between them. A connected component is just a maximal set of pairwise connected vertices, and our problem is to compute the components. So now audience participation time number two. How many connected components? Three, anybody else? Good. Okay. One, two, three. That was pretty easy. How many connected components? Good. These four vertices are connected. All of these vertices are connected. All of these vertices are connected. No way to get from here to here or to here. Excellent. How many connected components? Take a guess. Three. Three is the answer. So here's an example. I mean, humans are very good if things are spread out, right? But everything is overlapping, and a computer could do this easily, but maybe not a human. All right. How are we going to address this problem algorithmically? You call it the others differently. Thank you, wit. We need a way to represent the solution. So the representation is going to be a label for every vertex such that two vertices in the same component have the same label. And we'll require that the labels be vertices in the component. So we want to label every vertex in a component with a single unique vertex, call it a canonical vertex. And then we can easily test for any two vertices if they're in the same component or not. I'll use little n to denote the total number of vertices, little m to denote the number of edges. And we'll assume that the vertices are just numbered from one to n, or they are the numbers from one to n, the integers from one to n. And one useful labeling to think about is the minimum labeling, where every vertex is labeled with the minimum vertex in its component. And I'm going to use this very simple graph with one component consisting of all the vertices, one through seven, as sort of a running example. So the minimum vertex in the component is one. This is the labeling. So these are the vertices, each one labeled with label one. Now another way to represent a labeling is this is just a function from the vertices to the vertices. And we can represent this, forgive my poor use of PowerPoint, but the red arrow is denote the function value. So there's one fixed point here at one. This is the canonical label. This is just a function. And this is the solution to our problem. We want a labeling for every component. Now it's easy to compute connected components sequentially, that is one step at a time, and there are two classical ways of doing this. The first is to use graph search. Any kind of graph search will do breadth first search, depth first search. So breadth first search, for example, we start at an arbitrary vertex. We go to all adjacent vertices from there to all adjacent vertices and so on. And we can't get anywhere else. We've explored an entire component, and then we start from another unvisited vertex and repeat. Depth first search, we proceed along a path until we get stuck and we have to back up. That's a different kind of search. There are lots of kinds of search. Any one of them will solve this problem in time linear in the graph size. Another approach is to turn the problem into a data structure problem. We use a so-called disjoint set or union find data structure, which does the following. It allows us to maintain a collection of disjoint sets, each initially a singleton, and each of which has a canonical element. And we're allowed two operations. A unite operation, which given two elements, if they're in different sets, combines the sets into one. If they're already in the same set, the unite operation does nothing. That's the update. And the find operation returns the canonical element of the set containing the element x. So if we have some implementation of these two operations, this data structure, it's easy to solve the connected component problem. We just iterate over all the edges. And for each edge, we unite the endpoints. And that's going to put all the vertices in each connected component into one particular set. The underlying data structure is picking the canonical elements. And then we do a second loop that returns the labels, which are just the results of the find operation. Now notice here that we don't actually have to execute this second loop. We can use the find operation to give us the values if we want to do a test whether two vertices are in the same component or not. Now graph search solves the problem in linear time. And it turns out that if you implement the union find operations in a nice way, you get a solution that is almost linear time. There's an extra factor here of what I'll call alpha. This is the inverse of Ackerman's function. For those of you who know Ackerman's function, it's a very simple data structure with a very complicated running time. And there's a whole additional story here that I'm not going to tell. But for all practical purposes, this is a constant. A nice thing about this, the use of the data structure here is that you don't have to build a representation of the graph. All you need is the edge set, the lists of pairs of vertices. And also you can do updating. You can do arbitrary insertions of new edges into the graph and update the connected components as you go. You get extra flexibility here. Now the obvious question to ask is what happens if you want to support edge deletions as well as insertions? That's another story that I'm not going to talk about here. Well, good. Is this the end? How about really big graphs? So it's amazing the kind of things you can find on the web. CLM stands for product lifestyle management. So this is a graph of various products and their path through their life cycle somehow. This one, I believe, is proteins that interact with each other. Here's some, this is some kind of a friendship graph. Think of the Facebook graph. So how big is big now? With the advent of the worldwide web, Facebook, Google, and so on, people want to solve problems like this and in particular find connected components on grass with billions, at least billions of vertices and trillions of edges. For such problems, even linear time might not be fast enough. So can we do better? And in particular, can we go beyond sequential algorithms? Can we use parallelism or concurrency to speed up the computation? So let's think about this in a big way. Lots and lots of processors, constant processors per edge. So the algorithms that I'm going to be talking about, we think of one or two processors per edge and a few processors, one processor per vertex. What is the computation model here? Well there are two possibilities and I'm not going to go into great detail in the models. The so-called PRAM parallel random access machine where there's a global common memory and a bunch of processes that are allowed to access the common memory and they each have some small amount of private memory. So common memory model. The issue with PRAM model, there are many issues, but one of them is do you allow concurrent reading and what happens on concurrent writing? How do you resolve right conflicts? I'll come back to that point in a minute. Another model, the one that's, so the PRAM model goes back to the 80s at least and was the favored one of the theoreticians. The more recent model is a distributed memory model. Think of Hadoop or MapReduce, computing in the cloud, it's all about message passing. So here the memory is distributed, every process has its own memory and it's sending messages to other processors and getting information back. So we think about a process for each vertex and each edge and they're sending messages back and forth. I'm going to describe some very simple algorithms that can be implemented in either of these models. So here's a naive algorithm of the kind I want to think about. This is just label propagation. For convenience, I'm going to replace every edge, this is an undirected pair here, by two directed copies, directed arcs. So this goes from V to W and this goes from W to V. This is just to simplify the notation here. So how does this work? We initialize that I'm going to use V.p, p for parent, I'll come back to this point in a minute. This is going to be the label of a vertex. I initialize every vertex to have its own itself as a label. Then I iterate over the arcs and I update the parents by replacing the old parent by the minimum of the ends of the parents of all the adjacent arcs. We'll see the example, a worked example on the next several slides. So the PI values are the current values, the I plus one values are the new values. We keep doing this until nothing changes. The final set of parents is the result of the computation. So we got three lines of initialization. V.p is the parent or the label. This loop runs synchronously in parallel. So every arc is doing the same thing at the same time. That means there may be several values getting written into the new parent simultaneously based upon multiple arcs. So I'm allowing concurrent reading to get the values. And I'm also allowing concurrent writes. And I'm assuming that write conflicts are resolved in favor of the smallest value that's encoded by the min here. And the fact that I put in these subscripts, this guarantees that you could actually run this sequentially if you wanted to and it would be correct and everything works. But if you were actually going to implement this on a PRAM or a distributed model, you would want to do an appropriate replacement of this pseudo code by real code. So on the PRAM model, for example, every arc would read the parents of both ends and then try to write the appropriate value into the other one. In the message passing model, each vertex would send its parent to all the arcs and then the arcs would do something and send information back to the parents. I won't go into the details. I hope the algorithms will be straightforward enough that you can think about how you would implement these if you wanted to do it. All right, so here's the label propagation algorithm run on this example. Everybody starts out self-labeled. And now the 7, 6 arc allows us to update the parent of 7 to be 6, but 5 is also a candidate. So 7 is going to end up with label 5. 5 has two possibilities. 3 and 7. 7 is bigger, so it drops out. But 5 gets 3, 3 gets 2, 6 gets 4, 4 gets 1. And this is the picture. So instead of a whole bunch of self-loops, now we've got two paths, actually. And we've decomposed things into two pieces somehow. And now things progress. These vertices start improving toward 2, and these vertices start improving toward 1. And you've got to wait for a while because the answer for all of them is supposed to be 1. But eventually, 6 points to 1, and then 7 gets 1 as a candidate, and then 7 is going to get pulled off. 5 will get pulled off. 3 will get pulled off, and 2 gets pulled off at the end. And I'll go through this quickly here. And we end up with the ultimate solution after some number of steps. Now this is a highly parallel algorithm, but it's not very efficient because this graph has large diameter. The diameter, the maximum number of edges on the shortest path, is essentially the size of the entire graph. So this algorithm, in effect, it's doing concurrent breadth-first search from all the smallest vertices in the components plus some extra work. It's highly inefficient, although it has been proposed in practice. But it does have the property that if you run this on your most parallel computer with huge resources up in the cloud, you can still beat it on a relatively small PC with a depth-first search, let us say. So not so good. But this is the first step. So let's try to do better. How can we improve this algorithm? How can we deal with the high-diameter situation? There's a wonderful idea that goes by several names. I'm going to call, oh, wait. We'll get there. Let me talk about this notion of why do we want to think of labels as parents? I've kind of illustrated this in the picture. So if we think of the pairs of vertices and their labels, parents, as being arcs, this defines a directed graph. Every vertex has out-degree exactly one. This is like a function. If the only cycles in this graph are self-loops, then we get a set of rooted trees, where this really is the parent in the rooted tree. So we're really manipulating a collection of trees. The connect steps are kind of hooking trees together or breaking a subtree off and putting it someplace else. But the side effect of connecting is we get deep trees. We have to somehow compensate for the deep trees. And the way we'll do that is by using this shortcut operation that goes by other names, as I said. So this simultaneously concurrently replaces the parent of each vertex by the grandparent. And it roughly halves the depths of all the vertices. So if you do a logarithmic number of shortcuts, you will squash all the trees. And I'll call a tree flat if it's just got a bunch of children and a root. And that is our ultimate objective, to create a flat tree for each component, one tree per component. So we might get from linear number of parallel steps down to logarithmic number of parallel steps. Here I said log n, but one might actually hope for log d. But can we do that? And what are algorithms going to look like? So we've got this notion of connection based upon edges or arcs and short cutting. We're going to put them together. So now I want to consider several algorithms based upon these principles. Each algorithm is going to do a collection of rounds. And every round is going to consist of looking at the arcs and changing parents, doing some kind of a connection. And then doing one or more shortcuts, and then possibly something else, and changing the edges to make things simpler. All right. So a connect step is going to update the parents based upon the arcs. Short cut is going to replace parents by grandparents. An altar is going to replace arcs. There are several different ways to do the connection. What the label propagation algorithm did was one kind of connection. And I'm going to look at sort of the two extreme cases, which I'll call direct connect and parent connect. So direct connect, you look at every arc and you replace the smaller parent. So W is a candidate for the parent of V and vice versa, because we've got arcs going in both directions here. Parent connect looks one step deeper into things. So if we have an arc VW, this is replacing the parent of the parent. This is the new parent of the old parent, and the candidate value is the parent of the other end here. All right. So we've got shortcut. We're going to use one or the other of these forms of connection, and I'll come to a couple more in a moment. And here's what we do with the arcs. We replace each arc by an arc between the parents of the two vertices. But they are different. If the parents are the same, we just throw the arc away. So that's the arc alteration step. There are other possibilities to do arc updating that have some properties. These are sort of opposite approaches. One is to try to delete arcs, to sparsify the graph so you don't have as many arcs to work with. And you'll notice that this arc alteration does some kind of sparsification because when an arc becomes a loop, it gets thrown away. I should also say that this can create multiple arcs which we process, and they're harmless to the algorithm, although maybe not to the notation, shall we say. Okay. Or we can densify. We could add arcs to try to connect things together even more, sort of a more global form of short cutting. So here is our first algorithm, which I'll call Algorithm C for Connect. It repeatedly does the parent connect step and the shortcut step until no parent changes. Very simple algorithm. I wish I could say something about how efficient it is. I have no useful information, no useful theory on this one, which is odd because it's so simple, right? Here's another one. This one uses arc alteration, and it replaces the parent connect step here by a direct connect, and then it does a shortcut, and then it does an alter. So if we want to use the simple form of connection, we have to use this edge altering process because otherwise you immediately get stuck and you don't make progress. This one I'm going to try to illustrate. This one we can prove interesting things about. And I should say it was on the title slide. This is joint work with my grad student Cliff Liu at Princeton. So here we go. Here's the initialization. Now the first step is just like the first step of label propagation, and this is a little bitter drawing of what the parent arcs look like. But now we do the shortcutting step. So the shortcutting step is going to make 6.1, 7.3, 5.2. And now we do the arc alteration step, which is going to get rid of a bunch of arcs here, in fact, and leaves us only with the... So this is actually two arcs. This is one edge. This is a 3-1 arc and a 1-3 arc and a 2-3 and a 3-2. So this is the state after one round of this algorithm. We've got two trees, and they got squashed by the shortcutting. This tree is flat. Everybody is either the root or it points to the root. This one, there's still a path of length 2 here. And this thing eventually finishes. And it looks like it doesn't finish much faster than the label propagation algorithm, but if you look at bigger examples, it really is much faster, and we can prove nice bounds about it, which I'll come back to. But before doing that, nice algorithm, simple algorithm, does it have possible disadvantages and how might we overcome them? Well, it's maintaining trees because the labels only decrease, and all the algorithms I will present here are computing the minimum labeling. But it can, in fact, in the connect step, it can break a subtree off of one tree and reattach it to another tree if it thinks things are improving locally. That's a kind of a non-monotonic process, and we might think that that's kind of going sideways instead of making progress. We'll call an algorithm monotonic. If it doesn't, in fact, split trees. If you want our algorithm to be monotonic, we have to make sure that when we're connecting, we only change the parents of roots. So let us modify the connect steps to only change parents of roots. That gives us, in the parent case, we get this. So this is a test which basically says I'm only going to change the parent of a root in this connect step. So if my parent is my grandparent, the parent is a root, and only then am I allowed to do the corresponding update. And I notice I didn't put the subscripts in here. So here is algorithm R for root connect. This is like algorithm C except that we restricted the connect step to roots. And this one we can prove quite nice bounds for. And there's a variant of this algorithm that replaces this by a direct connect, parent-direct connect alter, a different algorithm, interestingly, but with more or less the same properties. You can imagine the combinatorial explosion when you start putting these sorts of things together in different ways. But let's focus on these few. Now there's still a possible drawback of these algorithms. The connect steps are producing these deep trees. And the shortcutting process is gradually making the trees flatter. But especially if we're only connecting roots, we got to wait till things get flattened out before the edges accumulate down near the roots, and we can actually hook trees together. So how can we overcome this delay by repeatedly doing shortcuts? Now a shortcut takes one process per vertex, whereas a connect step takes one process per edge. So it is perhaps reasonable to do more shortcuts per iteration. Several shortcuts or even a non-constant number of shortcuts per iteration. The extreme would be every time we do a connect, we then shortcut to make the trees completely flat. And here is an algorithm that does that, algorithm S. Once you, so this has two loops. There's an inner loop that repeatedly shortcuts to completely flatten the trees. And in between, we do the parent connect. So we're always operating on flat trees. And we don't have to test for roots, because this is now guaranteed only to connect roots. So we've got three algorithms I want to focus on. Algorithm A, algorithm R, and algorithm S. And there's algorithm C that I can't say anything interesting about. History is simple, but they seem to be new, all these algorithms. They're simpler than the ones in the existing literature. And I would welcome citations to show me otherwise. The question we want to answer is how many steps do these algorithms take? How many parallel steps? How many rounds? Before I address this question, let me talk a little bit about history. So the first era of working on parallel algorithms, this was the theoreticians roughly from the 1980s to the 2000s. The machine model was the parallel random access machine or some flavor of this model. And the goal as the typical goal of theoreticians is to maximize the efficiency, minimize the parallel time and the total work, which is the number of processors times the parallel time. Even if the algorithm is complicated. The triumph in this field was a beautiful but complicated algorithm of Halperin and Zwick, and actually there are two versions of it. Logarithmic number of parallel steps, sublinear number of processors, which means that the total work is linear, giving a concurrent algorithm that is as efficient as a search-based solution, a sequential solution. And this algorithm throws everything, including the kitchen sink that people knew from this field at this problem, I would say. Randomized, it's in the exclusive read, exclusive write model. So there's no write conflicts and no read conflicts, which is even more astonishing. Nobody knows if it can be de-randomized or not. The algorithms that I've described are very simple deterministic algorithms. Now the second era, roughly 1990s to the present, people actually wanted to solve, this is the internet, right? People wanted to solve this problem on very large scale graphs. They started looking at parallel algorithms, notably in the distributed model based upon new distributed computing frameworks that we are familiar with. And the goal here was to actually get something fast in practice, simple enough that it could be implemented by a competent programmer. The people who worked in this area read some of the literature, at least the early PRAM literature, made claims like not implementable or too complicated, which is not really true. So they invented their own algorithms with some hand-wavy and sometimes flawed proofs of resource bounds. So the question here is to try to come up with simple methods for which we can prove things so that the practitioners can use these ideas and have good performance with some guarantees. Okay. So where did our algorithms come from? But algorithm R, this root connect algorithm, can be thought of as based upon a classical paper by Shalok and Vishkin published in 1982. They operated in the more standard model where right conflicts, you know, you can't predict which right wins. Arbitrary resolution of right conflicts. This is a weaker model. It maintains trees. It doesn't move subtrees around so it has this monotone property. It doesn't do minimum labeling. It does two shortcuts per round, although they claim that this is not needed, although they claim it simplifies the analysis. And they put some extra complications in there, extra steps to guarantee that every round, the difficulty with this sort of algorithm is you can have a tree that gets flat and then it just, it's connected to other trees, but it sits there for a long time before it gets connected to something else because the connections to other trees are deep in the other trees and they have to get flat before anything happens with the flat trees. So they added some extra steps to get around this problem. They did prove a logarithmic bound, which is kind of our goal here, not so simple analysis. And they showed that a simplified version of their algorithm that notably doesn't have these extra steps doesn't work so well. It's like label propagation. But this example relies on their right conflict resolution assumption. And if you reinterpret this algorithm R that I presented for this model, it doesn't work. So the point is we're changing the model here, we're strengthening the model to something that is perfectly reasonable in this day and age. We get a simpler algorithm, but to get it, we need this stronger right conflict resolution. So this is maybe a reason nobody talked about this algorithm back in the PRAM days. This algorithm S doing repeated shortcuts. Then in the late PRAM era, shall we say, Griner did some experiments with many algorithms. There were early parallel machines, the connection machine, for example. And people got excited to try to play with these things. And he devised an algorithm that does repeated shortcuts. It uses direct connect and edge alternation. But he was worried about this problem of delayed connection of these trees. So his solution to this was in alternate rounds, instead of taking minimum values, you take maximum values. So the intuition here is that you do logarithmic shortcuts that flattens the tree. That's the cost of the inner loop. If every tree gets combined to some other tree, every iteration or every other iteration, you have the number of trees in each iteration. In the outer loop, that's going to give you a log squared bound. That's what Griner claimed. This algorithm is used in practice. The GPU people seem to be particularly enamored of it. Turns out to the best of my ability to interpret this algorithm, this bound is not correct. This thing, in fact, has this bound, and even a very simple example, kills this thing. So this is kind of astonishing to me. So young researchers read the literature skeptically. There are opportunities there. Prove results for yourself. Look for gaps. Okay, now there's one more algorithm which is algorithm A, and I'm already out of time here, so I better speed up. This is how I got started on this problem. Costas tutsuclis, my pardon to the Greeks in the audience. He was a PhD student a long time ago of mine, and these guys all worked at Yahoo, which is now Oath, they built an interesting parallel computing platform that they called Thronos, and they devised their own connected component algorithm, and algorithm A is in effect a simplification. They did a hand-wavy proof of log n bound here. The proof is not right. The proof makes no sense. I don't have a counter example for this one. This algorithm may in fact run in this many steps, but so does algorithm A, and it's considerably simpler, and this actually is the paper that got us started on this work. So we can prove, and I don't have time to go through the interesting technical details, that this repeated shortcut algorithm does have the bound that Griner claims, and it's simpler than his algorithm, so why not use it? This is the worst case, log squared. You can prove an average case bound for this algorithm, too, average case in the following sense. If the vertex numbers are random, uniform random numbers, the log n and the inner loop turns into a log log n. The trees turn out to be balanced to begin with, and these are upper bounds. This is a worst case bound, but this is not, and it might be that this thing has an average case behavior that's logarithmic. This algorithm R matches the log n bound of the Shalouk-Viskan algorithm, simpler. We had to use a variant of, now this is our book on Shalouk, which had a follow-on to the Shalouk and Vishkan paper. We use ideas from their analysis, but the interesting thing is you have to look at what happens over multiple rounds, because you have to deal with these flat trees that are just sitting there for a while. The analysis is pretty interesting. In algorithm A, we can prove a log squared bound as well, and I have no idea whether this is tight or not. In algorithm C, which I mentioned, I hope has the same bound, but it differs in subtle ways from this algorithm, and I can't prove anything about it. So is log n best possible? Well, in fact, no. This is still an ongoing field of research for the new version of the theoreticians. People have been trying to get to log d. There was a result presented in 2018 that gives a complicated algorithm in a powerful distributed model that allows sorting in constant time, and the bound is log d, that's the diameter times some log log that depends upon n and the density. This algorithm doesn't need this powerful model. You can implement this on a PRAM with arbitrary right conflict resolution. Using, essentially, just hashing. Stop now. Yes, okay. And this has been further improved to log d plus log log n. Last comment. I'm assumed global synchronization here. What happens if you have only local synchronization or total asynchrony? Proving resource bounds gets really challenging, but we do have some work on disjoint set union. Union find in the concurrent setting. And with that, I'll say thank you very much. Thank you very much for a great talk. Even if you are running slightly over time, we take the time for a question from the young researchers. Is there one in the back there? Hello. I might miss something, but from my understanding, in each step, you are having two competing factors. One is you want to keep the flat trees not very, so not increase the depth of the flat trees. And the other thing is you want to combine these trees sufficiently fast. But if you're aiming for log n factor, instead of making the diameter one for each time in the flat tree, couldn't you just leave them at log n? Wouldn't it make it slightly faster at least? Can you repeat what you just said? So in each step, if you want to create a flat tree, you could leave the depth of the flat tree as something like log n rather than making the diameter one. Then the edges are still left at the fringes. And if you're restricting your connection to the roots, you have to still get that information down to the roots for the next connect step. So I don't see how that would work. And in any case, if you want to go from n to log n by having, it's going to cost you constant log n in any case if I'm not mistaken. But we can take this offline, perhaps. Thank you. Okay. If there are no further questions, let's thank... Oh, there is one back in the back. Yes, all the way in the back. Hello. Thanks for the nice talk. I have a question that new tools of Apache Spark like GraphX, it deals with both complex as well as big graphs. So does your theory means these things are implemented, implementable to their type of framework also? I'm trying to work with practitioners to get these ideas implemented, getting theory into practice as a slow process. But these algorithms are simple enough, they should be implementable on any parallel platform whatsoever without too much trouble. That's what I think. Okay. Let's thank Bob Tajan once more. Thank you.
 So, our next speaker will be Bob Tarjan, who is a professor at Princeton University.  He belongs to a very distinguished group of scientists who has received a award from  the computer science community and the math community.  We heard, as far as I know, the only other member of this distinguished group, Leslie  Valiant, talked yesterday.  And Bob Tarjan received the Neville-Lenna Prize in 1982 and the Turing Prize in 1986.  So Bob, the floor is yours.  Good morning.  Thank you.  I'm hoping for a little audience participation.  There will be a few places in my talk and at the end I would love to get some questions  from the young researchers on my talk or any other subject that you're interested in.  Terry Pancake mentioned in the opening ceremony that the Turing Award is given for work with  a 25-year horizon.  So John Hopcroft and I got the award in 1986 for work on, fundamental work on data structures  and algorithms.  How many of you young researchers were alive in 1986?  Okay.  So 25 years before 1986, that was 1961.  I did not do this work in 1961.  In 1961, I was in the eighth grade in junior high school.  But I had a wonderful math teacher who was teaching us pianos, axioms, and abstract algebra,  which was kind of the new math, but this was before the new math got introduced in the  U.S. and completely failed, but it was a catnip to this cat.  But so now I'm going to talk about concurrent connected components.  But let me be, so I've been in this field for a long time.  This is going to be recent ongoing work, hopefully us old fogies can still contribute  a bit.  But before I talk about this, I want to make a few observations based upon my own experience.  So computer science is quite a young field, especially compared to mathematics or physics.  It's been running for maybe 50 years, maybe a bit longer.  We found a number of beautiful, theoretically efficient algorithms, developed beautiful  theories of complexity.  But there's a gap between theory and practice.  Many of these algorithms have yet to be used because they're complicated or for other  reasons.  And if they're not correctly implemented, they can fail.  If the engineers who are trying to implement the algorithms can't implement them correctly,  and this is a subject that Leslie Lamport, for example, knows all about, disaster happens.  And furthermore, our theoretical notions of efficiency do not necessarily correlate with  what happens in the real world.  Often very simple methods suffice, even though they may have worse theoretical performance.  So what is going on here?  Well, we know that software developers' human time is much more precious than machine time.  If you're faced with a deadline, you choose the simplest solution that works, or that  seems to work.  And software developers may have learned some theory in school, and they try to apply it,  maybe, but then maybe they oversimplify it and they get it wrong.  Or they may build their own solution based upon ideas that they've seen and then provide  some efficiency analysis, and maybe that is wrong because they're not theoretically trained  and they don't have the time to work out the details.  Now what is our challenge as theoreticians to try to respond to this real world phenomenon?  I think it's very important to develop and analyze simple methods.  The algorithm has got to be simple enough that somebody can actually program it and  use it in practice.  The analysis, the justification, even the proof of correctness can be arbitrarily complicated,  but the algorithm has better be simple.  So my research goal, generally speaking, especially these days, is to try to develop  simple algorithms, I'll call them reference algorithms.  Paul Erdos was a famous mathematician who had many interesting ideas, but one of them  was proofs from the book.  This is the book Up in the Sky, the perfect proof, if you will.  So can we develop algorithms of the same type, algorithms from the book, as simple as possible,  provable resource bounds for important input classes and efficient in practice.  Now computers, notwithstanding the tailing off of Moore's law, keep getting faster and  faster and memory sizes keep getting bigger and bigger, and this creates a massive design  space for choosing possibilities for algorithms.  Computer science, again, is a young field.  People have plucked the low-hanging fruit, but there are places where maybe they didn't  find the best solution.  So let's try now to look at some of these important basic problems, systematically explore the  design space and see if we can say something.  This something like this quote was attributed to the design sign.  Let's make everything as simple as possible, but not oversimplify.  All right, so let's take an example that I hope will illustrate some of these points,  the connected components problem.  This is perhaps the most basic problem in graph theory.  We've got an undirected graph, which just consists of a bunch of vertices connected  by edges.  Two vertices are connected if there's a path between them.  A connected component is just a maximal set of pairwise connected vertices, and our problem  is to compute the components.  So now audience participation time number two.  How many connected components?  Three, anybody else?  Good.  Okay.  One, two, three.  That was pretty easy.  How many connected components?  Good.  These four vertices are connected.  All of these vertices are connected.  All of these vertices are connected.  No way to get from here to here or to here.  Excellent.  How many connected components?  Take a guess.  Three.  Three is the answer.  So here's an example.  I mean, humans are very good if things are spread out, right?  But everything is overlapping, and a computer could do this easily, but maybe not a human.  All right.  How are we going to address this problem algorithmically?  You call it the others differently.  Thank you, wit.  We need a way to represent the solution.  So the representation is going to be a label for every vertex such that two vertices in  the same component have the same label.  And we'll require that the labels be vertices in the component.  So we want to label every vertex in a component with a single unique vertex, call it a canonical  vertex.  And then we can easily test for any two vertices if they're in the same component or not.  I'll use little n to denote the total number of vertices, little m to denote the number  of edges.  And we'll assume that the vertices are just numbered from one to n, or they are the numbers  from one to n, the integers from one to n.  And one useful labeling to think about is the minimum labeling, where every vertex is  labeled with the minimum vertex in its component.  And I'm going to use this very simple graph with one component consisting of all the vertices,  one through seven, as sort of a running example.  So the minimum vertex in the component is one.  This is the labeling.  So these are the vertices, each one labeled with label one.  Now another way to represent a labeling is this is just a function from the vertices  to the vertices.  And we can represent this, forgive my poor use of PowerPoint, but the red arrow is denote  the function value.  So there's one fixed point here at one.  This is the canonical label.  This is just a function.  And this is the solution to our problem.  We want a labeling for every component.  Now it's easy to compute connected components sequentially, that is one step at a time,  and there are two classical ways of doing this.  The first is to use graph search.  Any kind of graph search will do breadth first search, depth first search.  So breadth first search, for example, we start at an arbitrary vertex.  We go to all adjacent vertices from there to all adjacent vertices and so on.  And we can't get anywhere else.  We've explored an entire component, and then we start from another unvisited vertex and  repeat.  Depth first search, we proceed along a path until we get stuck and we have to back up.  That's a different kind of search.  There are lots of kinds of search.  Any one of them will solve this problem in time linear in the graph size.  Another approach is to turn the problem into a data structure problem.  We use a so-called disjoint set or union find data structure, which does the following.  It allows us to maintain a collection of disjoint sets, each initially a singleton, and each  of which has a canonical element.  And we're allowed two operations.  A unite operation, which given two elements, if they're in different sets, combines the  sets into one.  If they're already in the same set, the unite operation does nothing.  That's the update.  And the find operation returns the canonical element of the set containing the element  x.  So if we have some implementation of these two operations, this data structure, it's  easy to solve the connected component problem.  We just iterate over all the edges.  And for each edge, we unite the endpoints.  And that's going to put all the vertices in each connected component into one particular  set.  The underlying data structure is picking the canonical elements.  And then we do a second loop that returns the labels, which are just the results of  the find operation.  Now notice here that we don't actually have to execute this second loop.  We can use the find operation to give us the values if we want to do a test whether two  vertices are in the same component or not.  Now graph search solves the problem in linear time.  And it turns out that if you implement the union find operations in a nice way, you get  a solution that is almost linear time.  There's an extra factor here of what I'll call alpha.  This is the inverse of Ackerman's function.  For those of you who know Ackerman's function, it's a very simple data structure with a very  complicated running time.  And there's a whole additional story here that I'm not going to tell.  But for all practical purposes, this is a constant.  A nice thing about this, the use of the data structure here is that you don't have to build  a representation of the graph.  All you need is the edge set, the lists of pairs of vertices.  And also you can do updating.  You can do arbitrary insertions of new edges into the graph and update the connected components  as you go.  You get extra flexibility here.  Now the obvious question to ask is what happens if you want to support edge deletions as well  as insertions?  That's another story that I'm not going to talk about here.  Well, good.  Is this the end?  How about really big graphs?  So it's amazing the kind of things you can find on the web.  CLM stands for product lifestyle management.  So this is a graph of various products and their path through their life cycle somehow.  This one, I believe, is proteins that interact with each other.  Here's some, this is some kind of a friendship graph.  Think of the Facebook graph.  So how big is big now?  With the advent of the worldwide web, Facebook, Google, and so on, people want to solve problems  like this and in particular find connected components on grass with billions, at least  billions of vertices and trillions of edges.  For such problems, even linear time might not be fast enough.  So can we do better?  And in particular, can we go beyond sequential algorithms?  Can we use parallelism or concurrency to speed up the computation?  So let's think about this in a big way.  Lots and lots of processors, constant processors per edge.  So the algorithms that I'm going to be talking about, we think of one or two processors per  edge and a few processors, one processor per vertex.  What is the computation model here?  Well there are two possibilities and I'm not going to go into great detail in the models.  The so-called PRAM parallel random access machine where there's a global common memory  and a bunch of processes that are allowed to access the common memory and they each  have some small amount of private memory.  So common memory model.  The issue with PRAM model, there are many issues, but one of them is do you allow concurrent  reading and what happens on concurrent writing?  How do you resolve right conflicts?  I'll come back to that point in a minute.  Another model, the one that's, so the PRAM model goes back to the 80s at least and was  the favored one of the theoreticians.  The more recent model is a distributed memory model.  Think of Hadoop or MapReduce, computing in the cloud, it's all about message passing.  So here the memory is distributed, every process has its own memory and it's sending messages  to other processors and getting information back.  So we think about a process for each vertex and each edge and they're sending messages  back and forth.  I'm going to describe some very simple algorithms that can be implemented in either of these  models.  So here's a naive algorithm of the kind I want to think about.  This is just label propagation.  For convenience, I'm going to replace every edge, this is an undirected pair here, by two  directed copies, directed arcs.  So this goes from V to W and this goes from W to V.  This is just to simplify the notation here.  So how does this work?  We initialize that I'm going to use V.p, p for parent, I'll come back to this point  in a minute.  This is going to be the label of a vertex.  I initialize every vertex to have its own itself as a label.  Then I iterate over the arcs and I update the parents by replacing the old parent by  the minimum of the ends of the parents of all the adjacent arcs.  We'll see the example, a worked example on the next several slides.  So the PI values are the current values, the I plus one values are the new values.  We keep doing this until nothing changes.  The final set of parents is the result of the computation.  So we got three lines of initialization.  V.p is the parent or the label.  This loop runs synchronously in parallel.  So every arc is doing the same thing at the same time.  That means there may be several values getting written into the new parent simultaneously  based upon multiple arcs.  So I'm allowing concurrent reading to get the values.  And I'm also allowing concurrent writes.  And I'm assuming that write conflicts are resolved in favor of the smallest value that's  encoded by the min here.  And the fact that I put in these subscripts, this guarantees that you could actually run  this sequentially if you wanted to and it would be correct and everything works.  But if you were actually going to implement this on a PRAM or a distributed model, you  would want to do an appropriate replacement of this pseudo code by real code.  So on the PRAM model, for example, every arc would read the parents of both ends and then  try to write the appropriate value into the other one.  In the message passing model, each vertex would send its parent to all the arcs and  then the arcs would do something and send information back to the parents.  I won't go into the details.  I hope the algorithms will be straightforward enough that you can think about how you would  implement these if you wanted to do it.  All right, so here's the label propagation algorithm run on this example.  Everybody starts out self-labeled.  And now the 7, 6 arc allows us to update the parent of 7 to be 6, but 5 is also a candidate.  So 7 is going to end up with label 5.  5 has two possibilities.  3 and 7.  7 is bigger, so it drops out.  But 5 gets 3, 3 gets 2, 6 gets 4, 4 gets 1.  And this is the picture.  So instead of a whole bunch of self-loops, now we've got two paths, actually.  And we've decomposed things into two pieces somehow.  And now things progress.  These vertices start improving toward 2, and these vertices start improving toward 1.  And you've got to wait for a while because the answer for all of them is supposed to  be 1.  But eventually, 6 points to 1, and then 7 gets 1 as a candidate, and then 7 is going  to get pulled off.  5 will get pulled off.  3 will get pulled off, and 2 gets pulled off at the end.  And I'll go through this quickly here.  And we end up with the ultimate solution after some number of steps.  Now this is a highly parallel algorithm, but it's not very efficient because this graph  has large diameter.  The diameter, the maximum number of edges on the shortest path, is essentially the size  of the entire graph.  So this algorithm, in effect, it's doing concurrent breadth-first search from all the smallest  vertices in the components plus some extra work.  It's highly inefficient, although it has been proposed in practice.  But it does have the property that if you run this on your most parallel computer with  huge resources up in the cloud, you can still beat it on a relatively small PC with a depth-first  search, let us say.  So not so good.  But this is the first step.  So let's try to do better.  How can we improve this algorithm?  How can we deal with the high-diameter situation?  There's a wonderful idea that goes by several names.  I'm going to call, oh, wait.  We'll get there.  Let me talk about this notion of why do we want to think of labels as parents?  I've kind of illustrated this in the picture.  So if we think of the pairs of vertices and their labels, parents, as being arcs, this  defines a directed graph.  Every vertex has out-degree exactly one.  This is like a function.  If the only cycles in this graph are self-loops, then we get a set of rooted trees, where this  really is the parent in the rooted tree.  So we're really manipulating a collection of trees.  The connect steps are kind of hooking trees together or breaking a subtree off and putting  it someplace else.  But the side effect of connecting is we get deep trees.  We have to somehow compensate for the deep trees.  And the way we'll do that is by using this shortcut operation that goes by other names,  as I said.  So this simultaneously concurrently replaces the parent of each vertex by the grandparent.  And it roughly halves the depths of all the vertices.  So if you do a logarithmic number of shortcuts, you will squash all the trees.  And I'll call a tree flat if it's just got a bunch of children and a root.  And that is our ultimate objective, to create a flat tree for each component, one tree per  component.  So we might get from linear number of parallel steps down to logarithmic number of parallel  steps.  Here I said log n, but one might actually hope for log d.  But can we do that?  And what are algorithms going to look like?  So we've got this notion of connection based upon edges or arcs and short cutting.  We're going to put them together.  So now I want to consider several algorithms based upon these principles.  Each algorithm is going to do a collection of rounds.  And every round is going to consist of looking at the arcs and changing parents, doing some  kind of a connection.  And then doing one or more shortcuts, and then possibly something else, and changing  the edges to make things simpler.  All right.  So a connect step is going to update the parents based upon the arcs.  Short cut is going to replace parents by grandparents.  An altar is going to replace arcs.  There are several different ways to do the connection.  What the label propagation algorithm did was one kind of connection.  And I'm going to look at sort of the two extreme cases, which I'll call direct connect and  parent connect.  So direct connect, you look at every arc and you replace the smaller parent.  So W is a candidate for the parent of V and vice versa, because we've got arcs going in  both directions here.  Parent connect looks one step deeper into things.  So if we have an arc VW, this is replacing the parent of the parent.  This is the new parent of the old parent, and the candidate value is the parent of the other  end here.  All right.  So we've got shortcut.  We're going to use one or the other of these forms of connection, and I'll come to a couple  more in a moment.  And here's what we do with the arcs.  We replace each arc by an arc between the parents of the two vertices.  But they are different.  If the parents are the same, we just throw the arc away.  So that's the arc alteration step.  There are other possibilities to do arc updating that have some properties.  These are sort of opposite approaches.  One is to try to delete arcs, to sparsify the graph so you don't have as many arcs  to work with.  And you'll notice that this arc alteration does some kind of sparsification because when  an arc becomes a loop, it gets thrown away.  I should also say that this can create multiple arcs which we process, and they're harmless  to the algorithm, although maybe not to the notation, shall we say.  Okay.  Or we can densify.  We could add arcs to try to connect things together even more, sort of a more global  form of short cutting.  So here is our first algorithm, which I'll call Algorithm C for Connect.  It repeatedly does the parent connect step and the shortcut step until no parent changes.  Very simple algorithm.  I wish I could say something about how efficient it is.  I have no useful information, no useful theory on this one, which is odd because it's so  simple, right?  Here's another one.  This one uses arc alteration, and it replaces the parent connect step here by a direct connect,  and then it does a shortcut, and then it does an alter.  So if we want to use the simple form of connection, we have to use this edge altering process  because otherwise you immediately get stuck and you don't make progress.  This one I'm going to try to illustrate.  This one we can prove interesting things about.  And I should say it was on the title slide.  This is joint work with my grad student Cliff Liu at Princeton.  So here we go.  Here's the initialization.  Now the first step is just like the first step of label propagation, and this is a little  bitter drawing of what the parent arcs look like.  But now we do the shortcutting step.  So the shortcutting step is going to make 6.1, 7.3, 5.2.  And now we do the arc alteration step, which is going to get rid of a bunch of arcs here,  in fact, and leaves us only with the...  So this is actually two arcs.  This is one edge.  This is a 3-1 arc and a 1-3 arc and a 2-3 and a 3-2.  So this is the state after one round of this algorithm.  We've got two trees, and they got squashed by the shortcutting.  This tree is flat.  Everybody is either the root or it points to the root.  This one, there's still a path of length 2 here.  And this thing eventually finishes.  And it looks like it doesn't finish much faster than the label propagation algorithm, but if  you look at bigger examples, it really is much faster, and we can prove nice bounds  about it, which I'll come back to.  But before doing that, nice algorithm, simple algorithm, does it have possible disadvantages  and how might we overcome them?  Well, it's maintaining trees because the labels only decrease, and all the algorithms I will  present here are computing the minimum labeling.  But it can, in fact, in the connect step, it can break a subtree off of one tree and  reattach it to another tree if it thinks things are improving locally.  That's a kind of a non-monotonic process, and we might think that that's kind of going  sideways instead of making progress.  We'll call an algorithm monotonic.  If it doesn't, in fact, split trees.  If you want our algorithm to be monotonic, we have to make sure that when we're connecting,  we only change the parents of roots.  So let us modify the connect steps to only change parents of roots.  That gives us, in the parent case, we get this.  So this is a test which basically says I'm only going to change the parent of a root  in this connect step.  So if my parent is my grandparent, the parent is a root, and only then am I allowed to do  the corresponding update.  And I notice I didn't put the subscripts in here.  So here is algorithm R for root connect.  This is like algorithm C except that we restricted the connect step to roots.  And this one we can prove quite nice bounds for.  And there's a variant of this algorithm that replaces this by a direct connect, parent-direct  connect alter, a different algorithm, interestingly, but with more or less the same properties.  You can imagine the combinatorial explosion when you start putting these sorts of things  together in different ways.  But let's focus on these few.  Now there's still a possible drawback of these algorithms.  The connect steps are producing these deep trees.  And the shortcutting process is gradually making the trees flatter.  But especially if we're only connecting roots, we got to wait till things get flattened out  before the edges accumulate down near the roots, and we can actually hook trees together.  So how can we overcome this delay by repeatedly doing shortcuts?  Now a shortcut takes one process per vertex, whereas a connect step takes one process per  edge.  So it is perhaps reasonable to do more shortcuts per iteration.  Several shortcuts or even a non-constant number of shortcuts per iteration.  The extreme would be every time we do a connect, we then shortcut to make the trees completely  flat.  And here is an algorithm that does that, algorithm S.  Once you, so this has two loops.  There's an inner loop that repeatedly shortcuts to completely flatten the trees.  And in between, we do the parent connect.  So we're always operating on flat trees.  And we don't have to test for roots, because this is now guaranteed only to connect roots.  So we've got three algorithms I want to focus on.  Algorithm A, algorithm R, and algorithm S. And there's algorithm C that I can't say  anything interesting about.  History is simple, but they seem to be new, all these algorithms.  They're simpler than the ones in the existing literature.  And I would welcome citations to show me otherwise.  The question we want to answer is how many steps do these algorithms take?  How many parallel steps?  How many rounds?  Before I address this question, let me talk a little bit about history.  So the first era of working on parallel algorithms, this was the theoreticians roughly from the  1980s to the 2000s.  The machine model was the parallel random access machine or some flavor of this model.  And the goal as the typical goal of theoreticians is to maximize the efficiency, minimize the  parallel time and the total work, which is the number of processors times the parallel  time.  Even if the algorithm is complicated.  The triumph in this field was a beautiful but complicated algorithm of Halperin and  Zwick, and actually there are two versions of it.  Logarithmic number of parallel steps, sublinear number of processors, which means that the  total work is linear, giving a concurrent algorithm that is as efficient as a search-based  solution, a sequential solution.  And this algorithm throws everything, including the kitchen sink that people knew from this  field at this problem, I would say.  Randomized, it's in the exclusive read, exclusive write model.  So there's no write conflicts and no read conflicts, which is even more astonishing.  Nobody knows if it can be de-randomized or not.  The algorithms that I've described are very simple deterministic algorithms.  Now the second era, roughly 1990s to the present, people actually wanted to solve, this is the  internet, right?  People wanted to solve this problem on very large scale graphs.  They started looking at parallel algorithms, notably in the distributed model based upon  new distributed computing frameworks that we are familiar with.  And the goal here was to actually get something fast in practice, simple enough that it could  be implemented by a competent programmer.  The people who worked in this area read some of the literature, at least the early PRAM  literature, made claims like not implementable or too complicated, which is not really true.  So they invented their own algorithms with some hand-wavy and sometimes flawed proofs  of resource bounds.  So the question here is to try to come up with simple methods for which we can prove  things so that the practitioners can use these ideas and have good performance with  some guarantees.  Okay.  So where did our algorithms come from?  But algorithm R, this root connect algorithm, can be thought of as based upon a classical  paper by Shalok and Vishkin published in 1982.  They operated in the more standard model where right conflicts, you know, you can't predict  which right wins.  Arbitrary resolution of right conflicts.  This is a weaker model.  It maintains trees.  It doesn't move subtrees around so it has this monotone property.  It doesn't do minimum labeling.  It does two shortcuts per round, although they claim that this is not needed, although  they claim it simplifies the analysis.  And they put some extra complications in there, extra steps to guarantee that every round,  the difficulty with this sort of algorithm is you can have a tree that gets flat and  then it just, it's connected to other trees, but it sits there for a long time before it  gets connected to something else because the connections to other trees are deep in the  other trees and they have to get flat before anything happens with the flat trees.  So they added some extra steps to get around this problem.  They did prove a logarithmic bound, which is kind of our goal here, not so simple analysis.  And they showed that a simplified version of their algorithm that notably doesn't have  these extra steps doesn't work so well.  It's like label propagation.  But this example relies on their right conflict resolution assumption.  And if you reinterpret this algorithm R that I presented for this model, it doesn't work.  So the point is we're changing the model here, we're strengthening the model to something  that is perfectly reasonable in this day and age.  We get a simpler algorithm, but to get it, we need this stronger right conflict resolution.  So this is maybe a reason nobody talked about this algorithm back in the PRAM days.  This algorithm S doing repeated shortcuts.  Then in the late PRAM era, shall we say, Griner did some experiments with many algorithms.  There were early parallel machines, the connection machine, for example.  And people got excited to try to play with these things.  And he devised an algorithm that does repeated shortcuts.  It uses direct connect and edge alternation.  But he was worried about this problem of delayed connection of these trees.  So his solution to this was in alternate rounds, instead of taking minimum values, you take  maximum values.  So the intuition here is that you do logarithmic shortcuts that flattens the tree.  That's the cost of the inner loop.  If every tree gets combined to some other tree, every iteration or every other iteration,  you have the number of trees in each iteration.  In the outer loop, that's going to give you a log squared bound.  That's what Griner claimed.  This algorithm is used in practice.  The GPU people seem to be particularly enamored of it.  Turns out to the best of my ability to interpret this algorithm, this bound is not correct.  This thing, in fact, has this bound, and even a very simple example, kills this thing.  So this is kind of astonishing to me.  So young researchers read the literature skeptically.  There are opportunities there.  Prove results for yourself.  Look for gaps.  Okay, now there's one more algorithm which is algorithm A, and I'm already out of time  here, so I better speed up.  This is how I got started on this problem.  Costas tutsuclis, my pardon to the Greeks in the audience.  He was a PhD student a long time ago of mine, and these guys all worked at Yahoo, which  is now Oath, they built an interesting parallel computing platform that they called Thronos,  and they devised their own connected component algorithm, and algorithm A is in effect a simplification.  They did a hand-wavy proof of log n bound here.  The proof is not right.  The proof makes no sense.  I don't have a counter example for this one.  This algorithm may in fact run in this many steps, but so does algorithm A, and it's considerably  simpler, and this actually is the paper that got us started on this work.  So we can prove, and I don't have time to go through the interesting technical details,  that this repeated shortcut algorithm does have the bound that Griner claims, and it's  simpler than his algorithm, so why not use it?  This is the worst case, log squared.  You can prove an average case bound for this algorithm, too, average case in the following  sense.  If the vertex numbers are random, uniform random numbers, the log n and the inner loop  turns into a log log n.  The trees turn out to be balanced to begin with, and these are upper bounds.  This is a worst case bound, but this is not, and it might be that this thing has an average  case behavior that's logarithmic.  This algorithm R matches the log n bound of the Shalouk-Viskan algorithm, simpler.  We had to use a variant of, now this is our book on Shalouk, which had a follow-on to  the Shalouk and Vishkan paper.  We use ideas from their analysis, but the interesting thing is you have to look at what  happens over multiple rounds, because you have to deal with these flat trees that are  just sitting there for a while.  The analysis is pretty interesting.  In algorithm A, we can prove a log squared bound as well, and I have no idea whether  this is tight or not.  In algorithm C, which I mentioned, I hope has the same bound, but it differs in subtle  ways from this algorithm, and I can't prove anything about it.  So is log n best possible?  Well, in fact, no.  This is still an ongoing field of research for the new version of the theoreticians.  People have been trying to get to log d.  There was a result presented in 2018 that gives a complicated algorithm in a powerful  distributed model that allows sorting in constant time, and the bound is log d, that's the diameter  times some log log that depends upon n and the density.  This algorithm doesn't need this powerful model.  You can implement this on a PRAM with arbitrary right conflict resolution.  Using, essentially, just hashing.  Stop now.  Yes, okay.  And this has been further improved to log d plus log log n.  Last comment.  I'm assumed global synchronization here.  What happens if you have only local synchronization or total asynchrony?  Proving resource bounds gets really challenging, but we do have some work on disjoint set union.  Union find in the concurrent setting.  And with that, I'll say thank you very much.  Thank you very much for a great talk.  Even if you are running slightly over time, we take the time for a question from the young  researchers.  Is there one in the back there?  Hello.  I might miss something, but from my understanding, in each step, you are having two competing  factors.  One is you want to keep the flat trees not very, so not increase the depth of the flat  trees.  And the other thing is you want to combine these trees sufficiently fast.  But if you're aiming for log n factor, instead of making the diameter one for each time in  the flat tree, couldn't you just leave them at log n?  Wouldn't it make it slightly faster at least?  Can you repeat what you just said?  So in each step, if you want to create a flat tree, you could leave the depth of the flat  tree as something like log n rather than making the diameter one.  Then the edges are still left at the fringes.  And if you're restricting your connection to the roots, you have to still get that information  down to the roots for the next connect step.  So I don't see how that would work.  And in any case, if you want to go from n to log n by having, it's going to cost you  constant log n in any case if I'm not mistaken.  But we can take this offline, perhaps.  Thank you.  Okay.  If there are no further questions, let's thank...  Oh, there is one back in the back.  Yes, all the way in the back.  Hello.  Thanks for the nice talk.  I have a question that new tools of Apache Spark like GraphX, it deals with both complex  as well as big graphs.  So does your theory means these things are implemented, implementable to their type of  framework also?  I'm trying to work with practitioners to get these ideas implemented, getting theory into  practice as a slow process.  But these algorithms are simple enough, they should be implementable on any parallel platform  whatsoever without too much trouble.  That's what I think.  Okay.  Let's thank Bob Tajan once more.  Thank you.
7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_0_71.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_72_191.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_192_239.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_240_335.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_336_491.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_492_551.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_552_1367.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_1368_4307.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_4308_6119.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_6120_7259.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_7260_8039.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_8040_10523.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_10524_11879.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_11880_12335.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_12336_13043.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_13044_14783.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_14784_16343.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_16344_17783.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_17784_18983.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_18984_20195.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_20196_22055.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_22056_22163.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_22164_22703.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_22704_22883.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_22884_23135.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_23136_23867.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_23868_33935.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_33936_35183.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_35184_35231.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_35232_35291.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_35292_36791.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_36792_38327.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_38328_39371.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_39372_40907.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_40908_40979.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_40980_41147.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_41148_41651.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_41652_42059.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_42060_42611.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_42612_42911.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_42912_44675.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_44676_46619.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_46620_47243.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_47244_49127.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_49128_49559.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_49560_49631.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_49632_50267.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_50268_51743.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_51744_52655.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_52656_53003.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_53004_53315.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_53316_55595.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_55596_57371.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_57372_59411.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_59412_59543.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_59544_59663.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_59664_60743.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_60744_63107.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_63108_63695.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_63696_65315.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_65316_67967.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_67968_68099.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_68100_69479.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_69480_69899.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_69900_70283.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_70284_74111.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_74112_74219.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_74220_74351.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_74352_74483.png 7th_HLF___Lecture__Robert_Endre_Tarjan_jKtLiqb1JvI_74484_74567.png
So, our next speaker will be Bob Tarjan, who is a professor at Princeton University. He belongs to a very distinguished group of scientists who has received a award from the computer science community and the math community. We heard, as far as I know, the only other member of this distinguished group, Leslie Valiant, talked yesterday. And Bob Tarjan received the Neville-Lenna Prize in 1982 and the Turing Prize in 1986. So Bob, the floor is yours. Good morning. Thank you. I'm hoping for a little audience participation. There will be a few places in my talk and at the end I would love to get some questions from the young researchers on my talk or any other subject that you're interested in. Terry Pancake mentioned in the opening ceremony that the Turing Award is given for work with a 25-year horizon. So John Hopcroft and I got the award in 1986 for work on, fundamental work on data structures and algorithms. How many of you young researchers were alive in 1986? Okay. So 25 years before 1986, that was 1961. I did not do this work in 1961. In 1961, I was in the eighth grade in junior high school. But I had a wonderful math teacher who was teaching us pianos, axioms, and abstract algebra, which was kind of the new math, but this was before the new math got introduced in the U.S. and completely failed, but it was a catnip to this cat. But so now I'm going to talk about concurrent connected components. But let me be, so I've been in this field for a long time. This is going to be recent ongoing work, hopefully us old fogies can still contribute a bit. But before I talk about this, I want to make a few observations based upon my own experience. So computer science is quite a young field, especially compared to mathematics or physics. It's been running for maybe 50 years, maybe a bit longer. We found a number of beautiful, theoretically efficient algorithms, developed beautiful theories of complexity. But there's a gap between theory and practice. Many of these algorithms have yet to be used because they're complicated or for other reasons. And if they're not correctly implemented, they can fail. If the engineers who are trying to implement the algorithms can't implement them correctly, and this is a subject that Leslie Lamport, for example, knows all about, disaster happens. And furthermore, our theoretical notions of efficiency do not necessarily correlate with what happens in the real world. Often very simple methods suffice, even though they may have worse theoretical performance. So what is going on here? Well, we know that software developers' human time is much more precious than machine time. If you're faced with a deadline, you choose the simplest solution that works, or that seems to work. And software developers may have learned some theory in school, and they try to apply it, maybe, but then maybe they oversimplify it and they get it wrong. Or they may build their own solution based upon ideas that they've seen and then provide some efficiency analysis, and maybe that is wrong because they're not theoretically trained and they don't have the time to work out the details. Now what is our challenge as theoreticians to try to respond to this real world phenomenon? I think it's very important to develop and analyze simple methods. The algorithm has got to be simple enough that somebody can actually program it and use it in practice. The analysis, the justification, even the proof of correctness can be arbitrarily complicated, but the algorithm has better be simple. So my research goal, generally speaking, especially these days, is to try to develop simple algorithms, I'll call them reference algorithms. Paul Erdos was a famous mathematician who had many interesting ideas, but one of them was proofs from the book. This is the book Up in the Sky, the perfect proof, if you will. So can we develop algorithms of the same type, algorithms from the book, as simple as possible, provable resource bounds for important input classes and efficient in practice. Now computers, notwithstanding the tailing off of Moore's law, keep getting faster and faster and memory sizes keep getting bigger and bigger, and this creates a massive design space for choosing possibilities for algorithms. Computer science, again, is a young field. People have plucked the low-hanging fruit, but there are places where maybe they didn't find the best solution. So let's try now to look at some of these important basic problems, systematically explore the design space and see if we can say something. This something like this quote was attributed to the design sign. Let's make everything as simple as possible, but not oversimplify. All right, so let's take an example that I hope will illustrate some of these points, the connected components problem. This is perhaps the most basic problem in graph theory. We've got an undirected graph, which just consists of a bunch of vertices connected by edges. Two vertices are connected if there's a path between them. A connected component is just a maximal set of pairwise connected vertices, and our problem is to compute the components. So now audience participation time number two. How many connected components? Three, anybody else? Good. Okay. One, two, three. That was pretty easy. How many connected components? Good. These four vertices are connected. All of these vertices are connected. All of these vertices are connected. No way to get from here to here or to here. Excellent. How many connected components? Take a guess. Three. Three is the answer. So here's an example. I mean, humans are very good if things are spread out, right? But everything is overlapping, and a computer could do this easily, but maybe not a human. All right. How are we going to address this problem algorithmically? You call it the others differently. Thank you, wit. We need a way to represent the solution. So the representation is going to be a label for every vertex such that two vertices in the same component have the same label. And we'll require that the labels be vertices in the component. So we want to label every vertex in a component with a single unique vertex, call it a canonical vertex. And then we can easily test for any two vertices if they're in the same component or not. I'll use little n to denote the total number of vertices, little m to denote the number of edges. And we'll assume that the vertices are just numbered from one to n, or they are the numbers from one to n, the integers from one to n. And one useful labeling to think about is the minimum labeling, where every vertex is labeled with the minimum vertex in its component. And I'm going to use this very simple graph with one component consisting of all the vertices, one through seven, as sort of a running example. So the minimum vertex in the component is one. This is the labeling. So these are the vertices, each one labeled with label one. Now another way to represent a labeling is this is just a function from the vertices to the vertices. And we can represent this, forgive my poor use of PowerPoint, but the red arrow is denote the function value. So there's one fixed point here at one. This is the canonical label. This is just a function. And this is the solution to our problem. We want a labeling for every component. Now it's easy to compute connected components sequentially, that is one step at a time, and there are two classical ways of doing this. The first is to use graph search. Any kind of graph search will do breadth first search, depth first search. So breadth first search, for example, we start at an arbitrary vertex. We go to all adjacent vertices from there to all adjacent vertices and so on. And we can't get anywhere else. We've explored an entire component, and then we start from another unvisited vertex and repeat. Depth first search, we proceed along a path until we get stuck and we have to back up. That's a different kind of search. There are lots of kinds of search. Any one of them will solve this problem in time linear in the graph size. Another approach is to turn the problem into a data structure problem. We use a so-called disjoint set or union find data structure, which does the following. It allows us to maintain a collection of disjoint sets, each initially a singleton, and each of which has a canonical element. And we're allowed two operations. A unite operation, which given two elements, if they're in different sets, combines the sets into one. If they're already in the same set, the unite operation does nothing. That's the update. And the find operation returns the canonical element of the set containing the element x. So if we have some implementation of these two operations, this data structure, it's easy to solve the connected component problem. We just iterate over all the edges. And for each edge, we unite the endpoints. And that's going to put all the vertices in each connected component into one particular set. The underlying data structure is picking the canonical elements. And then we do a second loop that returns the labels, which are just the results of the find operation. Now notice here that we don't actually have to execute this second loop. We can use the find operation to give us the values if we want to do a test whether two vertices are in the same component or not. Now graph search solves the problem in linear time. And it turns out that if you implement the union find operations in a nice way, you get a solution that is almost linear time. There's an extra factor here of what I'll call alpha. This is the inverse of Ackerman's function. For those of you who know Ackerman's function, it's a very simple data structure with a very complicated running time. And there's a whole additional story here that I'm not going to tell. But for all practical purposes, this is a constant. A nice thing about this, the use of the data structure here is that you don't have to build a representation of the graph. All you need is the edge set, the lists of pairs of vertices. And also you can do updating. You can do arbitrary insertions of new edges into the graph and update the connected components as you go. You get extra flexibility here. Now the obvious question to ask is what happens if you want to support edge deletions as well as insertions? That's another story that I'm not going to talk about here. Well, good. Is this the end? How about really big graphs? So it's amazing the kind of things you can find on the web. CLM stands for product lifestyle management. So this is a graph of various products and their path through their life cycle somehow. This one, I believe, is proteins that interact with each other. Here's some, this is some kind of a friendship graph. Think of the Facebook graph. So how big is big now? With the advent of the worldwide web, Facebook, Google, and so on, people want to solve problems like this and in particular find connected components on grass with billions, at least billions of vertices and trillions of edges. For such problems, even linear time might not be fast enough. So can we do better? And in particular, can we go beyond sequential algorithms? Can we use parallelism or concurrency to speed up the computation? So let's think about this in a big way. Lots and lots of processors, constant processors per edge. So the algorithms that I'm going to be talking about, we think of one or two processors per edge and a few processors, one processor per vertex. What is the computation model here? Well there are two possibilities and I'm not going to go into great detail in the models. The so-called PRAM parallel random access machine where there's a global common memory and a bunch of processes that are allowed to access the common memory and they each have some small amount of private memory. So common memory model. The issue with PRAM model, there are many issues, but one of them is do you allow concurrent reading and what happens on concurrent writing? How do you resolve right conflicts? I'll come back to that point in a minute. Another model, the one that's, so the PRAM model goes back to the 80s at least and was the favored one of the theoreticians. The more recent model is a distributed memory model. Think of Hadoop or MapReduce, computing in the cloud, it's all about message passing. So here the memory is distributed, every process has its own memory and it's sending messages to other processors and getting information back. So we think about a process for each vertex and each edge and they're sending messages back and forth. I'm going to describe some very simple algorithms that can be implemented in either of these models. So here's a naive algorithm of the kind I want to think about. This is just label propagation. For convenience, I'm going to replace every edge, this is an undirected pair here, by two directed copies, directed arcs. So this goes from V to W and this goes from W to V. This is just to simplify the notation here. So how does this work? We initialize that I'm going to use V.p, p for parent, I'll come back to this point in a minute. This is going to be the label of a vertex. I initialize every vertex to have its own itself as a label. Then I iterate over the arcs and I update the parents by replacing the old parent by the minimum of the ends of the parents of all the adjacent arcs. We'll see the example, a worked example on the next several slides. So the PI values are the current values, the I plus one values are the new values. We keep doing this until nothing changes. The final set of parents is the result of the computation. So we got three lines of initialization. V.p is the parent or the label. This loop runs synchronously in parallel. So every arc is doing the same thing at the same time. That means there may be several values getting written into the new parent simultaneously based upon multiple arcs. So I'm allowing concurrent reading to get the values. And I'm also allowing concurrent writes. And I'm assuming that write conflicts are resolved in favor of the smallest value that's encoded by the min here. And the fact that I put in these subscripts, this guarantees that you could actually run this sequentially if you wanted to and it would be correct and everything works. But if you were actually going to implement this on a PRAM or a distributed model, you would want to do an appropriate replacement of this pseudo code by real code. So on the PRAM model, for example, every arc would read the parents of both ends and then try to write the appropriate value into the other one. In the message passing model, each vertex would send its parent to all the arcs and then the arcs would do something and send information back to the parents. I won't go into the details. I hope the algorithms will be straightforward enough that you can think about how you would implement these if you wanted to do it. All right, so here's the label propagation algorithm run on this example. Everybody starts out self-labeled. And now the 7, 6 arc allows us to update the parent of 7 to be 6, but 5 is also a candidate. So 7 is going to end up with label 5. 5 has two possibilities. 3 and 7. 7 is bigger, so it drops out. But 5 gets 3, 3 gets 2, 6 gets 4, 4 gets 1. And this is the picture. So instead of a whole bunch of self-loops, now we've got two paths, actually. And we've decomposed things into two pieces somehow. And now things progress. These vertices start improving toward 2, and these vertices start improving toward 1. And you've got to wait for a while because the answer for all of them is supposed to be 1. But eventually, 6 points to 1, and then 7 gets 1 as a candidate, and then 7 is going to get pulled off. 5 will get pulled off. 3 will get pulled off, and 2 gets pulled off at the end. And I'll go through this quickly here. And we end up with the ultimate solution after some number of steps. Now this is a highly parallel algorithm, but it's not very efficient because this graph has large diameter. The diameter, the maximum number of edges on the shortest path, is essentially the size of the entire graph. So this algorithm, in effect, it's doing concurrent breadth-first search from all the smallest vertices in the components plus some extra work. It's highly inefficient, although it has been proposed in practice. But it does have the property that if you run this on your most parallel computer with huge resources up in the cloud, you can still beat it on a relatively small PC with a depth-first search, let us say. So not so good. But this is the first step. So let's try to do better. How can we improve this algorithm? How can we deal with the high-diameter situation? There's a wonderful idea that goes by several names. I'm going to call, oh, wait. We'll get there. Let me talk about this notion of why do we want to think of labels as parents? I've kind of illustrated this in the picture. So if we think of the pairs of vertices and their labels, parents, as being arcs, this defines a directed graph. Every vertex has out-degree exactly one. This is like a function. If the only cycles in this graph are self-loops, then we get a set of rooted trees, where this really is the parent in the rooted tree. So we're really manipulating a collection of trees. The connect steps are kind of hooking trees together or breaking a subtree off and putting it someplace else. But the side effect of connecting is we get deep trees. We have to somehow compensate for the deep trees. And the way we'll do that is by using this shortcut operation that goes by other names, as I said. So this simultaneously concurrently replaces the parent of each vertex by the grandparent. And it roughly halves the depths of all the vertices. So if you do a logarithmic number of shortcuts, you will squash all the trees. And I'll call a tree flat if it's just got a bunch of children and a root. And that is our ultimate objective, to create a flat tree for each component, one tree per component. So we might get from linear number of parallel steps down to logarithmic number of parallel steps. Here I said log n, but one might actually hope for log d. But can we do that? And what are algorithms going to look like? So we've got this notion of connection based upon edges or arcs and short cutting. We're going to put them together. So now I want to consider several algorithms based upon these principles. Each algorithm is going to do a collection of rounds. And every round is going to consist of looking at the arcs and changing parents, doing some kind of a connection. And then doing one or more shortcuts, and then possibly something else, and changing the edges to make things simpler. All right. So a connect step is going to update the parents based upon the arcs. Short cut is going to replace parents by grandparents. An altar is going to replace arcs. There are several different ways to do the connection. What the label propagation algorithm did was one kind of connection. And I'm going to look at sort of the two extreme cases, which I'll call direct connect and parent connect. So direct connect, you look at every arc and you replace the smaller parent. So W is a candidate for the parent of V and vice versa, because we've got arcs going in both directions here. Parent connect looks one step deeper into things. So if we have an arc VW, this is replacing the parent of the parent. This is the new parent of the old parent, and the candidate value is the parent of the other end here. All right. So we've got shortcut. We're going to use one or the other of these forms of connection, and I'll come to a couple more in a moment. And here's what we do with the arcs. We replace each arc by an arc between the parents of the two vertices. But they are different. If the parents are the same, we just throw the arc away. So that's the arc alteration step. There are other possibilities to do arc updating that have some properties. These are sort of opposite approaches. One is to try to delete arcs, to sparsify the graph so you don't have as many arcs to work with. And you'll notice that this arc alteration does some kind of sparsification because when an arc becomes a loop, it gets thrown away. I should also say that this can create multiple arcs which we process, and they're harmless to the algorithm, although maybe not to the notation, shall we say. Okay. Or we can densify. We could add arcs to try to connect things together even more, sort of a more global form of short cutting. So here is our first algorithm, which I'll call Algorithm C for Connect. It repeatedly does the parent connect step and the shortcut step until no parent changes. Very simple algorithm. I wish I could say something about how efficient it is. I have no useful information, no useful theory on this one, which is odd because it's so simple, right? Here's another one. This one uses arc alteration, and it replaces the parent connect step here by a direct connect, and then it does a shortcut, and then it does an alter. So if we want to use the simple form of connection, we have to use this edge altering process because otherwise you immediately get stuck and you don't make progress. This one I'm going to try to illustrate. This one we can prove interesting things about. And I should say it was on the title slide. This is joint work with my grad student Cliff Liu at Princeton. So here we go. Here's the initialization. Now the first step is just like the first step of label propagation, and this is a little bitter drawing of what the parent arcs look like. But now we do the shortcutting step. So the shortcutting step is going to make 6.1, 7.3, 5.2. And now we do the arc alteration step, which is going to get rid of a bunch of arcs here, in fact, and leaves us only with the... So this is actually two arcs. This is one edge. This is a 3-1 arc and a 1-3 arc and a 2-3 and a 3-2. So this is the state after one round of this algorithm. We've got two trees, and they got squashed by the shortcutting. This tree is flat. Everybody is either the root or it points to the root. This one, there's still a path of length 2 here. And this thing eventually finishes. And it looks like it doesn't finish much faster than the label propagation algorithm, but if you look at bigger examples, it really is much faster, and we can prove nice bounds about it, which I'll come back to. But before doing that, nice algorithm, simple algorithm, does it have possible disadvantages and how might we overcome them? Well, it's maintaining trees because the labels only decrease, and all the algorithms I will present here are computing the minimum labeling. But it can, in fact, in the connect step, it can break a subtree off of one tree and reattach it to another tree if it thinks things are improving locally. That's a kind of a non-monotonic process, and we might think that that's kind of going sideways instead of making progress. We'll call an algorithm monotonic. If it doesn't, in fact, split trees. If you want our algorithm to be monotonic, we have to make sure that when we're connecting, we only change the parents of roots. So let us modify the connect steps to only change parents of roots. That gives us, in the parent case, we get this. So this is a test which basically says I'm only going to change the parent of a root in this connect step. So if my parent is my grandparent, the parent is a root, and only then am I allowed to do the corresponding update. And I notice I didn't put the subscripts in here. So here is algorithm R for root connect. This is like algorithm C except that we restricted the connect step to roots. And this one we can prove quite nice bounds for. And there's a variant of this algorithm that replaces this by a direct connect, parent-direct connect alter, a different algorithm, interestingly, but with more or less the same properties. You can imagine the combinatorial explosion when you start putting these sorts of things together in different ways. But let's focus on these few. Now there's still a possible drawback of these algorithms. The connect steps are producing these deep trees. And the shortcutting process is gradually making the trees flatter. But especially if we're only connecting roots, we got to wait till things get flattened out before the edges accumulate down near the roots, and we can actually hook trees together. So how can we overcome this delay by repeatedly doing shortcuts? Now a shortcut takes one process per vertex, whereas a connect step takes one process per edge. So it is perhaps reasonable to do more shortcuts per iteration. Several shortcuts or even a non-constant number of shortcuts per iteration. The extreme would be every time we do a connect, we then shortcut to make the trees completely flat. And here is an algorithm that does that, algorithm S. Once you, so this has two loops. There's an inner loop that repeatedly shortcuts to completely flatten the trees. And in between, we do the parent connect. So we're always operating on flat trees. And we don't have to test for roots, because this is now guaranteed only to connect roots. So we've got three algorithms I want to focus on. Algorithm A, algorithm R, and algorithm S. And there's algorithm C that I can't say anything interesting about. History is simple, but they seem to be new, all these algorithms. They're simpler than the ones in the existing literature. And I would welcome citations to show me otherwise. The question we want to answer is how many steps do these algorithms take? How many parallel steps? How many rounds? Before I address this question, let me talk a little bit about history. So the first era of working on parallel algorithms, this was the theoreticians roughly from the 1980s to the 2000s. The machine model was the parallel random access machine or some flavor of this model. And the goal as the typical goal of theoreticians is to maximize the efficiency, minimize the parallel time and the total work, which is the number of processors times the parallel time. Even if the algorithm is complicated. The triumph in this field was a beautiful but complicated algorithm of Halperin and Zwick, and actually there are two versions of it. Logarithmic number of parallel steps, sublinear number of processors, which means that the total work is linear, giving a concurrent algorithm that is as efficient as a search-based solution, a sequential solution. And this algorithm throws everything, including the kitchen sink that people knew from this field at this problem, I would say. Randomized, it's in the exclusive read, exclusive write model. So there's no write conflicts and no read conflicts, which is even more astonishing. Nobody knows if it can be de-randomized or not. The algorithms that I've described are very simple deterministic algorithms. Now the second era, roughly 1990s to the present, people actually wanted to solve, this is the internet, right? People wanted to solve this problem on very large scale graphs. They started looking at parallel algorithms, notably in the distributed model based upon new distributed computing frameworks that we are familiar with. And the goal here was to actually get something fast in practice, simple enough that it could be implemented by a competent programmer. The people who worked in this area read some of the literature, at least the early PRAM literature, made claims like not implementable or too complicated, which is not really true. So they invented their own algorithms with some hand-wavy and sometimes flawed proofs of resource bounds. So the question here is to try to come up with simple methods for which we can prove things so that the practitioners can use these ideas and have good performance with some guarantees. Okay. So where did our algorithms come from? But algorithm R, this root connect algorithm, can be thought of as based upon a classical paper by Shalok and Vishkin published in 1982. They operated in the more standard model where right conflicts, you know, you can't predict which right wins. Arbitrary resolution of right conflicts. This is a weaker model. It maintains trees. It doesn't move subtrees around so it has this monotone property. It doesn't do minimum labeling. It does two shortcuts per round, although they claim that this is not needed, although they claim it simplifies the analysis. And they put some extra complications in there, extra steps to guarantee that every round, the difficulty with this sort of algorithm is you can have a tree that gets flat and then it just, it's connected to other trees, but it sits there for a long time before it gets connected to something else because the connections to other trees are deep in the other trees and they have to get flat before anything happens with the flat trees. So they added some extra steps to get around this problem. They did prove a logarithmic bound, which is kind of our goal here, not so simple analysis. And they showed that a simplified version of their algorithm that notably doesn't have these extra steps doesn't work so well. It's like label propagation. But this example relies on their right conflict resolution assumption. And if you reinterpret this algorithm R that I presented for this model, it doesn't work. So the point is we're changing the model here, we're strengthening the model to something that is perfectly reasonable in this day and age. We get a simpler algorithm, but to get it, we need this stronger right conflict resolution. So this is maybe a reason nobody talked about this algorithm back in the PRAM days. This algorithm S doing repeated shortcuts. Then in the late PRAM era, shall we say, Griner did some experiments with many algorithms. There were early parallel machines, the connection machine, for example. And people got excited to try to play with these things. And he devised an algorithm that does repeated shortcuts. It uses direct connect and edge alternation. But he was worried about this problem of delayed connection of these trees. So his solution to this was in alternate rounds, instead of taking minimum values, you take maximum values. So the intuition here is that you do logarithmic shortcuts that flattens the tree. That's the cost of the inner loop. If every tree gets combined to some other tree, every iteration or every other iteration, you have the number of trees in each iteration. In the outer loop, that's going to give you a log squared bound. That's what Griner claimed. This algorithm is used in practice. The GPU people seem to be particularly enamored of it. Turns out to the best of my ability to interpret this algorithm, this bound is not correct. This thing, in fact, has this bound, and even a very simple example, kills this thing. So this is kind of astonishing to me. So young researchers read the literature skeptically. There are opportunities there. Prove results for yourself. Look for gaps. Okay, now there's one more algorithm which is algorithm A, and I'm already out of time here, so I better speed up. This is how I got started on this problem. Costas tutsuclis, my pardon to the Greeks in the audience. He was a PhD student a long time ago of mine, and these guys all worked at Yahoo, which is now Oath, they built an interesting parallel computing platform that they called Thronos, and they devised their own connected component algorithm, and algorithm A is in effect a simplification. They did a hand-wavy proof of log n bound here. The proof is not right. The proof makes no sense. I don't have a counter example for this one. This algorithm may in fact run in this many steps, but so does algorithm A, and it's considerably simpler, and this actually is the paper that got us started on this work. So we can prove, and I don't have time to go through the interesting technical details, that this repeated shortcut algorithm does have the bound that Griner claims, and it's simpler than his algorithm, so why not use it? This is the worst case, log squared. You can prove an average case bound for this algorithm, too, average case in the following sense. If the vertex numbers are random, uniform random numbers, the log n and the inner loop turns into a log log n. The trees turn out to be balanced to begin with, and these are upper bounds. This is a worst case bound, but this is not, and it might be that this thing has an average case behavior that's logarithmic. This algorithm R matches the log n bound of the Shalouk-Viskan algorithm, simpler. We had to use a variant of, now this is our book on Shalouk, which had a follow-on to the Shalouk and Vishkan paper. We use ideas from their analysis, but the interesting thing is you have to look at what happens over multiple rounds, because you have to deal with these flat trees that are just sitting there for a while. The analysis is pretty interesting. In algorithm A, we can prove a log squared bound as well, and I have no idea whether this is tight or not. In algorithm C, which I mentioned, I hope has the same bound, but it differs in subtle ways from this algorithm, and I can't prove anything about it. So is log n best possible? Well, in fact, no. This is still an ongoing field of research for the new version of the theoreticians. People have been trying to get to log d. There was a result presented in 2018 that gives a complicated algorithm in a powerful distributed model that allows sorting in constant time, and the bound is log d, that's the diameter times some log log that depends upon n and the density. This algorithm doesn't need this powerful model. You can implement this on a PRAM with arbitrary right conflict resolution. Using, essentially, just hashing. Stop now. Yes, okay. And this has been further improved to log d plus log log n. Last comment. I'm assumed global synchronization here. What happens if you have only local synchronization or total asynchrony? Proving resource bounds gets really challenging, but we do have some work on disjoint set union. Union find in the concurrent setting. And with that, I'll say thank you very much. Thank you very much for a great talk. Even if you are running slightly over time, we take the time for a question from the young researchers. Is there one in the back there? Hello. I might miss something, but from my understanding, in each step, you are having two competing factors. One is you want to keep the flat trees not very, so not increase the depth of the flat trees. And the other thing is you want to combine these trees sufficiently fast. But if you're aiming for log n factor, instead of making the diameter one for each time in the flat tree, couldn't you just leave them at log n? Wouldn't it make it slightly faster at least? Can you repeat what you just said? So in each step, if you want to create a flat tree, you could leave the depth of the flat tree as something like log n rather than making the diameter one. Then the edges are still left at the fringes. And if you're restricting your connection to the roots, you have to still get that information down to the roots for the next connect step. So I don't see how that would work. And in any case, if you want to go from n to log n by having, it's going to cost you constant log n in any case if I'm not mistaken. But we can take this offline, perhaps. Thank you. Okay. If there are no further questions, let's thank... Oh, there is one back in the back. Yes, all the way in the back. Hello. Thanks for the nice talk. I have a question that new tools of Apache Spark like GraphX, it deals with both complex as well as big graphs. So does your theory means these things are implemented, implementable to their type of framework also? I'm trying to work with practitioners to get these ideas implemented, getting theory into practice as a slow process. But these algorithms are simple enough, they should be implementable on any parallel platform whatsoever without too much trouble. That's what I think. Okay. Let's thank Bob Tajan once more. Thank you.
my talk or any other subject that you're efficiency do not necessarily correlate with what develop and analyze simple methods. The algorithm problem. This is perhaps the most basic problem in graph theory. We've got an undirected graph, components sequentially, that is one step at a one of them will solve this problem in time data structure, which does the following. It easy to solve the connected component problem. We component or not. Now graph search solves the constant. A nice thing about this, the use of the connected components on grass with billions, at to speed up the computation? So let's think about title slide. This is joint work with my grad the total work is linear, giving a concurrent it can be de-randomized or not. The algorithms this is the internet, right? People wanted to distributed computing frameworks that we are the new version of the theoreticians. People have