Lower bounds in distributed computing

Juho Hirvonen

Lower bounds in distributed computing

Julkaisun otsikon käännös: Lower bounds in distributed computing

Juho Hirvonen

Tietotekniikan laitos

Tutkimustuotos: Doctoral Thesis › Collection of Articles

Abstrakti

Tutkin tässä väitöskirjatyössä hajautetun laskennan vaativuusteoriaa synkronisissa viestinvälitysmalleissa. Työ keskittyy paikallisiin ongelmiin, eli ongelmiin, joiden ratkaisu voidaan löytää käyttäen vain vähäinen määrä kommunikaatiota. Tutkitussa asetelmassa kommunikaatioverkko on myös ongelman syöte. Hajautetun järjestelmän täytyy löytää ratkaisu, joka liittyy tämän verkon rakenteeseen ja jokaisen verkon solmun täytyy tuottaa oma osansa tulosteesta. Työssä tutkitaan hajautetun laskennan standardimalleihin kuuluvaa LOCAL-mallia. Tämä malli ei huomioi erilaisia hajautetun laskennan haasteita, kuten vikoja, ruuhkautumista, tai laskenta- ja muistivaatimuksia. Tätä mallia tutkitaan paikallisuuden ymmärtämiseksi: kuinka kauas informaatiota täytyy propagoida, jotta ongelma voidaan ratkaista hajautetusti? Kuinka monta kommunikaatiokierrosta ongelman ratkaiseminen vaatii? Monet kiinnostavat ongelmat, kuten kommunikaatioverkon virittävän puun löytäminen, ovat globaaleja ongelmia. Tässä työssä tarkastelemme toista ääripäätä: ongelmia, jotka voidaan ratkaista ajassa, joka on kokonaan riippumaton tai korkeintaan heikosti riippuvainen kommunikaatioverkon koosta. Tällaisia ongelmia ovat esimerkiksi klassiset symmetrianrikkomisongelmat kuten väritys ja riippumattomat joukot. Tyypillisesti näiden ongelmien aikavaativuus riippuu kahdesta tekijästä, verkon koosta ja sen maksimiasteluvusta. Yhteys verkon kokoon on melko hyvin ymmärretty, mutta riippuvuus maksimiasteluvusta ei. Tunnettujen ylä- ja alarajojen erotus on eksponentiaalinen. Kehittämämme alarajatekniikka antaa ensimmäisen maksimiasteluvun suhteen lineaarisen alarajan luonnolliselle verkko-ongelmalle. Lisäksi olemme tutkineet solmuille annettavien uniikkien nimien vaikutusta. Vaikka tyypillisesti uniikit tunnisteet eivät auta vakioaikaisia algoritmeja, näytämme, että tietyissä tilanteissa niitä voidaan hyödyntää. Paikallisten päätösongelmien tapauksessa, jossa solmujen täytyy tarkastaa annettu ratkaisu uuden rakentamisen sijaan, karakterisoimme sen informaation määrän, joka riittää ja vaaditaan uniikkien tunnisteiden korvaamiseen. Viimeiseksi tutkimme epädeterministisyyden vaikutusta paikallisiin päätösongelmiin. Kehitämme paikallisen päätöshierarkian, joka on analoginen keskitetyn laskennan polynomisen hierarkian kanssa, ja tutkimme tämän hierarkian rakennetta. Väitöskirjatyö keskittyy rakenteellisiin tuloksiin, erityisesti mahdottomuustuloksiin. Verkon asteluvusta riippuvat alarajatulokset edustavat täysin uudenlaista alarajatekniikkaa, joka hyödyntää verkossa olevaa symmetriaa.

Julkaisun otsikon käännös	Lower bounds in distributed computing
Alkuperäiskieli	Englanti
Pätevyys	Tohtorintutkinto
Myöntävä instituutio	Aalto-yliopisto
Valvoja/neuvonantaja	Suomela, Jukka, Vastuuprofessori Suomela, Jukka, Ohjaaja
Kustantaja	Aalto University
Painoksen ISBN	978-952-60-7138-1
Sähköinen ISBN	978-952-60-7137-4
Tila	Julkaistu - 2016
OKM-julkaisutyyppi	G5 Artikkeliväitöskirja

Tutkimusalat

hajautettu laskenta
paikalliset algoritmit
alarajat

Pääsy asiakirjaan

http://urn.fi/URN:ISBN:978-952-60-7137-4Lisenssi: Määrittelemätön

Siteeraa tätä

@phdthesis{74c20010d52e460aa380534734d492ca,

title = "Lower bounds in distributed computing",

abstract = "In this thesis I study the complexity theory of distributed computing in synchronous message passing models. The focus is on highly local problems, that is, problems in which very little communication is required. In this setting the underlying communication network is also the input graph. The distributed system must collectively compute a solution to a problem related to the structure of this network, with each computer producing its own part of the output.We study the LOCAL model, one of the standard models in distributed computing. It abstracts away faults, congestion, computational requirements, memory requirements, and many other challenges in distributed computing. We study this model to understand the locality aspect of distributed computing: How far does information have to propagate in distributed problem solving? How many communication rounds is required? Many interesting problems, such as finding a spanning tree in the communication network, are inherently global. We are interested in the other extreme: problems that can be solved in time that is weakly dependent or completely independent of the size of the communication network. Typical problems include classical symmetry breaking tasks such as colouring or maximal independent set. Typically the time complexity of such problems depends on two parameters: the size and the maximum degree of the input graph. The connection with the first parameter is well understood with tight upper and lower bounds. The connection with the maximum degree is much less well understood, with an exponential gap between the upper and lower bounds. We develop a new lower bound technique to give the first lower bound for a natural graph problem that is linear in the maximum degree.In addition we study the power of unique in several contexts. We show that while usually unique identifiers are unhelpful for constant-time algorithms, there are certain special cases in which they do help. In the context of local decision, where the task is essentially to verify a given solution instead of constructing a new one, we characterize the minimal information that is sufficient to replace unique identifiers. Finally, we also study the power of nondeterminism in local decision. We develop a local hierarchy in a manner analogous to the polynomial hierarchy in centralized computing, and study the structure of this hierarchy.The focus of this thesis is on structural results, especially lower bounds. The lower bounds as a function of the maximum degree of the graph employ a completely novel proof technique based on graph symmetries.",

keywords = "distributed computing, local algorithms, lower bounds, hajautettu laskenta, paikalliset algoritmit, alarajat, distributed computing, local algorithms, lower bounds",

author = "Juho Hirvonen",

year = "2016",

language = "English",

isbn = "978-952-60-7138-1",

series = "Aalto University publication series DOCTORAL DISSERTATIONS",

publisher = "Aalto University",

number = "239",

address = "Finland",

school = "Aalto University",

}

TY - BOOK

T1 - Lower bounds in distributed computing

AU - Hirvonen, Juho

PY - 2016

Y1 - 2016

N2 - In this thesis I study the complexity theory of distributed computing in synchronous message passing models. The focus is on highly local problems, that is, problems in which very little communication is required. In this setting the underlying communication network is also the input graph. The distributed system must collectively compute a solution to a problem related to the structure of this network, with each computer producing its own part of the output.We study the LOCAL model, one of the standard models in distributed computing. It abstracts away faults, congestion, computational requirements, memory requirements, and many other challenges in distributed computing. We study this model to understand the locality aspect of distributed computing: How far does information have to propagate in distributed problem solving? How many communication rounds is required? Many interesting problems, such as finding a spanning tree in the communication network, are inherently global. We are interested in the other extreme: problems that can be solved in time that is weakly dependent or completely independent of the size of the communication network. Typical problems include classical symmetry breaking tasks such as colouring or maximal independent set. Typically the time complexity of such problems depends on two parameters: the size and the maximum degree of the input graph. The connection with the first parameter is well understood with tight upper and lower bounds. The connection with the maximum degree is much less well understood, with an exponential gap between the upper and lower bounds. We develop a new lower bound technique to give the first lower bound for a natural graph problem that is linear in the maximum degree.In addition we study the power of unique in several contexts. We show that while usually unique identifiers are unhelpful for constant-time algorithms, there are certain special cases in which they do help. In the context of local decision, where the task is essentially to verify a given solution instead of constructing a new one, we characterize the minimal information that is sufficient to replace unique identifiers. Finally, we also study the power of nondeterminism in local decision. We develop a local hierarchy in a manner analogous to the polynomial hierarchy in centralized computing, and study the structure of this hierarchy.The focus of this thesis is on structural results, especially lower bounds. The lower bounds as a function of the maximum degree of the graph employ a completely novel proof technique based on graph symmetries.

AB - In this thesis I study the complexity theory of distributed computing in synchronous message passing models. The focus is on highly local problems, that is, problems in which very little communication is required. In this setting the underlying communication network is also the input graph. The distributed system must collectively compute a solution to a problem related to the structure of this network, with each computer producing its own part of the output.We study the LOCAL model, one of the standard models in distributed computing. It abstracts away faults, congestion, computational requirements, memory requirements, and many other challenges in distributed computing. We study this model to understand the locality aspect of distributed computing: How far does information have to propagate in distributed problem solving? How many communication rounds is required? Many interesting problems, such as finding a spanning tree in the communication network, are inherently global. We are interested in the other extreme: problems that can be solved in time that is weakly dependent or completely independent of the size of the communication network. Typical problems include classical symmetry breaking tasks such as colouring or maximal independent set. Typically the time complexity of such problems depends on two parameters: the size and the maximum degree of the input graph. The connection with the first parameter is well understood with tight upper and lower bounds. The connection with the maximum degree is much less well understood, with an exponential gap between the upper and lower bounds. We develop a new lower bound technique to give the first lower bound for a natural graph problem that is linear in the maximum degree.In addition we study the power of unique in several contexts. We show that while usually unique identifiers are unhelpful for constant-time algorithms, there are certain special cases in which they do help. In the context of local decision, where the task is essentially to verify a given solution instead of constructing a new one, we characterize the minimal information that is sufficient to replace unique identifiers. Finally, we also study the power of nondeterminism in local decision. We develop a local hierarchy in a manner analogous to the polynomial hierarchy in centralized computing, and study the structure of this hierarchy.The focus of this thesis is on structural results, especially lower bounds. The lower bounds as a function of the maximum degree of the graph employ a completely novel proof technique based on graph symmetries.

KW - distributed computing

KW - local algorithms

KW - lower bounds

KW - hajautettu laskenta

KW - paikalliset algoritmit

KW - alarajat

KW - distributed computing

KW - local algorithms

KW - lower bounds

M3 - Doctoral Thesis

SN - 978-952-60-7138-1

T3 - Aalto University publication series DOCTORAL DISSERTATIONS

PB - Aalto University

ER -

Lower bounds in distributed computing

Abstrakti

Tutkimusalat

Pääsy asiakirjaan

Sormenjälki

Siteeraa tätä