Väitös tietotekniikan alalta, M.Sc. Mélanie Cambus

Väitöskirjan nimi: Distributed computing in dynamic and faulty networks: distributed graph algorithms and multidimensional agreement 

Väittelijä: Mélanie Cambus
Vastaväittäjä: professori John Augustine, Indian Institute of Technology Madras (IIT), India
Kustos: apulaisprofessori Jara Uitto, Aalto-yliopiston perustieteiden korkeakoulu 

Hajautetussa laskennassa monet itsenäiset laitteet ratkovat vaativia ongelmia yhdessä ilman keskitettyä koordinaattoria. Hajautettuja järjestelmiä voidaan mallintaa verkkoina, joissa solmut vastaavat laskentayksiköitä ja kaaret kommunikaatiolinkkejä. Tämä mallinnustapa antaa perustan skaalautuvien hajautettujen algoritmien suunnitteluun. Väitöskirjan ensimmäinen osa käsittelee perustavanlaatuisia ongelmia valtavissa verkoissa. Ensimmäinen algoritminen ongelma on korrelaatioklusterointi, jota usein ratkomaan tiedonlouhimisprosesseissa. Syötteenä on datapisteitä, jotka ovat pareittain joko samanlaisia tai erilaisia ja tavoitteena on ryhmitellä samanlaiset datapisteet keskenään ja erotella erilaiset. Yksi väitöskirjan keskeisistä tuloksista on approksimaatioalgoritmi semi-streaming -mallissa, joka saavuttaa tehokkaasti lähes 3-approksimaation optimiratkaisuun.

Toinen keskeinen tutkimusongelma on 2-ruling set -ongelma. Tavoitteena on valita solmujoukko, jossa solmut ovat keskenään riippumattomia ja jokaisella syöteverkon solmulla on yksi solmujoukon solmu korkeintaan etäisyydellä 2. Väitöstutkimuksessa suunniteltiin vakioaikaisia algoritmeja tähän ongelmaan useissa perustavanlaatuisissa hajautetun laskennan malleissa ja muistirajoitteisissa laskennan malleissa. 

Väitöskirjan toinen osa käsittelee moniulotteista yksimielisyysongelmaa. Hajautetut laskentayksiköt toimivat ympäristössä, joissa osa yksiköistä voi toimia mielivaltaisesti. Yksimielisyys vastaa sitä, että oikein toimivien laskentayksiköiden täytyy laskennan lopuksi tuottaa yhtenäinen tuloste, esimerkiksi binäärinen vektori. Väitöskirjatutkimuksessa suunnitellaan uusia algoritmeja yhteisymmärryksen approksimointiin ja tutkitaan approksimoinnin laadun ja tyypillisten yksimielisyyden takeiden suhdetta. Esittelemme myös algoritmeja, jotka on optimoitu yhdistettyä oppimista varten. 

Väitöskirjatutkimuksen tuloksilla on käyttötarkoituksia useilla eri aloilla, esimerkiksi data-analyysissa, verkkohallinnassa ja vikasietoisissa järjestelmissä. Tehokkaat, skaalautuvat ja robustit hajautetut algoritmit tuovat uusia menetelmiä ison datan käsittelyyn ja vakauttavat hajautetusti koulutettuja malleja.

Linkki väitöskirjan sähköiseen esittelykappaleeseen (esillä 7 päivää ennen väitöstä): Aaltodoc