Konsensusalgoritmeja

Konsensusalgoritmeja ovat protokollat, joiden avulla hajautetussa järjestelmässä toimivat prosessit voivat saavuttaa yhteisymmärryksen yhdestä dataarvosta tai tapahtumien järjestyksestä. Tämän avulla samaan tilaan saapuvia viestejä voidaan käsitellä johdonmukaisesti, vaikka verkko on viivästynyt tai osalla solmista esiintyy vikoja. Tavoitteena on sekä turvallisuus että saatavuus: oikeat solmut päätyvät samaan lopulliseen arvoon ja päätökset syntyvät järjestelmällisesti.

Konsensusalgoritmit voivat käsitellä eri virhetilanteita. Byzantilaiset viat tarkoittavat vilpillisiä tai viallisia solmuja, kun taas kaatumisviat tarkoittavat tilapäistä toimintahäiriötä. BFT-tyyppisten algoritmien teoreettinen toleranssi on usein niin, että järjestelmä kestää enintään f virhettä ja tarvitaan n ≥ 3f+1 solmua.

Käytännössä erilaiset algoritmit painottavat erilaisia ominaisuuksia. Crash fault tolerant -algoritmit kuten Paxos ja Raft korostavat yksinkertaisuutta ja suorituskykyä epävarmoissa verkko-olosuhteissa. Byzantine fault tolerant -algoritmit kuten PBFT, Tendermint ja HotStuff kestävät vilpillisiä solmuja ja epäluotettavia viestejä. Lisäksi kryptopohjaisissa ympäristöissä käytetään lohkoketjuissa ja vastaavissa palkkioihin tai esteisiin nojaavia mekanismeja kuten Proof of Work ja Proof of Stake.

Käyttökohteita ovat hajautetut tietokannat, monidatakeskuksellinen replikointi sekä lohkoketjut, joissa luotettavuus ja lopullinen vahvistus ovat keskeisiä. Historia kattaa Paxosin (1990-luvun loput) sekä Raftin (2010-luvun alku) ja BFT-tyyppiset ratkaisut kuten PBFT, Tendermint ja HotStuff.