Automatically Finding Non-constant Lower Bounds for Locally Checkable Labeling Problems in the LOCAL Model

Abstract

Distributed computing is any kind of computing that is performed on a spatially distributed system. It is often considered when high amounts of computation power is required. Distributed computing is used to solve large-scale problems that would otherwise be impractical to solve in a centralized system.

In this thesis, I study the theoretical foundations of distributed computing. The models of distributed computing I am interested in are the port-numbering (PN) model and the LOCAL model. In these models, each node of a computer network executes a common algorithm synchronously and can exchange messages with their neighboring nodes in each communication round. Between these communication rounds, the nodes can perform computation in an instant. The complexity of the algorithm is measured as the number of communication rounds it takes until each node of a network terminates. Locally checkable labeling (LCL) problems are a family of graph problems where a global solution can be verified locally by the individual nodes.

In the research of the foundations of distributed computing there is a recent trend to automate finding upper and lower bounds for LCL problems in the LOCAL model. This thesis contributes to the field by automating the process of finding non-constant lower bounds for LCL problems in the LOCAL model.

I present a new algorithm that can detect if an LCL problem does not have a solution in finite connected (Delta, delta)-biregular multigraphs. Then I show that if the problem does not have a solution in the graph family, it is also unsolvable in the PN model. I also prove that if an LCL problem is unsolvable in the PN model, then it cannot be solved in constant time in the LOCAL model. Thus, the algorithm can automatically prove that an LCL problem is unsolvable in constant time in the LOCAL model. In order to automatically find new lower bounds for LCL problems in the LOCAL model in practice, I present an implementation of the algorithm. With the implementation, I find new lower bounds for nine LCL problems and as a consequence, one of the problems is now classified with a tight bound of Theta(log* n).

Hajautettu laskenta on mitä tahansa laskentaa, johon osallistuu eri paikoissa sijaitsevia tietokoneita. Sitä käytetään usein tilanteissa, joissa vaaditaan suurta laskentatehoa. Hajautettua laskentaa hyödyntämällä voidaan ratkaista ison mittakaavan ongelmia, jotka olisivat epäkäytännöllisiä ratkaista keskitetyssä järjestelmässä.

Tässä työssä tutkitaan hajautetun laskennan teoreettista perustaa. Olen kiinnostunut hajautetun laskennan porttinumerointimallista eli PN-mallista sekä LOCAL-mallista. Näissä malleissa jokainen tietokoneverkon solmu suorittaa samaa algoritmia synkronisesti ja vaihtaa jokaisella viestintäkierroksella viestejä viereisten solmujen kanssa. Näiden viestintäkierroksien välillä solmut voivat laskea äärettömän nopeasti. Algoritmin nopeus on se kierrosten määrä, jonka jälkeen jokainen verkon solmu viimeistään lopettaa algoritmin suorittamisen. Paikallisesti tarkastettavat merkitsemisongelmat (LCL-ongelmat) ovat verkko-ongelmaperhe, jossa jokainen yksittäinen solmu voi paikallisesti tarkistaa globaalin ratkaisun.

Hajautetun laskennan teoreettisen perustan tutkimuksissa on viime aikoina näkynyt kehityssuunta, jossa automatisoidaan LCL-ongelmien ylä- ja alarajojen löytäminen LOCAL-mallissa. Tämän työ edistää kyseistä tutkimusalaa automatisoimalla LCL-ongelmien ei-vakioaikaisten alarajojen löytämisen LOCAL-mallissa.

Esittelen uuden algoritmin, joka tunnistaa, jos annetulle LCL-ongelmalle ei ole ratkaisua äärellisissä yhtenäisissä (Delta, delta)-säännöllisissä kaksijakoisissa moniverkoissa. Tämän jälkeen näytän, että jos tällä ongelmalla ei ole ratkaisua kyseisessä verkkoperheessä, niin se ei ole ratkeava PN-mallissa. Näytän myös, että jos annettu LCL-ongelma ei ole ratkeava PN-mallissa, niin sitä ei voi myöskään ratkaista vakioajassa LOCAL-mallissa. Tästä seuraa, että esittelemäni algoritmi voi todistaa automaattisesti, että LCL-ongelma ei ole vakioajassa ratkeava. Esittelen myös toteutuksen algoritmille, jotta voimme käytännössä löytää automaattisesti uusia alarajoja LCL-ongelmille LOCAL-mallissa. Löydän tällä toteutuksella uusia alarajoja yhdeksälle LCL-ongelmalle ja tämän seurauksena yhdelle näistä ongelmista tunnetaan sen laskennallinen vaativuus tarkasti: ongelman ratkaiseminen vaatii Theta(log* n) viestintäkierrosta.