Logic and Complexity in Distributed Computing

Tutkimustuotos

Tutkijat

Organisaatiot

Kuvaus

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.

Yksityiskohdat

AlkuperäiskieliEnglanti
PätevyysTohtorintutkinto
Myöntävä instituutio
Valvoja/neuvonantaja
Kustantaja
  • Aalto University
Painoksen ISBN978-952-60-8477-0
Sähköinen ISBN978-952-60-8478-7
TilaJulkaistu - 2019
OKM-julkaisutyyppiG5 Tohtorinväitöskirja (artikkeli)

    Tutkimusalat

  • hajautettu laskenta, laskennan vaativuusteoria, porttinumerointimalli, LOCAL-malli, verkko-ongelmat, LCL-ongelmat, modaalilogiikka, bisimulaatio

ID: 33310579