Applying Category Theory to the Study of Biregular LCL-Problems and Round Elimination

Abstract

Recently, a lot of progress has been made in the study of distributed computational complexity in the class of so-called locally checkable labelling problems (LCLs). In particular, there is a new proof technique, round elimination, which resembles a function, and finding its periodic points in a further restricted biregular formalism has been fruitful for showing lower bounds. In this thesis I provide a rigorous definition for biregular LCL-problems based on category theory, which gives powerful tools for studying 0-round reductions and equivalence of problems.

I define the category LCL (d, delta) with (d, delta)-biregular LCL-problems as objects and local correctness preserving (LCP) maps as morphisms. The use of categories gives access to terminology and definitions from category theory. LCP-maps imply 0-round reductions, and conversely I show that once impossible labels are removed, they capture all 0-round reductions that can be found with reasonable assumptions.

In this framework round elimination becomes a map between categories, and I prove that it preserves the existence of LCP-maps. Thus it can be defined over equivalence classes, generalising it as a proof technique and unifying existing definitions. My main result is that with reasonable assumptions the longest period of a periodic point of round elimination is 2. This implies that periodicity of a problem Pi can be checked automatically by determining the existence of LCP-maps Re2(Pi) to Pi, for which I provide an implementable algorithm.

Finally, the new tools make it possible to define a minimality condition for representatives of equivalence classes, which can be checked without referencing other problems. I prove that it is equivalent to an intuitive condition, and show how to minimise representatives.

This work provides a new perspective for the further study of biregular LCLproblems and improvements for the automated analysis tools. These in turn enhance our understanding of distributed computational complexity, which can help us develop more efficient algorithms for distributed systems.

Viime vuosina hajautettujen algoritmien laskennallisen vaativuuden tutkimuksessa on tehty harppauksia tarkastelemalla paikallisesti tarkistettavia merkitsemisongelmia (LCL-ongelmia). Erityisesti uuden funktiota muistuttavan todistustustekniikan, kierroseliminaation, jaksollisten pisteiden etsiminen on ollut antoisaa alarajojen todistamisessa. Tässä työssä annan kaksisäännöllisille LCL-ongelmille kategoriateoriaan pohjautuvan tarkan määritelmän, joka tarjoaa tehokkaita työkaluja nollan kierroksen reduktioiden ja ongelmien ekvivalenssin tutkimiseen.

Määrittelen kategorian LCL (d, delta), jonka objekteina ovat (d, delta)-kaksisäännölliset LCL-ongelmat ja morfismeina paikallisen paikkansapitävyyden säilyttävät kuvaukset (LCP-kuvaukset). Näytän, että LCP-kuvaukset vastaavat kohtuullisilla oletuksilla nollan kierroksen reduktioita. Kategorioiden käyttö mahdollistaa kategoriateorian määritelmien ja sanaston hyödyntämisen.

Kierroseliminaatio muuttuu tässä kontekstissa kuvaukseksi kategorioiden välillä, ja osoitan sen säilyttävän LCP-kuvausten olemassaolon. Niinpä kierroseliminaatio voidaan määritellä ekvivalenssiluokkien yli, mikä yleistää sitä todistustekniikkana yhdistäen sen eri määritelmiä. Työn päätulos on, että kohtuullisilla oletuksilla kierroseliminaation jaksollisten pisteiden pisin mahdollinen jakso on 2. Tästä seuraa, että ongelman Pi jaksollisuus voidaan tarkistaa automaattisesti selvittämällä, onko LCP-kuvauksia Re2(Pi) to Pi olemassa, mihin annan algoritmin.

Lopuksi hyödynnän uusia työkaluja määrittelemällä ekvivalenssiluokkien edustajille minimaalisuusehdon, joka voidaan tarkistaa viittaamatta muihin ongelmiin. Todistan sen olevan yhtäpitävä luontevan ehdon kanssa, sekä lisäksi näytän, miten edustajia voi minimoida.

Työ tarjoaa uuden näkökulman LCL-ongelmien tutkimiseen ja parannuksia siihen liittyviin automaattityökaluihin. Nämä vuorostaan lisäävät ymmärrystä hajautetusta aikavaativuudesta, mikä voi auttaa tehokkaampien algoritmien kehityksessä hajautetuille järjestelmille.