Väitös tietotekniikan alalta, FM Juho Hirvonen

2016-11-25 10:00:00 2016-11-25 23:59:59 Europe/Helsinki Väitös tietotekniikan alalta, FM Juho Hirvonen Väitöskirjan nimi on: Lower bounds in distributed computing http://sci.aalto.fi/fi/midcom-permalink-1e69202759f492a920211e6ab7c61466cbf82458245 Konemiehentie 2, 02150, Espoo

Väitöskirjan nimi on: Lower bounds in distributed computing

25.11.2016 / 10:00
salissa T2, Konemiehentie 2, 02150, Espoo, FI

Filosofian maisteri Juho Hirvonen väittelee perjantaina 25.11.2016 klo 10 Aalto-yliopiston perustieteiden korkeakoulussa, salissa T2, Konemiehentie 2, Espoo. Väitöskirjassa "Lower bounds in distributed computing" tutkitaan hajautetun laskennan teoreettisia perusteita. Siinä todistetaan useita mahdottomuustuloksia, jotka kertovat kuinka kaukaa informaatiota täytyy hakea erilaisten hajautettujen verkko-ongelmien ratkaisemiseksi.

Hajautetussa laskennassa tutkitaan tilannetta, jossa useiden tietokoneiden täytyy tehdä yhteistyötä ratkaistakseen jokin laskennallinen ongelma. Tietokoneet ovat osa tietoliikenneverkkoa, ja voivat keskustella keskenään jos ne on kytketty toisiinsa.

Tietoliikenneverkot ovat usein suuria ja harvoja, eli niissä on paljon tietokoneita, mutta kukin tietokone on kytketty suoraan vain pieneen osaan muista koneista. Tiedon kuljettaminen verkossa on tyypillisesti hidasta kunkin tietokoneen sisällä tapahtuvaan laskentaan verrattuna. Täten se, kuinka kaukaa, eli kuinka monen välikäden kautta, tietoverkosta täytyy hakea tietoa kunkin ongelman ratkaisemiseksi.

Tässä väitöstutkimuksessa on tutkittu hajautetun laskennan paikallisuutta, eli ongelmia, joissa ratkaisun löytäminen edellyttää tiedon kuljettamista vain kunkin tietokoneen lähiympäristöstä. Työ keskittyy todistamaan alarajoja eli tuloksia, jotka osoittavat, että tietoa täytyy kerätä ainakin tietyltä etäisyydeltä annetun ongelman ratkaisemiseksi.

Eräs työn keskeisistä tuloksista on todistaa uudentyyppisiä alarajatuloksia pariutusongelmille. Nämä tulokset kertovat uudentyyppisestä, perustavaa laatua olevasta haasteesta hajautetussa laskennassa. Tulokset on todistettu uudentyyppistä todistustekniikkaa käyttäen.

Väitöstiedote (pdf)

Vastaväittäjä: professori Michael Elkin, Ben-Gurion University of Negev, Israel

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

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