Väitös tietotekniikan alalta, M.Sc. Jan Studený

Väitöskirjan nimi: Designing and finding very fast distributed algorithms for bounded-degree graphs

Tohtoriopiskelija: Jan Studený
Vastaväittäjä: apulaisprofessori Seth Gilbert, National University of Singapore, Singapore
Kustos: apulaisprofessori Jukka Suomela, Aalto-yliopiston perustieteiden korkeakoulu, tietotekniikan laitos

Hajautetussa laskennassa tutkitaan järjestelmiä, joissa erilliset laskentayksiköt kommunikoivat keskenään ja pyrkivät saavuttamaan yhteisen päämäärän. Tässä väitöskirjassa tarkastelemme verkko-ongelmien ratkomista tilanteessa, jossa verkko on harva, eli verkon solmuilla on vähän naapureita.

Ensiksi tutkimme ongelmia, joiden ratkaisut voidaan tarkistaa paikallisesti (locally checkable labeling, LCL). Tämä laaja ongelmaperhe sisältää sellaisia tehtäviä kuin verkon värittäminen, maksimaalinen riippumattoman joukon ja maksimaalinen pariutuksen löytäminen sekä erilaiset suunnistusongelmat. Keskeinen tavoite on luonnehtia LCL-ongelmat täydellisesti eri verkkoperheissä ja automaattisesti tuottaa näille ongelmille asymptoottisesti optimaalisia algoritmeja. Työssä on saavutettu täydellinen luonnehdinta seuraaville verkkoperheille: polut, syklit ja säännölliset juurelliset puut. Lisäksi meillä on osittainen luonnehdinta säännöllisille suuntaamattomille puille. Näistä kaikista luokittelualgoritmeista on nyt olemassa myös yhtenäiset toteutukset. Osa tuloksista perustuu uuteen yhteyteen automaattiteorian kanssa, kun taas osa käyttää työssä esiteltyä "ratkeavuussertifikaatin" käsitettä.

Väitöskirjan toisessa osassa keskitytään harvojen matriisien kertolaskuun kaistanleveysrajoitetuissa järjestelmissä. Näytämme, että tasaisesti harvojen matriisien tapauksessa (kussakin rivissä ja sarakkeessa on enintään d nollasta poikkeavaa alkioita) on olemassa nopea algoritmi, jonka suorituskyky rikkoo neliöllisen rajan parametrin d suhteen. Yksi käytetyistä tekniikoista on etsiä alueita, jotka ovat paikallisesti tiheitä, ja käyttää tehokkaampia tiheiden matriisien kertolaskualgoritmeja näiden osien laskemiseen. Tämä tutkimus edistää teoreettista ymmärrystä harvojen verkkojen käsittelystä hajautetuissa järjestelmistä ja rikastuttaa meneillään olevaa tutkimusta verkkoteorian, automaattiteorian ja hajautetun laskennan leikkauskohdassa. Tulokset osoittavat, että tiettyjen verkkoperheiden LCL-ongelmat voidaan täysin luokitella, ja matriisien kertolaskussa käytetyt tekniikat osoittavat, miten suorituskykyä on mahdollista parantaa sellaisissakin järjestelmissä, joissa viestinnän kaistanleveyttä on rajoitettu.

Tulokset ovat sovellettavissa hajautettuihin järjestelmiin, joissa verkot ovat harvoja (esimerkiksi sensoriverkot ja vertaisverkkojärjestelmät). Matriisikertolaskutulokset ovat merkityksellisiä aloille, joissa käsitellään isoa dataa, jonka rakenne muodostaa harvan verkon.

Avaisanat: hajautetut algoritmit, paikallisesti tarkastettavat merkinnät, matriisikertolasku, paikallisuus, hajautetun laskennan vaativuus, algoritmisynteesi, ruuhkainen klikki, matalakaistamalli

Linkki väitöskirjan sähköiseen esittelykappaleeseen (esillä 10 päivää ennen väitöstä): https://aaltodoc.aalto.fi/doc_public/eonly/riiputus/ 

Yhteystiedot:

Perustieteiden korkeakoulun väitöskirjat: https://aaltodoc.aalto.fi/handle/123456789/52