Lower bounds in distributed computing

Thumbnail Image

Files

isbn9789526071374.pdf (1.08 MB)

URL

Journal Title

Journal ISSN

Volume Title

School of Science | Doctoral thesis (article-based) | Defence date: 2016-11-25
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.

Authors

Date

2016

Department

Tietotekniikan laitos
Department of Computer Science

Major/Subject

Mcode

Degree programme

Language

en

Pages

75 + app. 81

Series

Aalto University publication series DOCTORAL DISSERTATIONS, 239/2016

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.

Description

Supervising professor

Suomela, Jukka, Prof., Aalto University, Department of Computer Science, Finland

Thesis advisor

Suomela, Jukka, Prof., Aalto University, Department of Computer Science, Finland

Keywords

distributed computing, local algorithms, lower bounds, hajautettu laskenta, paikalliset algoritmit, alarajat

Other note

Parts

  • [Publication 1]: Juho Hirvonen and Jukka Suomela. Distributed maximal matching: greedy is optimal. In Proceedings of the 2012 ACM Symposium on Principles of Distributed Computing (PODC 2012), Funchal, Portugal, pages 165–174, July 2012.
    DOI: 10.1145/2332432.2332464 View at publisher
  • [Publication 2]: Pierre Fraigniaud, Juho Hirvonen, and Jukka Suomela. Node labels in local decision. Proceedings of the 22nd International Colloquim on Structural Information and Communication Complexity (SIROCCO 2015), Montserrat, Spain, pages 31–45, July 2015.
    DOI: 10.1007/978-3-319-25258-2_3 View at publisher
  • [Publication 3]: Laurent Feuilloley, Pierre Fraigniaud, and Juho Hirvonen. A hierarchy of local decision. Accepted for publication in Proceedings of the 43rd International Colloquim on Automata, Languages, and Programming (ICALP 2016), July 2016
  • [Publication 4]: Henning Hasemann, Juho Hirvonen, Joel Rybicki, and Jukka Suomela. Deterministic local algorithms, unique identifiers, and fractional graph colouring. Theoretical Computer Science, Volume 610, part B, 11, pages 204–217, January 2016.
    DOI: 10.1016/j.tcs.2014.06.044 View at publisher
  • [Publication 5]: Mika Göös, Juho Hirvonen, and Jukka Suomela. Linear-in-lower bounds in the LOCAL model. Accepted for publication in Distributed Computing, 2016.
    DOI: 10.1145/2611462.2611467 View at publisher

Citation

Permanent link to this item

https://urn.fi/URN:ISBN:978-952-60-7137-4

Collections

[diss] Perustieteiden korkeakoulu / SCI