Lower bounds in distributed computing

Abstract

In this thesis I study the complexity theory of distributed computing in synchronous message passing models. The focus is on highly local problems, that is, problems in which very little communication is required. In this setting the underlying communication network is also the input graph. The distributed system must collectively compute a solution to a problem related to the structure of this network, with each computer producing its own part of the output.

We study the LOCAL model, one of the standard models in distributed computing. It abstracts away faults, congestion, computational requirements, memory requirements, and many other challenges in distributed computing. We study this model to understand the locality aspect of distributed computing: How far does information have to propagate in distributed problem solving? How many communication rounds is required?

Many interesting problems, such as finding a spanning tree in the communication network, are inherently global. We are interested in the other extreme: problems that can be solved in time that is weakly dependent or completely independent of the size of the communication network. Typical problems include classical symmetry breaking tasks such as colouring or maximal independent set. Typically the time complexity of such problems depends on two parameters: the size and the maximum degree of the input graph. The connection with the first parameter is well understood with tight upper and lower bounds. The connection with the maximum degree is much less well understood, with an exponential gap between the upper and lower bounds. We develop a new lower bound technique to give the first lower bound for a natural graph problem that is linear in the maximum degree.

In addition we study the power of unique in several contexts. We show that while usually unique identifiers are unhelpful for constant-time algorithms, there are certain special cases in which they do help. In the context of local decision, where the task is essentially to verify a given solution instead of constructing a new one, we characterize the minimal information that is sufficient to replace unique identifiers.

Finally, we also study the power of nondeterminism in local decision. We develop a local hierarchy in a manner analogous to the polynomial hierarchy in centralized computing, and study the structure of this hierarchy.

The focus of this thesis is on structural results, especially lower bounds. The lower bounds as a function of the maximum degree of the graph employ a completely novel proof technique based on graph symmetries.

Tutkin tässä väitöskirjatyössä hajautetun laskennan vaativuusteoriaa synkronisissa viestinvälitysmalleissa. Työ keskittyy paikallisiin ongelmiin, eli ongelmiin, joiden ratkaisu voidaan löytää käyttäen vain vähäinen määrä kommunikaatiota. Tutkitussa asetelmassa kommunikaatioverkko on myös ongelman syöte. Hajautetun järjestelmän täytyy löytää ratkaisu, joka liittyy tämän verkon rakenteeseen ja jokaisen verkon solmun täytyy tuottaa oma osansa tulosteesta.

Työssä tutkitaan hajautetun laskennan standardimalleihin kuuluvaa LOCAL-mallia. Tämä malli ei huomioi erilaisia hajautetun laskennan haasteita, kuten vikoja, ruuhkautumista, tai laskenta- ja muistivaatimuksia. Tätä mallia tutkitaan paikallisuuden ymmärtämiseksi: kuinka kauas informaatiota täytyy propagoida, jotta ongelma voidaan ratkaista hajautetusti? Kuinka monta kommunikaatiokierrosta ongelman ratkaiseminen vaatii?

Monet kiinnostavat ongelmat, kuten kommunikaatioverkon virittävän puun löytäminen, ovat globaaleja ongelmia. Tässä työssä tarkastelemme toista ääripäätä: ongelmia, jotka voidaan ratkaista ajassa, joka on kokonaan riippumaton tai korkeintaan heikosti riippuvainen kommunikaatioverkon koosta. Tällaisia ongelmia ovat esimerkiksi klassiset symmetrianrikkomisongelmat kuten väritys ja riippumattomat joukot. Tyypillisesti näiden ongelmien aikavaativuus riippuu kahdesta tekijästä, verkon koosta ja sen maksimiasteluvusta. Yhteys verkon kokoon on melko hyvin ymmärretty, mutta riippuvuus maksimiasteluvusta ei. Tunnettujen ylä- ja alarajojen erotus on eksponentiaalinen. Kehittämämme alarajatekniikka antaa ensimmäisen maksimiasteluvun suhteen lineaarisen alarajan luonnolliselle verkko-ongelmalle.

Lisäksi olemme tutkineet solmuille annettavien uniikkien nimien vaikutusta. Vaikka tyypillisesti uniikit tunnisteet eivät auta vakioaikaisia algoritmeja, näytämme, että tietyissä tilanteissa niitä voidaan hyödyntää. Paikallisten päätösongelmien tapauksessa, jossa solmujen täytyy tarkastaa annettu ratkaisu uuden rakentamisen sijaan, karakterisoimme sen informaation määrän, joka riittää ja vaaditaan uniikkien tunnisteiden korvaamiseen.

Viimeiseksi tutkimme epädeterministisyyden vaikutusta paikallisiin päätösongelmiin. Kehitämme paikallisen päätöshierarkian, joka on analoginen keskitetyn laskennan polynomisen hierarkian kanssa, ja tutkimme tämän hierarkian rakennetta.

Väitöskirjatyö keskittyy rakenteellisiin tuloksiin, erityisesti mahdottomuustuloksiin. Verkon asteluvusta riippuvat alarajatulokset edustavat täysin uudenlaista alarajatekniikkaa, joka hyödyntää verkossa olevaa symmetriaa.