A key concept in the theory of distributed computing is locality: if I am a node in the middle of a large graph, how far do I need to see in order to pick my own part of the solution? A modern, effective technique for studying such questions is called round elimination.
With round elimination, one can turn any local graph problem into a new graph problem that is strictly more localized: if problem can be solved so that each node needs information only within distance , then problem can be solved so that each node needs information only within distance . Round elimination is a mechanical procedure that can be fully automated: one can enter the description of to a computer program and out comes the description of .
One particularly interesting phenomenon is that some problems are fixed points for or , that is, we have got or . Whenever this happens for a nontrivial problem, we immediately know that cannot be solved locally—this is a quick and easy way to prove lower bounds on the locality of many graph problems. In this short article I will give a brief introduction to the round elimination technique and its key applications.
1. Introduction
Locality of graph problems. Imagine you are a node in the middle of a large graph. Together with all other nodes, you will need to solve some graph problem, in a distributed manner: you will need to output your own part of the solution. For example, if we are interested in the vertex coloring problem, each node has to output its own color, and the local outputs have to form a proper coloring for the entire graph: adjacent nodes have to output different colors.
A key concept that the theory of distributed computing studies is locality: how far does each node need to see in the graph to pick its own part of the solution. If you are only aware of yourself and know nothing about the structure of the graph, there is not much you can do. And if you see the entire graph, then you have got enough information to solve any graph problem. But what happens between these extremes?
Which graph problems can be solved based on constant-radius neighborhoods? For example, what can you do if you see up to distance 3 in the graph, as shown in the above figure? What about slightly super-constant neighborhoods, e.g. radius or ? And which problems are inherently global and require you to see almost the entire graph in the worst case?
How to study locality? The study of locality was initiated by Linial (1987, 1992) in the late 1980s, but what was lacking for a long time was systematic techniques that can be applied to a broad range of graph problems. Until recently, the main technique that the researchers used to study the locality of graph problems was, in essence, thinking hard.
There is a small number of specific graph problems whose locality has been well-understood already for a long time, see, e.g., Linial (1987, 1992), Naor (1991), and Kuhn et al. (2004, 2006, 2016). However, what do you do when you encounter a new graph problem nobody else has studied before?
We do not yet have a complete answer that could be applied to any given graph problem. However, many graph problems of interest are locally verifiable: if the solution is not feasible, at least one node will notice it immediately by looking at the solution in its own local neighborhood. For example, vertex coloring is by definition locally verifiable: if a coloring is not proper, then there is a node that is adjacent to another node with the same color. And whenever we have got a locally verifiable problem, there is now a mechanical technique that we can try to use: round elimination.
Round elimination. Round elimination is based on an old idea that was already used by Linial (1987, 1992) in his lower bound for the locality of vertex coloring, but for a long time it seemed to be just an ad-hoc trick that is applicable to one specific problem. However, in the past four years it was discovered that the same idea can be generalized and applied to study any locally verifiable problem (Brandt et al. 2016, Brandt 2019, Olivetti 2020).
Informally, round elimination is a function “” that maps a locally verifiable graph problem to another locally verifiable graph problem . Round elimination will make problems strictly more local in the following sense:
If has a (sufficiently small) locality , then has locality .
Round elimination turns a problem into a more localized problem .
Here, “locality ” means that can be solved (for the worst-case inputs) if and only if all nodes see up to distance in the graph.
Round elimination is a mechanical process—there is even a freely available computer program (Olivetti 2020) that is happy to calculate for any given problem , and we will also soon see how to use it.
Significance of round elimination. Now even if we can apply round elimination to a given graph problem , it does not mean that we will be able to immediately prove tight upper and lower bounds for the locality of . The whole procedure may seem a bit pointless at first: if we do not understand the locality of , why would it be helpful to construct another problem that we do not understand either?
However, as we will see soon, sometimes we are lucky and a mechanical application of round elimination immediately gives a tight lower bound. For example, some problems are fixed points or period-2 points in round elimination, that is, we have
and whenever this happens we immediately get a lower bound result—more about this soon!
We are currently seeing more and more examples of results in which round elimination has played a key role, see, e.g., Brandt et al. (2016), Balliu et al. (2019, 2020a, 2020b), and Brandt and Olivetti (2020). We have recently systematically explored large families of graph problems, and round elimination has been an essential tool that has made it possible to make rapid progress.
In this short article I will give a brief overview of the round elimination technique and some of its key applications; I will use the sinkless orientation problem as a running example to illustrate the key ideas.
2. Example: sinkless orientation
Problem definition.Sinkless orientation is the following graph problem:
Given an undirected graph , orient all edges such that each node with degree at least 3 has outdegree at least 1.
(a) Graph . (b) A sinkless orientation for graph . (c) A simple centralized algorithm for finding a sinkless orientation: find a cycle and orient it consistently (orange), orient all other edges towards the cycle (blue), break ties arbitrarily (gray).
That is, high-degree nodes cannot be sink nodes. It is easy to see that such an orientation always exists, and there is a very simple centralized algorithm that finds such an orientation (w.l.o.g. assume that is connected):
If contains a cycle , first orient all edges of in a consistent direction (this way all nodes in will have outdegree at least 1 and hence they are happy). Then orient all other edges towards , breaking ties arbitrarily (this way all other nodes will also have outdegree at least 1, as there is at least one incident edge that points towards ).
Otherwise is a tree and there is a node of degree at most 1; then orient all edges towards (this way all nodes except will have outdegree 1).
Locality of sinkless orientation. The above algorithm is inherently global. Furthermore, it is unnecessarily global: the above algorithm will also ensure that nodes of degree 2 have outdegree at least 1, while this is not required in the problem definition. Maybe we could find a much more local solution to this problem?
This is indeed the case; it turns out that the locality of this problem is only for randomized algorithms and for deterministic algorithms (Ghaffari and Su 2017). The general case and the randomized algorithm are more complicated, but it is easy to see that at least in the case of trees the locality of the problem is . We describe the distributed algorithm from the perspective of an individual node with :
Node finds the nearest node such that (breaking ties arbitrarily). Note that such a node has to exist within distance in any tree with nodes.
Let be the unique edge incident to that points towards .
Node will announce that is oriented from to . Note that there are never conflicts: node will not announce that is oriented from to .
Finally, if there are some unoriented edges, orient them arbitrarily. This will ensure that all edges are oriented and, if a node has degree at least 3, it successfully orients at least one of its incident edges away from itself. Furthermore, each node only needs to see up to distance .
Models of distributed computing. The above idea can be implemented as a concrete distributed algorithm in many models of distributed computing, but for our purposes it is sufficient to note that it works in each of the following models:
Port-numbering model: For each node, there is a numbering of its incident edges, and for each edge, there is a numbering of its endpoints. We can refer to the 1st neighbor, 2nd neighbor, etc. of each node, and we can refer to the 1st endpoint and the 2nd endpoint of each edge. The port numbering comes from an adversary, and it is completely arbitrary: for example, if is the 1st neighbor of , it does not mean that has to be the 1st neighbor of .
Deterministic LOCAL model: The nodes are labeled with unique identifiers. If there are nodes, the unique identifiers are natural numbers between 1 and . The unique identifiers come from an adversary.
Randomized LOCAL model: Each node has a source of independent random bits, and the solution is correct w.h.p.
(a) Port-numbering model; here the numbering of the endpoints of each edge is represented with arrows and the numbering of the incident edges of each node is represented with numbers 1–3. (b) Deterministic LOCAL model; the numerical labels of the nodes are their unique identifiers.
We have been discussing here locality but we can equally well study the round complexity of message-passing algorithms: if we imagine that each node is a computer and each edge is a communication link, in synchronous communication rounds each node can gather full information about its radius- neighborhood and nothing more. Hence we can use the terms “locality” and “round complexity” (or distributed time complexity) interchangeably.
Lower bounds on the locality? Good, so far we know that the locality of the sinkless orientation problem is at most . But is this the best that we can do? Now we are getting closer to our topic.
We will use round elimination to show that, even if we are looking at trees, the sinkless orientation problem cannot be solved in the port-numbering model with locality , or, equivalently, in rounds. This may sound like a weak statement, as it only applies to the port-numbering model. However, it turns out that proving a lower bound in the port-numbering model is the key step. As we will discuss in more detail in Section 6, tight bounds in the other models follow:
In the randomized LOCAL model the locality is at least (Brandt et al. 2016).
In the deterministic LOCAL model the locality is at least (Chang et al. 2016).
3. How to represent problems?
Bipartite edge-labeling formalism. One thing we have learned over the recent years is that it is important to have the right formalism in which we can represent graph problems. The formalism that we will use here is defined so that it makes round elimination as simple as possible, but there is a downside: it is not a particularly natural formalism for a human being to think about graph problems. However, the formalism is very expressive, and in essence all locally verifiable graph problems can be turned into this formalism with some effort (with local reductions that only influence locality by a small additive or multiplicative constant). The right formalism looks like this:
The input graph is an infinite 2-colored tree.
The first color class is called active, and each active node has degree .
The second color class is called passive, and each passive node has degree .
The task is to label each edge with a label from some finite set .
The graph problem is a pair :
is the constraint for active nodes.
is the constraint for passive nodes.
The solution is encoded in the local outputs of the active nodes. For each active node , its local output contains the labels of each edge incident to . The passive nodes do not produce any output.
The labels of the edges incident to an active node satisfy constraint .
The labels of the edges incident to a passive node satisfy constraint .
The constraints and are sets of multisets of edge labels; we will soon see an example that makes their role clear. Before that, one remark is in order: we study here infinite trees, but this is merely for convenience so that we do not need to worry about boundaries. Nevertheless, we can still prove lower bounds that apply to finite inputs: if we show that, for example, in an infinite tree a node has to see at least up to distance , then the same will hold also in the middle of a finite tree in which all leaf nodes are at distance more than ; after all, the local neighborhoods are indistinguishable.
Representing sinkless orientation in the formalism. To prove a lower bound, it is sufficient to construct some family of instances that is hard, and as is often the case, it turns out that the sinkless orientation problem is hard to solve if you are in the middle of a regular tree. And it is easy to see that 3-regular trees have to be the most difficult case; after all the problem becomes trivial if all nodes have degree 2, and there is more slack if there are nodes of a degree higher than 3.
As discussed above, we can also first consider infinite trees and once we have a lower bound construction for infinite trees, we can zoom into a finite fragment of an infinite tree. So the specific problem that we will consider is “sinkless orientation in infinite 3-regular trees”. But how do we map this to the formalism above? In our formalism we are supposed to have a 2-colored tree (which we do not have here), and we are supposed to be labeling edges (while here our task is to orient edges).
It turns out that there is a simple trick we can apply: we split all edges in two halves, and label the half-edges using alphabet , where denotes “head” and denotes “tail”. And now the constraints are simply the following:
For each original edge, exactly one of the half-edges has to be labeled with and the other half-edge has to be labeled with (so that each edge has a well-defined orientation).
For each original node, at least one of the incident half-edges has to be labeled with (so that there is at least one outgoing edge).
(a) Sinkless orientation in a 3-regular tree. (b) Equivalent problem encoded in the bipartite edge-labeling formalism; active nodes (orange) represent edges, passive nodes (blue) represent nodes, and the edge labels and represent “head” and “tail”. In a feasible solution, the multiset of labels around an active node is always , while the multiset of labels around a passive node is , , or . The edge labels are encoded in the local outputs of the active nodes.
Let us formalize this. Let be the original (infinite) tree. We construct a new (infinite) tree , where the set of nodes is and the set of edges is . Now forms one color class and forms another color class; nodes in have degree 3 and nodes in have degree 2. We will now (somewhat arbitrarily) decide to call the set of active nodes and the set of passive nodes, that is, active nodes have degree 2 and passive nodes have degree 3.
As the problem will be the starting point for round elimination, we will call it , and we will use to denote the set of labels. To complete the definition, we need to specify the two constraints and . Here is the set of possible multisets of labels incident to active nodes. As the active nodes correspond to the original edges, we will only allow one possible multiset that contains exactly one and exactly one :
However, for the passive nodes there are more possibilities: we can have one, two, or three incident labels, and hence
Equivalence of representations. Now we have completed the definition of . The key observation is that problem faithfully captures the locality of the sinkless orientation problem in 3-regular trees: if we have an algorithm that finds a sinkless orientation, we can simulate it as a black box to find a solution for , and vice versa, and the simulation changes locality only by a constant factor (distance in graph corresponds to distance in graph ).
Hence, from now on we can forget about the sinkless orientation problem and study the locality of problem specified in –.
Roadmap. We will now apply round elimination to in two ways: first the hard way in Section 4, and then the easy way in Section 5 with the help of computers. In both cases we will see that two applications of round elimination will get us back to the same problem, i.e., ; what that implies is then discussed in more detail in Section 6.
4. Round elimination, done by hand
Basic idea. Imagine you have some algorithm that solves in rounds in any infinite tree . That is, each active node only needs to see up to distance in to determine what are the labels of its incident edges—which of them to label with and which of them to label with .
We will construct now a new algorithm that solves another problem in rounds. The idea is very simple; algorithm works as follows:
Let be a passive node in , and let be one of its active neighbors.
Node gathers all information within radius and sees what it now knows about the output of in algorithm .
Let be the set of all possible labels that might produce for the edge .
Node labels the edge with the set .
A schematic illustration of the round elimination step .
Note that here we have switched the roles of active and passive nodes: what was previously passive in will take an active role in and vice versa; hence we will refer to e.g. -active and -active nodes. Also note that the set of labels changes: if our original set of labels was , the new set of labels will consist of nonempty subsets of .
Algorithm by construction works based on information within distance . However, what is not at all obvious is this: is really solving a nontrivial problem ? After all, could it not happen that just labels all edges with the set ? As we will see through examples, this is not going to be the case!
First step. Let us now apply this idea to the sinkless orientation problem, which we formalized as problem in –. Assume that solves based on radius- neighborhoods, for some value . As we work in the port-numbering model, and the structure of the tree is regular (alternately nodes of degree 2 and degree 3), the only unknown information that can use is the specific assignment of port numbers.
Now consider a -passive node . Recall that passive nodes had degree 3, so there are three active neighbors, , , and . Let consist of all information within distance from , and let consist of all information within distance from ; see the figure above for illustrations.
Now is exactly enough information to determine what would output for the edge . However, represents only a part of , and hence is not enough to simulate . The key observation is this: can be decomposed in two parts, and , as shown in the illustration. Furthermore, parts , , and are disjoint—this is going to be crucial as we will soon see!
When we run algorithm at node , it first gathers all information in . Then for each and each label , we will make the following thought experiment: is there some such that given algorithm would label the edge with ? Let be the set of all such labels ; algorithm will simply output the set for the edge . Now what are the properties that the output of will satisfy?
Let be a -passive node. Assume that for each there was some such that labels with . But parts are disjoint, and therefore we could construct an input in which simultaneously labels all edges incident to with , which is not allowed in according to . Therefore there has to be at least one index such that never labels with , and therefore will label with the set . The other edges might be labeled with , , or .
Let be a -active node. If labels an edge with set , then we know that labels the same edge with some value in this set; after all, the real input that sees is among the possible worlds that will consider in its thought experiment. By assumption, the output of will satisfy constraint defined in , and therefore it will label exactly one edge incident to with and the other edge with . Therefore will label with either or and with either or .
Nodes that were passive in are now active in and vice versa, so if we look at the new roles of the nodes, we can summarize that the output satisfies the following properties:
-active nodes (degree 3): at least one incident edge is labeled with .
-passive nodes (degree 2): one incident edge is labeled with or and the other with or .
But if these are the only constraints we have, the label looks rather pointless. Whenever would output , it could equally well output without violating the above constraints. So there are only two meaningful outputs for ; let us give them some names:
Using this notation, we can restate the properties satisfied by the output of :
-active nodes: at least one incident edge is labeled with .
-passive nodes: at least one incident edge is labeled with .
We can now write this down in our formalism as the specification of a graph problem as follows:
But note that there is one further simplification that we can do (just to keep the problem definition as short as possible): if we have a feasible solution in which an active node labels multiple incident edges with , it can simply replace some of them with s without violating either of the above constraints. Hence w.l.o.g. we can constrain the problem as follows:
Now we have done one step of round elimination: we started with problem , assumed that it is solvable in rounds with some algorithm , and we constructed a new problem that is by construction solvable in rounds using an algorithm that, in essence, just simulates as a black box (and does some minor local post-processing so that we have got a more concise description for problem ).
It turns out that this conversion from to is “if and only if”: assuming there is some algorithm that solves in rounds, we can also recover a solution for in rounds. It is not hard to see this is indeed the case: in essence we can map to and then to either or so that each -active node is adjacent to exactly one .
Second step. We repeat exactly the same reasoning to construct algorithm that solves some problem in rounds. Consider a -passive node . Passive nodes have degree 2, so there are two active neighbors, and . Let consist of all information within distance from , let consist of all information within distance from , and let us decompose in two parts, and .
When we run algorithm at node , it again gathers all information in and labels with the set of all labels that might output for some choice of . What are the properties that the output of will satisfy?
Let be a -passive node. Constraint in implies that cannot ever label all edges incident to with , and hence will label at least one edge with the set that does not contain .
Let be a -active node. Constraint in implies that will label one of the incident edges with and the other two with . Therefore will label one of the incident edges with or , which are the subsets that contain , and the other two with or , which are the subsets that contain .
So to recap, after switching the roles of the nodes, we have got:
-active nodes: at least one incident edge is labeled with .
-passive nodes: one incident edge is labeled with or and the two others with or .
Again there is a label that is rather pointless: any can be replaced with . Hence there are only two meaningful outputs for ; let us again give some convenient names for them:
Using this notation, we can now write down the properties satisfied by the output of as a specification of a graph problem as follows:
And again we can simplify it further by observing that if would label two incident edges with , it can safely replace one of them with . We arrive at the following problem:
And the good news is that we can stop now!
We found a periodic point! Let us recap. We started with , sinkless orientation, and then applied round elimination twice to obtain and . But now if we compare in – with in –, we notice that they are the same problem, up to the naming of the output labels!
We have found a periodic point in round elimination: .
We will discuss how to interpret this in more detail in Section 6, but we will first see how to find such a periodic point with a significantly smaller amount of effort.
5. Round elimination, with the help of a computer
Round Eliminator tool. We have now spent several pages doing a somewhat technical and error-prone analysis to first construct problem and then another problem , and along the way we did also some simplifications that may seem like ad-hoc steps. Is round elimination really that hard?
No, the good news is that we can reproduce exactly what we did in Section 4 with a couple of mouse clicks if we use the Round Eliminator tool by Olivetti (2020)! The only thing we need to know is the language in which we specify problems.
Round Eliminator notation. Recall the original definition of problem in –:
In the computer-readable version we simply write each possible multiset on its own line; the elements are space-separated and we can list them in any order, for example:
Problem 1
Active
Passive
h t
h h t
h t t
t t t
However, often the number of possible multisets gets very large and a shorthand notation is needed. The language that we use with Round Eliminator allows us to write the same problem also as follows:
Problem 2
Active
Passive
h t
ht ht t
The interpretation of the line ht ht t is that for the first element we can choose either h or t, and the same holds for the second element. So expanding this will result in four possibilities, h h t, h t t, t h t, and t t t, the second and the third one being the same multiset. So Problem 2 is exactly the same problem as Problem 1. We have got a very concise way of specifying the sinkless orientation problem.
We do not necessarily need to use the concise form when specifying problems, but we will nevertheless need to be familiar with it so that we can understand the output of the Round Eliminator tool.
First step. Let us open the Round Eliminator tool (Olivetti 2020) and enter Problem 2; we press “start” and then “speedup” to perform one step of round elimination. We get the following problem back:
Problem 3
Active
Passive
B B A
AB B
If we rename A to and B to , we can see that Round Eliminator gave us back exactly the same problem as what we had in – after one manual round elimination step. It is easier to see the equivalence if we expand the shorthand notation and reorder it a bit:
Problem 4
Active
Passive
A B B
A B
B B
Second step. Let us continue and press the “speedup” button again. Now we get the following problem back:
Problem 5
Active
Passive
B A
AB AB B
If we rename A to and B to , we see that this is exactly the same problem as what we had in – after two round elimination steps. And on the other hand we can see that this is also identical to Problem 2 that we started with (the only difference being the names of the labels). So we have with a couple of mouse clicks identified that , and hence we are at the same point as where we were at the end of Section 4.
6. Consequences of a periodic point
Immediate lower bound in the port-numbering model. We have now seen (twice) that , that is, two steps of round elimination gives us back the same problem—or a bit more precisely, problem is isomorphic to . There are at least two useful ways to interpret this, but both lead to the same conclusion:
If the locality of in infinite trees is some finite value , then the locality of the same problem is , which is absurd. Hence the locality of in infinite trees cannot be finite.
If we have an algorithm that solves in rounds for some finite even , we can use round elimination repeatedly to reduce to 0. But it is easy to check that cannot be solved in 0 rounds, so cannot exist.
The conclusion in both cases is that sinkless orientation cannot be solved at all in the port-numbering model if you are in the middle of a regular tree and do not see any leaf nodes (or other irregularities).
And now it is enough to observe that we can construct a finite 3-regular tree with nodes in which all leaf nodes are within distance from the midpoint, and hence we get a tight lower bound on the locality of sinkless orientation in the port-numbering model.
Consequences for other models of computing. Now let us look back at what we did: we performed round elimination in the port-numbering model (so e.g. the only “unknown” information in the distant parts was the specific choice of port numbering).
We would like to do the same in the usual deterministic LOCAL model. Unfortunately, the unique identifiers are something that we cannot directly handle in the round elimination process. For example, if in some neighborhood algorithm outputs for the edge if and only if it sees the unique identifier 1 in part , then we cannot argue that will also output for all edges for some choice of unique identifiers. After all, identifier 1 cannot be simultaneously in part and part .
However, we can take a detour through randomized algorithms. We simply assume that all nodes have random bits as inputs. We start with a randomized algorithm that solves so that the local failure probability is some small . Then we can show that will solve so that the local failure probability is some , which depends on and the structure of . Now if we apply this reasoning to the sinkless orientation problem, we can repeat the argument steps for an even and arrive at that solves in rounds so that the local failure probability is . If we have , we can show that is not too high, and has to do something nontrivial, and hence , which implies that the original algorithm requires more than rounds. Therefore the locality of has to be for randomized algorithms. For the details of this kind of an analysis, see, for example, Brandt et al. (2016) and Balliu et al. (2020a).
Now that we have a lower bound for the randomized LOCAL model, it immediately implies a lower bound in the deterministic LOCAL model: after all, any deterministic algorithm gives also an equally fast randomized algorithm (we can use randomness to construct unique identifiers w.h.p.). Hence we have got a lower bound of for the deterministic LOCAL model. But we can do better; the gap result by Chang et al. (2016) shows that the existence of an -round deterministic algorithm for a locally verifiable problem implies the existence of an -round deterministic algorithm for the same problem, but we know that such an algorithm cannot exist. Hence the gap result implies that the locality of the sinkless orientation problem in the deterministic LOCAL model is , which is tight.
To recap, we took the following steps:
Start with a locally verifiable problem .
Show that is a periodic point in round elimination: .
It follows that the complexity of in the port-numbering model is .
By taking into account failure probabilities, it follows that the complexity of in the randomized LOCAL model is .
By amplifying this with the gap result, it follows that the complexity of in the deterministic LOCAL model is .
All of this generalizes. Now the key point is this: the above reasoning was in essence only using the fact that is a locally verifiable problem with . Hence whenever we have a periodic point in round elimination, we get for free the same lower bound results: the locality is in the deterministic LOCAL model and in the randomized LOCAL model.
Of course we are not always lucky; however, whenever we encounter a locally verifiable problem of an unknown complexity, it makes sense to check if or e.g. some relaxation of happens to satisfy e.g. or . Lots of examples of such problems are already known (Olivetti and Suomela 2020), and for all such problems we can immediately derive a lower bound with the help of the Round Eliminator tool.
Often we need to consider relaxations. There is one counterintuitive observation that is useful to keep in mind when applying round elimination: often it is easier to prove lower bounds for easier problems! For example, we have seen that sinkless orientation is a periodic point in round elimination. Now consider a more challenging version of the problem, sinkless and sourceless orientation, in which nodes of degree at least 3 must have both indegree and outdegree at least 1. Trivially, sinkless and sourceless orientation is at least as hard as sinkless orientation. However, sinkless and sourceless orientation is not a periodic point in round elimination. Therefore to prove a lower bound for sinkless and sourceless orientation, it is useful to note that it is a strict restriction of the sinkless orientation problem, which is one of the problems that is known to be a periodic point in round elimination, and this observation gives a lower bound also for sinkless and sourceless orientations.
7. There is a lot more we can do
Round elimination sequences. Round elimination is by no means merely about periodic points. More generally, we can construct e.g. a sequence of problems such that for each . Such a sequence can be applied both to prove upper bounds and to prove lower bounds:
Upper bounds: If is a trivial problem that can be solved in 0 rounds, then we know that the locality of is at most . We can even work backwards to extract a -round algorithm for solving .
Lower bounds: If is a nontrivial problem that cannot be solved in 0 rounds, then we know that the locality of is more than .
Restrictions and relaxations. One challenge here is that if the round elimination sequence does not converge to a periodic point, the size of the description of the problems can very rapidly increase, and even if is a simple problem with a short description, might already be too large to even write down explicitly in a computer, let alone to understand for a human being. Hence what we often do in practice is to consider restrictions and relaxations:
An upper bound sequence is a sequence of problems such that is a restriction of for each . Now if is solvable in 0 rounds, the locality of is at most .
A lower bound sequence is a sequence of problems such that is a relaxation of for each . Now if is not solvable in 0 rounds, the locality of is more than .
Lower bound sequences were used recently, for example, to show a lower bound for maximal matchings and maximal independent sets (Balliu et al. 2019), and also Linial’s (1987, 1992) lower bound can be interpreted as such a sequence of problems.
Further reading. For more information on the round elimination process, these are recommended reading:
Brandt (2019) gives the formal mathematical definition of the round elimination process.
Olivetti (2020) gives a detailed explanation of how to use the Round Eliminator tool.
Acknowledgments
Many thanks to Sebastian Brandt and Yannic Maus for their comments on this article, and also to everyone else who has taken part in the development of the round elimination technique!
Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer (2004).
What cannot be computed locally!Proc. 23rd Annual ACM Symposium on Principles of Distributed Computing (PODC 2004).
Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer (2006).
The price of being near-sighted.Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006).
Here are some additional resources related to round elimination; this list was last updated on November 9, 2020.
Introductory material:
Sebastian Brandt (2019).
Automatic Round Elimination: A New Approach for Proving Complexity Bounds in the LOCAL Model.
Talk at ADGA 2019:
abstract,
slides.
Work that uses round elimination for proving upper bounds:
Pierre Fraigniaud, Marc Heinrich, and Adrian Kosowski (2016).
Local Conflict Coloring.Proc. 57th Annual Symposium on Foundations of Computer Science (FOCS 2016).arXiv:1511.01287.