License: Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2020.2
URN: urn:nbn:de:0030-drops-122490
Go to the corresponding LIPIcs Volume Portal

Suomela, Jukka

Landscape of Locality (Invited Talk)

LIPIcs-SWAT-2020-2.pdf (0.2 MB)


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 world-wide communication networks and large-scale 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 radius-T 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 constant-radius 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 general-purpose 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 near-complete picture of the landscape of LCL problems - and it looks nothing like what we would have expected.

BibTeX - Entry

  author =	{Jukka Suomela},
  title =	{{Landscape of Locality (Invited Talk)}},
  booktitle =	{17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-150-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{162},
  editor =	{Susanne Albers},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-122490},
  doi =		{10.4230/LIPIcs.SWAT.2020.2},
  annote =	{Keywords: Theory of distributed computing, Network algorithms, Locality, Distributed time complexity}

Keywords: Theory of distributed computing, Network algorithms, Locality, Distributed time complexity
Collection: 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)
Issue Date: 2020
Date of publication: 12.06.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI