Väitös tietojenkäsittelytieteen alalta, FM Tuomo Lempiäinen

Filosofian maisteri Tuomo Lempiäinen väittelee torstaina 4.4.2019 klo 12 Aalto-yliopiston perustieteiden korkeakoulussa, salissa M1, Otakaari 1, Espoo. Väitöskirjassa "Logic and Complexity in Distributed Computing" tutkittiin hajautetun laskennan teoriaa kahdesta näkökulmasta. Työssä muodostettiin yhteys hajautetun laskennan ja matemaattisen logiikan välille sekä todistettiin useiden uusien vaativuusluokkien olemassaolo.

Hajautetut järjestelmät koostuvat useista erillisistä toimijoista tai laskentayksiköistä, jotka kykenevät viestimään keskenään. Tällaisia järjestelmiä ovat esimerkiksi erilaiset tietoverkot kuten Internet, elävien olentojen solurakenne sekä ihmisten muodostamat sosiaaliset verkostot. Tässä väitöskirjassa tutkittiin hajautettuja järjestelmiä koskevia perustavanlaatuisia kysymyksiä tietojenkäsittelyteorian näkökulmasta.

Toinen väitöskirjan kahdesta päätuloksesta muodostaa uuden yhteyden hajautetun laskennan ja matemaattisen logiikan välille. Tulos osoittaa, että tietyt hajautetun laskennan mallit vastaavat ilmaisuvoimaltaan suoraan tiettyjä modaalilogiikan variantteja. Tämä mahdollistaa esimerkiksi olemassa olevien logiikan työkalujen käytön hajautetun laskennan tutkimisessa.

Olennainen hajautettuja järjestelmiä koskeva kysymys on kommunikaation määrä: kuinka paljon laskentayksiköiden on viestittävä keskenään voidakseen ratkaista viestintäverkon rakennetta koskevia ongelmia? Tätä kutsutaan ongelmien aikavaativuudeksi. Lisäksi voidaan tarkastella esimerkiksi tilavaativuutta – yksittäisen laskentayksikön tarvitsemaa tallennustilan määrää.

Väitöskirjan toinen päätulos koskee uusia vaativuusluokkia. Työssä löydettiin yhteys aika- ja tilavaativuuden välille määrittelemällä ongelma, jonka tilavaativuus on riippumaton verkon koosta, mutta aikavaativuus kasvaa lineaarisesti. Lisäksi työssä kehitettiin menetelmä, joka osoittaa, että on olemassa ääretön hierarkia ennestään tuntemattomia aikavaativuusluokkia. Tämä on suoraa jatkumoa viime aikoina huomattavasti edenneelle hajautetun vaativuusteorian kehittämiselle.

Vastaväittäjä: Associate Professor Yuval Emek, Technion, Israel

Kustos: apulaisprofessori Jukka Suomela, Aalto-yliopiston perustieteiden korkeakoulu, tietotekniikan laitos

Elektroninen väitöskirja: http://urn.fi/URN:ISBN:978-952-60-8478-7