Simulation argument I. General technique
11 Feb 2019As said earlier on this blog, a recent preprint proves a set of longexpected lower bounds for distributed graph algorithms. This post is the first of a (short) series of (short) posts about the basics of this paper.
A series of posts
In this first post we give an overview of the simulation argument, which is the framework used for the lower bound.
The next posts will be about:
 specific construction for edge labelings on bicolored trees
 Example 1: sinkless orientation
 Example 2: maximal matching
Most of the content of this series is probably better explained in the preprint cited above, so you may want to look at it instead of these posts! The main difference will appear in the second post where I propose a slightly different vocabulary, based on polynomials. The posts assume familiarity with the local model.
A few bits of context
The simulation technique can be traced back to Linial, and his $\Omega(\log^*n)$ lower bound for coloring.^{1} However, it did a comeback with a 2015 paper that had a different point of view. It was then simplified and improved.^{2} The technique was an important part of the talk of Juho Hirvonen at the 2017 ADGA workshop.
Overview of the simulation argument
The core question of the simulation argument is the following. Suppose that in time $T$ you can solve a problem. Then what can you solve if you have only $T1$ rounds? For example, if you can solve coloring with $c$ colors in $T$ rounds, can you solve coloring with $2^c$ colors (which is easier) is $T1$ rounds? For lower bounds, the basic line of reasoning is the following.
Base step: 0 rounds
Fix a problem $P$. Suppose you have a way to do the following transformation.
Start with:
an algorithm $A$ in $T$ rounds for a problem $P$.
Change it into:
an algorithm $A’$ in $T1$ rounds for another problem $P’$.
Then, say you want to prove that solving $P$ requires more than one round. Then you only need to prove that you have a transformation as above, with $T=1$, and that $P’$ is not trivial (that is, to prove that $P’$ cannot be solved in zero round). Indeed if there is an algorithm in one round for $P$, then you can transform it into an algorithm in 0 round for $P’$, which would contradict the nontriviality of $P’$. At this point, you know that $P$ requires at least two rounds. This may sound silly as we have just moved the difficulty from one problem to another: for this technique to work, we need to be able to prove that $P’$ is nontrivial. But this is usually much simpler.
Induction
Lower bounds of one rounds are not super exciting, and one would like to prove bounds of $k+1$ rounds, for some $k$. The argument goes the following way. For the sake of contradiction, suppose there is an algorithm in $k$ rounds for your problem $P$. Now you prove that there exists a family of problems $P_0, P_1, P_2, …,P_k$, with $P_0=P$, such that:
 none of them is trivial
 given an algorithm for $P_i$ in $ki$ rounds, you can transform it into an algorithm in $ki1$ rounds for $P_{i+1}$.
The second bullet implies that $P_k$ can be solved in $0$ rounds, which impossible because the first bullet states that it is nontrivial. Thus $P$ needs at least $k+1$ rounds.
Simulation argument
The question now: how do you define a transformation from one problem to another?
Suppose you know an algorithm in $T$ rounds, but you have only a view of
$T1$ rounds. Then you can do the following.
 Imagine all the possible ways your $(T1)$neighborhood could be extended to a $T$neighborhood.
 Compute a solution for each of these extensions, using your $T$round algorithm.
 Label your node/edges with the set of all the labels that the Tround algorithm would use in at least one of these extensions.
Obviously you are not solving the original problem because you are labeling your node/edges with sets of labels, instead of labeling them with only one label. Also this labeling may be uninteresting: every node/edge could be labeled with all the possible labels. But maybe it is interesting. And then you may be able to define a nontrivial problem $P’$ (probably a quite artificial problem but it’s ok) such that this setlabeling is a proper labeling for $P’$.
Simplification step
You may also want to have a simplification step. This is a step that you perform after you have labeled your nodes/edges with sets of labels. The goal is to simplify the proof, by replacing the sets of labels by something simpler, typically simple labels. For example you decide that every set of labels {$a,b$} is replaced by $a$. For this step to be useful you need that:
 one can compute the simplification without further communication (e.g. no synchronization with neighbors)
 the new labels fit into a language that has good properties, in particular, it is not trivial.
Footnotes

The simulation argument appears more clearly in the modern version of the proof ↩

See this recent note by Sebastian Brandt that formalizes precisely the approach. ↩