Logic and Complexity in Distributed Computing

 |  Login

Show simple item record

dc.contributor Aalto-yliopisto fi
dc.contributor Aalto University en
dc.contributor.advisor Suomela, Jukka, Prof., Aalto University, Department of Computer Science, Finland
dc.contributor.author Lempiäinen, Tuomo
dc.date.accessioned 2019-03-21T10:01:00Z
dc.date.available 2019-03-21T10:01:00Z
dc.date.issued 2019
dc.identifier.isbn 978-952-60-8478-7 (electronic)
dc.identifier.isbn 978-952-60-8477-0 (printed)
dc.identifier.issn 1799-4942 (electronic)
dc.identifier.issn 1799-4934 (printed)
dc.identifier.issn 1799-4934 (ISSN-L)
dc.identifier.uri https://aaltodoc.aalto.fi/handle/123456789/37232
dc.description.abstract This dissertation studies the theory of distributed computing. In the distributed setting, computation is carried out by multiple independent computational units. They communicate with neighbouring units and collectively solve a problem. Systems of this kind are widespread in the information society as well as in the natural world: prime examples include the Internet, multi-processor computer systems, the cells of a biological organism and human social networks. Therefore it is important to gain knowledge on the fundamental capabilities and limitations of distributed systems. Our work takes place in the context of deterministic and synchronous message-passing models of distributed computing. Such models abstract away some possible features of distributed systems, such as asynchrony, congestion and faults, while putting emphasis on the amount of communication needed between the units. The computational units are expected to solve a problem related to the structure of the underlying communication network. More specifically, we study the standard LOCAL model, the standard port-numbering model and several weaker variants of the latter. The contributions of this dissertation are two-fold. First, we give new methods for studying distributed computing by establishing a strong connection between several weak variants of the port-numbering model and corresponding variants of modal logic. This makes it possible to apply existing logical tools, such as bisimulation, to understand computation in the distributed setting. We also give a full characterisation of the relationships between the models of computing, which has implications on the side of mathematical logic. Second, we prove the existence of various new non-empty complexity classes. One of our results studies the relationship between time and space complexity, which is a relatively new topic in distributed computing research. We demonstrate the existence of a problem that can be solved in a constant amount of space in a very weak model but nonetheless requires a non-constant amount of time even in a much stronger model of computing. Another result continues the recent success on developing complexity theory for the LOCAL model. We introduce a new technique which shows the existence of an infinite hierarchy of problems with novel time complexities. en
dc.description.abstract Tässä väitöskirjassa tutkitaan hajautetun laskennan teoriaa. Hajautetussa tilanteessa laskentaa suorittavat useat itsenäiset laskentayksiköt. Ne kommunikoivat viereisten laskentayksiköiden kanssa ja yhdessä tuottavat ratkaisun johonkin ongelmaan. Tällaisia järjestelmiä esiintyy laajalti niin tietoyhteiskunnassa kuin luonnossakin: hyviä esimerkkejä ovat Internet, usean suorittimen tietokonejärjestelmät, biologisen organismin solut tai vaikkapa ihmisten muodostamat sosiaaliset verkostot. Siksi on tärkeää saada tietoa tällaisten järjestelmien perustavanlaatuisista kyvyistä ja rajoituksista. Tässä työssä keskitytään hajautettuun laskentaan deterministissä ja synkronisissa viestinvälitysmalleissa. Tällaiset mallit jättävät huomiotta jotkin mahdolliset hajautettujen järjestelmien ominaisuudet, esimerkiksi asynkronian, ruuhkautumisen ja vikaantumisen, ja niiden sijaan korostavat tarvittavaa laskentayksiköiden välisen kommunikaation määrää. Yksiköiden odotetaan ratkaisevan ongelman, joka koskee järjestelmän pohjalla olevan kommunikaatioverkon rakennetta. Tarkalleen ottaen työssä tutkitaan paljon tutkittuja LOCAL- ja porttinumerointimalleja sekä useita viimeksi mainitun mallin heikompia variantteja. Väitöskirjalla on kaksi päätulosta. Ensiksi työssä esitellään uusia menetelmiä hajautetun laskennan tutkimiseen todistamalla vahva yhteys useiden porttinumerointimallin heikkojen varianttien ja vastaavien modaalilogiikan varianttien välille. Tämä mahdollistaa olemassaolevien logiikan välineiden, esimerkiksi bisimulaation, soveltamisen hajautetun laskennan ymmärtämiseen. Lisäksi työssä karakterisoidaan täydellisesti näiden laskennan mallien väliset suhteet, millä on seurauksia myös matemaattisen logiikan alueella. Toiseksi väitöskirjassa osoitetaan useiden uusien epätyhjien vaativuusluokkien olemassaolo. Yhdessä tuloksista tutkitaan aika- ja tilavaativuuden välistä suhdetta, joka on varsin uusi aihe hajautetun laskennan tutkimuksessa. Tulos osoittaa, että on olemassa ongelma, joka voidaan ratkaista vakiotilassa hyvin heikossa laskennan mallissa mutta joka vaatii vakiota suuremman määrän aikaa, vaikka laskennan malli olisi paljon vahvempi. Toinen tulos jatkaa viimeaikaista menestyksekästä vaativuusteorian kehittämistä LOCAL-mallille. Työssä esitellään uusi tekniikka, jonka avulla voidaan muodostaa ääretön hierarkia ongelmia, jotka kuuluvat uusiin aikavaativuusluokkiin. fi
dc.format.extent 71 + app. 73
dc.format.mimetype application/pdf en
dc.language.iso en en
dc.publisher Aalto University en
dc.publisher Aalto-yliopisto fi
dc.relation.ispartofseries Aalto University publication series DOCTORAL DISSERTATIONS en
dc.relation.ispartofseries 55/2019
dc.relation.haspart [Publication 1]: Lauri Hella, Matti Järvisalo, Antti Kuusisto, Juhana Laurinharju, Tuomo Lempiäinen, Kerkko Luosto, Jukka Suomela, Jonni Virtema. Weak models of distributed computing, with connections to modal logic. Distributed Computing, 2015, volume 28, issue 1, pp. 31–53. DOI: 10.1007/s00446-013-0202-3
dc.relation.haspart [Publication 2]: Tuomo Lempiäinen. Ability to count messages is worth Θ(Δ) rounds in distributed computing. In Proc. 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2016), New York, NY, USA, pp. 357–366, July 2016. DOI: 10.1145/2933575.2934567
dc.relation.haspart [Publication 3]: Tuomo Lempiäinen, Jukka Suomela. Constant space and non-constant time in distributed computing. In Proc. 21st International Conference on Principles of Distributed Systems (OPODIS 2017), Lisbon, Portugal, pp. 30:1–30:16, March 2018. Full Text in Acris/Aaltodoc: http://urn.fi/URN:NBN:fi:aalto-201812106087. DOI: 10.4230/LIPIcs.OPODIS.2017.30
dc.relation.haspart [Publication 4]: Alkida Balliu, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempiäinen, Dennis Olivetti, Jukka Suomela. New classes of distributed time complexity. In Proc. 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2018), Los Angeles, CA, USA, pp. 1307–1318, June 2018. DOI: 10.1145/3188745.3188860
dc.subject.other Computer science en
dc.title Logic and Complexity in Distributed Computing en
dc.title Logiikka ja vaativuus hajautetussa laskennassa fi
dc.type G5 Artikkeliväitöskirja fi
dc.contributor.school Perustieteiden korkeakoulu fi
dc.contributor.school School of Science en
dc.contributor.department Tietotekniikan laitos fi
dc.contributor.department Department of Computer Science en
dc.subject.keyword distributed computing en
dc.subject.keyword computational complexity theory en
dc.subject.keyword port-numbering model en
dc.subject.keyword LOCAL model en
dc.subject.keyword graph problems en
dc.subject.keyword LCL problems en
dc.subject.keyword modal logic en
dc.subject.keyword bisimulation en
dc.subject.keyword hajautettu laskenta fi
dc.subject.keyword laskennan vaativuusteoria fi
dc.subject.keyword porttinumerointimalli fi
dc.subject.keyword LOCAL-malli fi
dc.subject.keyword verkko-ongelmat fi
dc.subject.keyword LCL-ongelmat fi
dc.subject.keyword modaalilogiikka fi
dc.subject.keyword bisimulaatio fi
dc.identifier.urn URN:ISBN:978-952-60-8478-7
dc.type.dcmitype text en
dc.type.ontasot Doctoral dissertation (article-based) en
dc.type.ontasot Väitöskirja (artikkeli) fi
dc.contributor.supervisor Suomela, Jukka, Prof., Aalto University, Department of Computer Science, Finland
dc.opn Emek, Yuval, Prof., Technion, Israel
dc.rev Carton, Oliver, Prof., University Paris Diderot, France
dc.rev Emek, Yuval, Prof., Technion, Israel
dc.date.defence 2019-04-04
local.aalto.acrisexportstatus checked 2019-06-10_1828
local.aalto.formfolder 2019_03_21_klo_10_57
local.aalto.archive yes


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search archive


Advanced Search

article-iconSubmit a publication

Browse