Suomela, Jukka
Landscape of Locality (Invited Talk)
Abstract
The theory of distributed computing aims at understanding which tasks can be solved efficiently in large distributed systems. This forms the basis for our understanding of the modern world, which heavily depends on worldwide communication networks and largescale distributed computer systems.
In distributed computing the key computational resource is communication, and we seek to find out which computational problems can be solved with only a few communication steps. This is directly connected to the concept of locality: in T synchronous communication rounds, all nodes in a network can gather all information in their radiusT neighborhoods, but not any further. Hence the distributed time complexity of a graph problem can be defined in two equivalent ways: it is the number of communication rounds needed to solve the problem, and it is the distance up to which individual nodes need to see in order to choose their own part of the solution.
While the locality of graph problems has been studied already since the 1980s, only in the past four years we have started to take big leaps in understanding what the landscape of distributed time complexity looks like and with what kind of tools and techniques we can study it.
One concept that has been a driving force in the recent developments is the notion of locally verifiable problems. These are graph problems in which a solution is feasible if and only if it looks valid in all constantradius neighborhoods; put otherwise, these are problems that could be solved efficiently with a nondeterministic distributed algorithm, and hence they form a natural distributed analogue of class NP. Now the key question is this: if a problem is locally verifiable, is it also locally solvable, and if not, what can we say about its distributed time complexity?
Naor and Stockmeyer [SIAM J. Comput. 1995] formalized the idea of locally verifiable problems by introducing the class of LCL problems (locally checkable labeling problems). While the concept is old, and over the years we have seen results related to the locality of many specific LCLs, little was known about the distributed complexity of LCLs in general. By 2015, we had only seen examples of LCLs with localities O(1), Θ(log^* n), and Θ(n), and it was wide open whether these three classes are all that there is.
All this started to change rapidly after we proved [Brandt et al., STOC 2016] that there are natural examples of LCLs that have a locality strictly between ω(log^* n) and o(n). The same paper also paved the way for the development of a new generalpurpose proof technique for analyzing the locality of locally verifiable problems, namely round elimination.
Now after four years of work and a number of papers by several research teams working in the area, we have reached a point in which there is a nearcomplete picture of the landscape of LCL problems  and it looks nothing like what we would have expected.
BibTeX  Entry
@InProceedings{suomela:LIPIcs:2020:12249,
author = {Jukka Suomela},
title = {{Landscape of Locality (Invited Talk)}},
booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
pages = {2:12:1},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771504},
ISSN = {18688969},
year = {2020},
volume = {162},
editor = {Susanne Albers},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12249},
URN = {urn:nbn:de:0030drops122490},
doi = {10.4230/LIPIcs.SWAT.2020.2},
annote = {Keywords: Theory of distributed computing, Network algorithms, Locality, Distributed time complexity}
}
12.06.2020
Keywords: 

Theory of distributed computing, Network algorithms, Locality, Distributed time complexity 
Seminar: 

17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)

Issue date: 

2020 
Date of publication: 

12.06.2020 