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

Joel Rybicki

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

Julkaisun otsikon käännös: Laskureita, kellotusta ja väritystä: Vikasietoinen hajautettu koordinointi

Joel Rybicki

Tietotekniikan laitos

Tutkimustuotos: Doctoral Thesis › Collection of Articles

Abstrakti

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.

Julkaisun otsikon käännös	Laskureita, kellotusta ja väritystä: Vikasietoinen hajautettu koordinointi
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-7066-7
Sähköinen ISBN	978-952-60-7065-0
Tila	Julkaistu - 2016
OKM-julkaisutyyppi	G5 Artikkeliväitöskirja

Tutkimusalat

hajautetut algoritmit
vikasietoisuus
synkronointi

Pääsy asiakirjaan

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

Siteeraa tätä

@phdthesis{97dd2bb1a4724582a8767f3fdf00255e,

title = "Counting, clocking, and colouring - Fault-tolerant distributed coordination",

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.",

keywords = "distributed algorithms, fault tolerance, synchronisation, hajautetut algoritmit, vikasietoisuus, synkronointi, distributed algorithms, fault tolerance, synchronisation",

author = "Joel Rybicki",

year = "2016",

language = "English",

isbn = "978-952-60-7066-7",

series = "Aalto University publication series DOCTORAL DISSERTATIONS",

publisher = "Aalto University",

number = "208",

address = "Finland",

school = "Aalto University",

}

TY - BOOK

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

AU - Rybicki, Joel

PY - 2016

Y1 - 2016

N2 - 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.

AB - 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.

KW - distributed algorithms

KW - fault tolerance

KW - synchronisation

KW - hajautetut algoritmit

KW - vikasietoisuus

KW - synkronointi

KW - distributed algorithms

KW - fault tolerance

KW - synchronisation

M3 - Doctoral Thesis

SN - 978-952-60-7066-7

T3 - Aalto University publication series DOCTORAL DISSERTATIONS

PB - Aalto University

ER -

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

Abstrakti

Tutkimusalat

Pääsy asiakirjaan

Sormenjälki

Siteeraa tätä