Paxos ( englanniksi Paxos ) on protokollaperhe konsensusongelman ratkaisemiseksi epäluotettavien tietokoneiden verkossa. Konsensus on prosessi, jossa osallistujaryhmä saa sovitun tuloksen. Suurin ongelma on häiriön esiintyminen tiedonsiirtovälineessä [1] . Tätä tehtävää käytetään esimerkiksi tapahtumien hyväksymiseen hajautetuissa järjestelmissä.
Protokollat konsensusongelman ratkaisemiseksi ovat Leslie Lamportin [ 2] ehdottaman ja F. Schneiderin [3] edelleen tutkiman automaattisen lähestymistavan peruselementti .
Automaattinen lähestymistapa on menetelmä algoritmin toteuttamiseksi hajautetussa järjestelmässä, joka ylläpitää vikasietoisuutta. Tämä on systemaattinen lähestymistapa, joka ei salli virheiden tiedostamista. Lamportin periaatteellinen lähestymistapa ottaa huomioon kaikki mahdolliset tapaukset.
Paxos-protokollaperhe luotiin ja kuvattiin vuonna 1990, mutta se julkaistiin tieteellisessä kirjallisuudessa vasta vuonna 1998. Tutkimus aiheesta aloitettiin kuitenkin kauan ennen protokollan käyttöönottoa. Esimerkiksi automaattinen replikointi , ohjelmointitapa, joka perustuu vuonna 1985 ehdotettuun virtuaaliseen synkronointimalliin .
Paxos-protokollaperhe harkitsee konsensusongelman ratkaisuvaihtoehtoja arvioijien lukumäärän, tuloksen saamisen viiveiden, osallistujien aktiivisuuden, lähetettyjen viestien määrän ja epäonnistumisten mukaan. Vikaturvallisen konsensuksen tulos on määrittelemätön (eli tietyin edellytyksin arvioijat eivät pääse yksimielisyyteen), mutta turvallisuus (johdonmukaisuus) on taattu, ja olosuhteet, joissa konsensus on mahdotonta, ovat erittäin harvinaisia.
Algoritmi on nimetty kreikkalaisen Paxoksen saaren kuvitteellisen oikeusjärjestelmän mukaan .
Tämän perheen algoritmit takaavat seuraavat 3 indikaattoria:
Paxos-algoritmin esittämisen yksinkertaistamiseksi kuvataan seuraavat määritelmät ja ehdot.
Tyypillisesti konsensusalgoritmi voi edistyä käyttämällä 2F+1-prosessoreita, vaikka kaikki F-prosessorit epäonnistuvat samanaikaisesti. Uudelleenmäärityksen avulla on kuitenkin mahdollista käyttää protokollaa, joka kestää minkä tahansa määrän täydellisiä vikoja, kunhan enintään F prosessoria epäonnistuu samanaikaisesti.
Paxos kuvaa prosessorien toimintaa niiden rooleilla protokollassa: asiakas, vastaanottaja (hyväksyjä), hakija (tarjous), oppija ja johtaja. Tyypillisissä toteutuksissa yhdellä prosessorilla voi olla yhtä tai useampaa roolia samanaikaisesti. Tämä ei vaikuta protokollan oikeellisuuteen - rooleja yhdistetään yleensä latenssin ja/tai protokollan viestien määrän vähentämiseksi.
Asiakas Asiakas lähettää pyynnön hajautetulle järjestelmälle ja odottaa vastausta. Esimerkiksi pyyntö kirjoittaa tiedostoon hajautetulla tiedostopalvelimella. Hyväksyjä (äänestäjä) Hyväksyjät toimivat protokollan vikaturvallisena "muistina". He kokoontuvat ryhmissä, joita kutsutaan koorumeiksi. Kaikki hyväksyjälle lähetetyt viestit on lähetettävä hyväksyjien koorumiin. Kaikki hyväksyjältä saadut viestit jätetään huomiotta, kunnes jokaiselta päätösvaltaisessa hyväksyjältä on vastaanotettu kopio. Hakija (ehdotus) Kantaja puolustaa asiakkaan pyyntöä yrittämällä saada hyväksyjät hyväksymään pyynnön ja toimii avustajana protokollan eteenpäin viemisessä ristiriitojen sattuessa. Opiskelija Oppijat toimivat protokollan replikointitekijänä. Kun hyväksyjät ovat neuvotelleet asiakkaan pyynnöstä, oppija voi ryhtyä toimiin (eli täydentää pyyntöä ja lähettää vastauksen asiakkaalle). Lisää opiskelijoita voidaan lisätä käsittelyn käytettävyyden parantamiseksi. Johtaja Paxos vaatii erinomaisen hakijan (kutsutaan johtajaksi) edistyäkseen. Monet prosessit saattavat uskoa olevansa johtajia, mutta pöytäkirja takaa edistymisen vain, jos joku heistä lopulta valitaan. Jos kaksi prosessia luulee olevansa johtajia, ne voivat pysäyttää protokollan tarjoamalla jatkuvasti ristiriitaisia päivityksiä. Tässä tapauksessa turvaominaisuudet kuitenkin säilyvät.Päätösvaltaisuus on enemmistö klusterin jäsenistä.
Q = N/2 + 1
Esimerkiksi jos klusterissa on 6 jäsentä, päätösvaltaisuus on 4.
Koorumit ilmaisevat algoritmin turvallisuusominaisuudet varmistaen, että tiedot tuloksista säilyvät ainakin joissakin säilyneissä prosessoreissa.
Koorumit määritellään hyväksyjäjoukon osajoukoiksi siten, että millä tahansa kahdella osajoukolla (eli kahdella koorumilla) on vähintään yksi yhteinen elementti. Tyypillisesti päätösvaltainen on mikä tahansa osallistuvien hyväksyjien enemmistö. Tarkastellaan esimerkiksi hyväksyjien joukkoa {A, B, C, D}, jonka enemmistön päätösvaltaisuus on mitkä tahansa kolme hyväksyjää: {A, B, C}, {A, C, D}, {A, B, D} tai {B ,C,D}. Yleisemmin hyväksyjille ja koorumille voidaan antaa mielivaltaiset positiiviset painot, jotka määritellään minkä tahansa hyväksyjien alajoukoksi, joiden yhdistetty paino on suurempi kuin puolet kaikkien vastaanottajien kokonaispainosta.
Jokainen yritys määrittää v:n neuvoteltu arvo tehdään ehdotusten avulla, jotka hyväksyjät voivat hyväksyä tai olla hyväksymättä. Jokainen tarjous on yksilöllisesti numeroitu tietylle hakijalle. Numeroitua lausetta vastaava arvo voidaan laskea osana Paxos-protokollan suorittamista, mutta sitä ei vaadita.
Pysäytystilakone on kone, joka voi pysäyttää tietyn komennon käytön. Tällaisia automaatteja käytetään esimerkiksi konfiguraatiomuutoksen toteuttamiseen replikoituneessa automaatissa: uudelleenkonfiguroitava automaatti toteutetaan sarjana pysäytettyjä automaatteja, joista jokainen toimii omassa konfiguraatiossaan. Pysäyttävä paxos toteuttaa replikoitavan pysäytettävän tilakoneen.