Counting, clocking, and colouring - Fault-tolerant distributed coordination

 |  Login

Show simple item record

dc.contributor Aalto-yliopisto fi
dc.contributor Aalto University en
dc.contributor.advisor Suomela, Jukka, Prof., Aalto University, Department of Computer Science, Finland
dc.contributor.author Rybicki, Joel
dc.date.accessioned 2016-10-19T09:01:39Z
dc.date.available 2016-10-19T09:01:39Z
dc.date.issued 2016
dc.identifier.isbn 978-952-60-7065-0 (electronic)
dc.identifier.isbn 978-952-60-7066-7 (printed)
dc.identifier.issn 1799-4942 (electronic)
dc.identifier.issn 1799-4934 (printed)
dc.identifier.issn 1799-4934 (ISSN-L)
dc.identifier.uri https://aaltodoc.aalto.fi/handle/123456789/23023
dc.description.abstract This thesis studies fault-tolerant co-ordination and synchronisation in distributed systems. Such systems are prevalent in computing today: they range from large-scale communications networks to integrated hardware circuits. In essence, a distributed system consists of independent computational entities called nodes that solve some task together. In such a system, a common notion of time is critical for ensuring correct co-ordination and scheduling of actions. However, distributed systems are prone to scenarios in which the system may experience arbitrary transient failures, for example, due to various external disruptions. During a transient failure, the system ceases to operate correctly for some time which may put the system into an inconsistent state or even permanently damage parts of the system. In particular, the nodes in the system can lose synchrony. This thesis proposes synchronisation and scheduling algorithms that efficiently recover from such failures. The first part of this thesis considers self-stabilising Byzantine fault-tolerant algorithms. This means that we assume a strong adversarial fault model: the system starts from an arbitrary initial state and a large fraction of the nodes may be faulty. The faulty nodes may exhibit arbitrary misbehaviour, and in particular, give inconsistent information to other nodes. In this setting, we study the synchronous counting problem, which is a basic primitive for establishing a so-called digital clock. The task is to guarantee that eventually all correct nodes The main contribution of the first part is an array of techniques for designing fast and communication-efficient counting algorithms. In particular, we provide deterministic algorithms with asymptotically optimal stabilisation time and optimal resilience. That is, the algorithms quickly converge to correct behaviour and tolerate the largest possible number of faulty nodes. Compared to prior work, our solutions give an exponential improvement in the number of bits stored and transmitted by each node without resorting to randomisation or suboptimal resilience. The second part of this thesis investigates computational algorithm design and synthesis techniques. That is, we show how to automatically construct correct algorithms or prove their non-existence using computers. This is particularly attractive in the context of fault-tolerant systems, in which finding correct solutions is often a difficult task. We propose synthesis techniques based on propositional satisfiability solvers that yield novel state-optimal counting algorithms and tight bounds on the exact time complexity of distributed graph colouring. en
dc.description.abstract Tämä väitöstyö tutkii vikasietoisia algoritmeja koordinointi- ja ajastusongelmiin hajautetuissa järjestelmissä. Hajautetut järjestelmät koostuvat itsenäisistä laskentayksiköistä eli solmuista, joiden tavoite on suorittaa jokin tehtävä yhdessä. Esimerkkejä tälläisistä järjestelmistä ovat niin tietokone- ja viestintäverkot kuin erilaiset digitaalipiirit. Näissä järjestelmissä erityisesti solmujen tahdistus on tärkeää, jotta solmujen toiminnot suoritetaan oikeassa järjestyksessä. Hajautetut järjestelmät ovat usein alttiita vikatiloille, jotka voivat johtua ulkoisista tai sisäisistä häiriöistä. Häiriöiden johdosta järjestelmä voi hetkellisesti lakata toimimasta oikein, joutua sisäisesti ristiriitaiseen tilaan tai jopa osittain vaurioitua pysyvästi. Erityisesti vikatilanteissa solmut voivat ajautua epätahtiin aiheuttaen ongelmia toimintojen koordinoinnissa. Tässä työssä esitetään hajautettuja tahdistus- ja ajastusalgoritmeja, jotka toipuvat virhetilanteista tehokkaasti. Työn ensimmäisessä osassa tarkastellaan itsestabiloivia algoritmeja, jotka sietävät bysanttilaisia vikoja. Tämä tarkoittaa, että järjestelmän alkutila on mielivaltainen ja suuri osa solmuista voi olla pysyvästi viallisia. Vialliset solmut voivat poiketa määritellystä protokollasta mielivaltaisella tavalla sekä lähettää epäkonsistenttia ja väärää informaatiota muille järjestelmän solmuille. Tämän vahvan vikamallin puitteissa kehitämme synkronisia laskureita, jotka ovat eräs tapa muodostaa jaettu digitaalinen kello. Synkroninen laskuri takaa, että mikä tahansa onkaan järjestelmän alkutila ja miten tahansa vialliset solmut käyttäytyvät, lopulta kaikilla ehjillä solmuilla on yhtenäinen käsitys tasaisesti etenevän laskurin arvosta. Työssä esitellään menetelmiä nopeiden ja kommunikaatiotehokkaiden synkronisten laskurien suunnitteluun. Kehitämme deterministisiä laskureita, jotka stabiloituvat asymptoottisesti optimaalisessa ajassa sekä sietävät suurimman mahdollisen määrän viallisia solmuja. Aiempiin ratkaisuihin verrattuna työssä esitetyt algoritmit vaativat eksponentiaalisesti vähemmän bittejä solmun tilan ja lähetettyjen viestien koodaukseen, eikä algoritmien tarvitse turvautua satunnaisuuteen tai tinkiä vikasietoisuudesta. Työn toinen osa keskittyy laskennalliseen algoritmisuunnitteluun. Kehitämme tietokoneavusteisia menetelmiä, joilla voi automaattisesti konstruoida oikeellisia hajautettuja algoritmeja tai osoittaa, että halutunlaisia algoritmeja ei ole olemassa. Nämä menetelmät soveltuvat erityisesti vikasietoisten järjestelmien suunnitteluun, sillä oikeellisten algoritmien kehittäminen vahvoissa vikamalleissa on usein vaikeaa. Esitämme kuinka hyödyntää propositiologiikan toteutuvuusratkaisimia tilaoptimaalisten laskurien tuottamiseen sekä verkon värityksen tarkan aikavaativuuden laskemiseen. fi
dc.format.extent 107 + app. 70
dc.format.mimetype application/pdf en
dc.language.iso en en
dc.publisher Aalto University en
dc.publisher Aalto-yliopisto fi
dc.relation.ispartofseries Aalto University publication series DOCTORAL DISSERTATIONS en
dc.relation.ispartofseries 208/2016
dc.relation.haspart [Publication 1]: Danny Dolev, Keijo Heljanko, Matti Järvisalo, Janne H. Korhonen, Christoph Lenzen, Joel Rybicki, Jukka Suomela, and Siert Wieringa. Synchronous Counting and Computational Algorithm Design. Journal of Computer and System Sciences, 82, 2, pp. 310–332, March 2016. DOI: 10.1016/j.jcss.2015.09.002
dc.relation.haspart [Publication 2]: Christoph Lenzen, Joel Rybicki, and Jukka Suomela. Efficient Counting with Optimal Resilience. Manuscript submitted for publication. Extended and revised version of two conference papers [86, 88], June 2016.
dc.relation.haspart [Publication 3]: Joel Rybicki and Jukka Suomela. Exact Bounds for Distributed Graph Colouring. In Post-Proceedings of 22nd International Colloquium on Structural Information and Communication Complexity (SIROCCO 2015), Montserrat, Spain, July 14–16, 2015. pp. 46-60, November 2015. DOI: 10.1007/978-3-319-25258-2_4
dc.subject.other Computer science en
dc.title Counting, clocking, and colouring - Fault-tolerant distributed coordination en
dc.title Laskureita, kellotusta ja väritystä: Vikasietoinen hajautettu koordinointi fi
dc.type G5 Artikkeliväitöskirja fi
dc.contributor.school Perustieteiden korkeakoulu fi
dc.contributor.school School of Science en
dc.contributor.department Tietotekniikan laitos fi
dc.contributor.department Department of Computer Science en
dc.subject.keyword distributed algorithms en
dc.subject.keyword fault tolerance en
dc.subject.keyword synchronisation en
dc.subject.keyword hajautetut algoritmit fi
dc.subject.keyword vikasietoisuus fi
dc.subject.keyword synkronointi fi
dc.identifier.urn URN:ISBN:978-952-60-7065-0
dc.type.dcmitype text en
dc.type.ontasot Doctoral dissertation (article-based) en
dc.type.ontasot Väitöskirja (artikkeli) fi
dc.contributor.supervisor Suomela, Jukka, Prof., Aalto University, Department of Computer Science, Finland
dc.opn Wattenhofer, Roger, Prof., ETH Zurich, Switzerland
dc.contributor.lab Distributed Algorithms en
dc.rev Moses, Yoram, Prof., Technion – Israel Institute of Technology, Israel
dc.rev Scheideler, Christian, Prof., University of Paderborn, Germany
dc.date.defence 2016-11-19


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search archive


Advanced Search

article-iconSubmit a publication

Browse

My Account