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

Thumbnail Image
Files
isbn9789526070650.pdf (1.32 MB)

Errata_rybicki_joel_DD_publication_P1.pdf (196.93 KB)
Journal Title
Journal ISSN
Volume Title
School of Science | Doctoral thesis (article-based) | Defence date: 2016-11-19
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Author
Date
2016
Department
Tietotekniikan laitos
Department of Computer Science
Major/Subject
Mcode
Degree programme
Language
en
Pages
107 + app. 70
Series
Aalto University publication series DOCTORAL DISSERTATIONS, 208/2016
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.

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.
Description
Supervising professor
Suomela, Jukka, Prof., Aalto University, Department of Computer Science, Finland
Thesis advisor
Suomela, Jukka, Prof., Aalto University, Department of Computer Science, Finland
Keywords
distributed algorithms, fault tolerance, synchronisation, hajautetut algoritmit, vikasietoisuus, synkronointi
Other note
Parts
  • [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 View at publisher
  • [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.
  • [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 View at publisher
Citation
Permanent link to this item
https://urn.fi/URN:ISBN:978-952-60-7065-0
Collections
[diss] Perustieteiden korkeakoulu / SCI