| dc.date.accessioned |
2014-12-01T07:30:29Z |
und |
| dc.date.accessioned |
2017-10-24T12:21:38Z |
|
| dc.date.available |
2014-12-01T07:30:29Z |
und |
| dc.date.available |
2017-10-24T12:21:38Z |
|
| dc.date.issued |
2014-12-01T07:30:29Z |
|
| dc.identifier.uri |
http://radr.hulib.helsinki.fi/handle/10138.1/4324 |
und |
| dc.identifier.uri |
http://hdl.handle.net/10138.1/4324 |
|
| dc.title |
A Classification of Weak Models of Distributed Computing |
en |
| ethesis.discipline |
Mathematics |
en |
| ethesis.discipline |
Matematiikka |
fi |
| ethesis.discipline |
Matematik |
sv |
| ethesis.discipline.URI |
http://data.hulib.helsinki.fi/id/44bc4f03-6035-4697-993b-cfc4cea667eb |
|
| ethesis.department.URI |
http://data.hulib.helsinki.fi/id/61364eb4-647a-40e2-8539-11c5c0af8dc2 |
|
| ethesis.department |
Institutionen för matematik och statistik |
sv |
| ethesis.department |
Department of Mathematics and Statistics |
en |
| ethesis.department |
Matematiikan ja tilastotieteen laitos |
fi |
| ethesis.faculty |
Matematisk-naturvetenskapliga fakulteten |
sv |
| ethesis.faculty |
Matemaattis-luonnontieteellinen tiedekunta |
fi |
| ethesis.faculty |
Faculty of Science |
en |
| ethesis.faculty.URI |
http://data.hulib.helsinki.fi/id/8d59209f-6614-4edd-9744-1ebdaf1d13ca |
|
| ethesis.university.URI |
http://data.hulib.helsinki.fi/id/50ae46d8-7ba9-4821-877c-c994c78b0d97 |
|
| ethesis.university |
Helsingfors universitet |
sv |
| ethesis.university |
University of Helsinki |
en |
| ethesis.university |
Helsingin yliopisto |
fi |
| dct.creator |
Lempiäinen, Tuomo |
|
| dct.issued |
2014 |
|
| dct.language.ISO639-2 |
eng |
|
| dct.abstract |
In this thesis we study the theoretical foundations of distributed computing. Distributed computing is concerned with graphs, where each node is a computing unit and runs the same algorithm. The graph serves both as a communication network and as an input for the algorithm. Each node communicates with adjacent nodes in a synchronous manner and eventually produces its own output. All the outputs together constitute a solution to a problem related to the structure of the graph. The main resource of interest is the amount of information that nodes need to exchange. Hence the running time of an algorithm is defined as the number of communication rounds; any amount of local computation is allowed.
We introduce several models of distributed computing that are weaker versions of the well-established port-numbering model. In the port-numbering model, a node of degree d has d input ports and d output ports, both numbered with 1, 2, ..., d such that the port numbers are consistent. We denote by VVc the class of all graph problems that can be solved in this model. We define the following subclasses of VVc, corresponding to the weaker models:
VV: Input and output port numbers are not necessarily consistent.
MV: Input ports are not numbered; nodes receive a multiset of messages.
SV: Input ports are not numbered; nodes receive a set of messages.
VB: Output ports are not numbered; nodes broadcast the same message to all neighbours.
MB: Combination of MV and VB.
SB: Combination of SV and VB.
This thesis presents a complete classification of the computational power of the models. We prove that the corresponding complexity classes form the following linear order:
SB ⊈ MB = VB ⊈ SV = MV = VV ⊈ VVc.
To prove SV = MV, we show that any algorithm receiving a multiset of messages can be simulated by an algorithm that receives only a set of messages. The simulation causes an additive overhead of 2∆ - 2 communication rounds, where ∆ is an upper bound for the maximum degree of the graph.
As a new result, we prove that the simulation is optimal: it is not possible to achieve a simulation overhead smaller than 2∆ - 2. Furthermore, we construct a graph problem that can be solved in one round of communication by an algorithm receiving a multiset of messages, but requires at least ∆ rounds when solved by an algorithm receiving only a set of messages. |
en |
| dct.abstract |
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. |
fi |
| dct.language |
en |
|
| ethesis.language.URI |
http://data.hulib.helsinki.fi/id/languages/eng |
|
| ethesis.language |
English |
en |
| ethesis.language |
englanti |
fi |
| ethesis.language |
engelska |
sv |
| ethesis.thesistype |
pro gradu-avhandlingar |
sv |
| ethesis.thesistype |
pro gradu -tutkielmat |
fi |
| ethesis.thesistype |
master's thesis |
en |
| ethesis.thesistype.URI |
http://data.hulib.helsinki.fi/id/thesistypes/mastersthesis |
|
| dct.identifier.urn |
URN:NBN:fi-fe2017112251644 |
|
| dc.type.dcmitype |
Text |
|
