A Classification of Weak Models of Distributed Computing

Tämä tutkielma käsittelee hajautetun laskennan teoreettisia perusteita. Hajautetussa laskennassa tarkastellaan verkkoja, joissa jokainen solmu on laskentayksikkö ja suorittaa samaa algoritmia. Verkko määrittelee solmujen väliset kommunikaatioyhteydet ja on samalla syöte algoritmille. Kukin solmu kommunikoi viereisten solmujen kanssa synkronisesti ja tuottaa lopulta oman tulosteensa. Solmujen tulosteet yhdessä muodostavat ratkaisun johonkin verkon rakenteeseen liittyvään ongelmaan. Tärkein algoritmien käyttämä resurssi on siirrettävän informaation määrä. Näin ollen algoritmin ajoaika määritellään kommunikaatiokierrosten lukumääräksi; solmut voivat tehdä mielivaltaisen paljon paikallista laskentaa. Tutkielmassa esitellään useita hajautetun laskennan malleja, jotka ovat heikompia versioita paljon tutkitusta porttinumerointimallista. Porttinumerointimallissa asteluvun d solmulla on d tulevaa porttia ja d lähtevää porttia, ja molemmat on numeroitu luvuilla 1, 2, ..., d siten, että tulevien ja lähtevien porttien numerointi on konsistentti. Kaikkien tässä mallissa ratkeavien verkko-ongelmien luokasta käytetään merkintää VVc. Työssä määritellään seuraavat luokan VVc aliluokat, jotka vastaavat heikompia laskennan malleja: VV: Tulevien ja lähtevien porttien numerointi ei ole välttämättä konsistentti. MV: Tulevia portteja ei ole numeroitu; solmut vastaanottavat monijoukon viestejä. SV: Tulevia portteja ei ole numeroitu; solmut vastaanottavat joukon viestejä. VB: Lähteviä portteja ei ole numeroitu; solmut lähettävät saman viestin kaikille naapureilleen. MB: Luokkien MV ja VB yhdistelmä. SB: Luokkien SV ja VB yhdistelmä. Tässä tutkielmassa esitetään mallien laskennallisen voiman täydellinen luokittelu. Malleja vastaavien vaativuusluokkien todistetaan muodostavan seuraavan lineaarisen järjestyksen: SB ⊈ MB = VB ⊈ SV = MV = VV ⊈ VVc. Yhtälön SV = MV todistamiseksi osoitetaan, että mitä tahansa algoritmia, joka vastaanottaa monijoukon viestejä, voi simuloida algoritmilla, joka vastaanottaa vain joukon viestejä. Simulaatio kasvattaa ajoaikaa 2∆ - 2 kommunikaatiokierroksella, jossa ∆ on yläraja verkon maksimiasteluvulle. Uutena tuloksena tutkielmassa todistetaan, että simulaatiotulos on optimaalinen: lisäkierroksia tarvitaan vähintään 2∆ - 2. Lisäksi määritellään verkko-ongelma, joka voidaan ratkaista yhdessä kommunikaatiokierroksessa monijoukon viestejä vastaanottavalla algoritmilla, mutta joka vaatii vähintään ∆ kierrosta, kun se ratkaistaan vain joukon viestejä vastaanottavalla algoritmilla.