Lower bounds in distributed computing

dc.contributorAalto-yliopistofi
dc.contributorAalto Universityen
dc.contributor.advisorSuomela, Jukka, Prof., Aalto University, Department of Computer Science, Finland
dc.contributor.authorHirvonen, Juho
dc.contributor.departmentTietotekniikan laitosfi
dc.contributor.departmentDepartment of Computer Scienceen
dc.contributor.labDistributed Algorithmsen
dc.contributor.schoolPerustieteiden korkeakoulufi
dc.contributor.schoolSchool of Scienceen
dc.contributor.supervisorSuomela, Jukka, Prof., Aalto University, Department of Computer Science, Finland
dc.date.accessioned2016-11-09T10:01:32Z
dc.date.available2016-11-09T10:01:32Z
dc.date.defence2016-11-25
dc.date.issued2016
dc.description.abstractIn 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.en
dc.description.abstractTutkin 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.fi
dc.format.extent75 + app. 81
dc.format.mimetypeapplication/pdfen
dc.identifier.isbn978-952-60-7137-4 (electronic)
dc.identifier.isbn978-952-60-7138-1 (printed)
dc.identifier.issn1799-4942 (electronic)
dc.identifier.issn1799-4934 (printed)
dc.identifier.issn1799-4934 (ISSN-L)
dc.identifier.urihttps://aaltodoc.aalto.fi/handle/123456789/23473
dc.identifier.urnURN:ISBN:978-952-60-7137-4
dc.language.isoenen
dc.opnElkin, Michael, Prof., Ben-Gurion University of the Negev, Israel
dc.publisherAalto Universityen
dc.publisherAalto-yliopistofi
dc.relation.haspart[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
dc.relation.haspart[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
dc.relation.haspart[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
dc.relation.haspart[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
dc.relation.haspart[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
dc.relation.ispartofseriesAalto University publication series DOCTORAL DISSERTATIONSen
dc.relation.ispartofseries239/2016
dc.revKuhn, Fabian, Prof., University of Freiburg, Germany
dc.revNanongai, Danupon, Prof., Kungliga Tekniska högskolan, Sweden
dc.subject.keyworddistributed computingen
dc.subject.keywordlocal algorithmsen
dc.subject.keywordlower boundsen
dc.subject.keywordhajautettu laskentafi
dc.subject.keywordpaikalliset algoritmitfi
dc.subject.keywordalarajatfi
dc.subject.otherComputer scienceen
dc.titleLower bounds in distributed computingen
dc.titleLower bounds in distributed computingfi
dc.typeG5 Artikkeliväitöskirjafi
dc.type.dcmitypetexten
dc.type.ontasotDoctoral dissertation (article-based)en
dc.type.ontasotVäitöskirja (artikkeli)fi
local.aalto.archiveyes
local.aalto.formfolder2016_11_08_klo_13_21
Files
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
isbn9789526071374.pdf
Size:
1.08 MB
Format:
Adobe Portable Document Format