Breakthroughs in Foundations of Distributed Computing

In distributed computing, many computational problems are inherently global: to solve such a problem, we need to get full information on the structure of the computer network. There are also some problems that can be solved in a strictly local manner: it is enough that each computer is aware of its local neighbourhood (e.g, of other computers that are within some small constant number of hops away).

 

While the two extremes — global problems and local problems — are nowadays fairly well understood, much less is known about problems that fall between the two extremes. Our recent work "A lower bound for the distributed Lovász local lemma" now gives the first genuine example of a problem of an intermediate time complexity, falling strictly between local problems and global problems, even in the case of networks in which all nodes have only a small number of neighbours. This work was accepted for presentation at STOC 2016, which is one of the most prestigious and selective conferences in theoretical computer science.

 

Our work has been available on ArXiv.org now for a few months, and it has already inspired groundbreaking follow-up work: the recent manuscript "An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model" by the University of Michigan researchers Yi-Jun Chang, Tsvi Kopelowitz, and Seth Pettie builds on our work to resolve another long-standing open question: they show that sometimes it is necessary to use randomness in order to design fast distributed algorithms.