Résumé | Locality of distributed computing is the study of how far information has to propagate in distributed systems. In the last few years, we have seen the emergence of a complexity theory of locality for a large class of natural problems, the locally checkable labelings. I will present some of the new lower bound techniques that have contributed to this theory. These techniques are based on simulation, providing elegant and simple proofs.
The sinkless orientation problem has played a key role a key role in this new theory. We gave a randomized lower bound of ?(log log n) for this problem (Brandt et al., STOC 2016), establishing it as the first problem with provably "intermediate" complexity. Our lower bound was later lifted to an ?(log n) deterministic lower bound by Chang et al. (FOCS 2016). This, along with the matching algorithms of Ghaffari and Su (SODA 2017), show that this problem exhibits an exponential separation between deterministic and randomized complexities.
I will show a simpler lower bound proof for this problem, using elements from different proofs. I will try to highlight the effectiveness of simulation as a proof technique, and try to showcase how complexity theoretic results can be used as black boxes in order to aid these proofs. |