Paxos ( engelsk Paxos ) er en familie af protokoller til løsning af problemet med konsensus i et netværk af upålidelige computere. Konsensus er processen med at opnå et aftalt resultat af en gruppe deltagere, hovedproblemet er tilstedeværelsen af interferens i datatransmissionsmediet [1] . Denne opgave bruges for eksempel til at godkende transaktioner i distribuerede systemer.
Protokollerne til løsning af konsensusproblemet er det grundlæggende element i automattilgangen i distribueret databehandling foreslået af Leslie Lamport [2] og yderligere udforsket af F. Schneider [3] .
Automatisk tilgang er en metode til at implementere en algoritme på et distribueret system, der opretholder fejltolerance. Dette er en systematisk tilgang, der ikke tillader ubevidst introduktion af fejl. Lamports principielle tilgang tager alle mulige sager i betragtning.
Paxos-familien af protokoller blev oprettet og beskrevet i 1990, men blev først offentliggjort i den videnskabelige litteratur i 1998. Forskningen i dette emne begyndte dog længe før implementeringen af protokollen. For eksempel automatisk replikering , en programmeringstilgang baseret på den virtuelle synkroniseringsmodel foreslået i 1985.
Paxos-familien af protokoller overvejer muligheder for at løse konsensusproblemet afhængigt af antallet af evaluatorer, antallet af forsinkelser for at opnå et resultat, deltagernes aktivitet, antallet af sendte beskeder og typerne af fejl. Resultatet af en fejlsikker konsensus er udefineret (dvs. under visse betingelser vil evaluatorerne ikke være i stand til at blive enige), men sikkerhed (konsistens) er garanteret, og forhold, hvor konsensus er umulig, er meget sjældne.
Algoritmen er opkaldt efter det fiktive retssystem på den græske ø Paxos .
Algoritmer i denne familie garanterer følgende 3 indikatorer:
For at forenkle præsentationen af Paxos-algoritmen beskriver vi følgende definitioner og forudsætninger.
Typisk kan konsensusalgoritmen gøre fremskridt ved at bruge 2F+1-processorer på trods af, at eventuelle F-processorer fejler på samme tid. Men ved at bruge omkonfiguration er det muligt at bruge en protokol, der overlever et vilkårligt antal komplette fejl, så længe ikke mere end F-processorer fejler på samme tid.
Paxos beskriver processorernes aktiviteter ud fra deres roller i protokollen: klient, modtager (acceptor), ansøger (tilbud), elev og leder. I typiske implementeringer kan en processor spille en eller flere roller på samme tid. Dette påvirker ikke korrektheden af protokollen - roller kombineres normalt for at reducere latens og/eller antallet af meddelelser i protokollen.
Klient Klienten sender en anmodning til det distribuerede system og venter på svar. For eksempel en anmodning om at skrive til en fil på en distribueret filserver. Acceptor (vælger) Acceptorer fungerer som en fejlsikker "hukommelse" af protokollen. De mødes i grupper kaldet kvorummer. Enhver besked sendt til en acceptor skal sendes til et beslutningsdygtigt antal acceptanter. Enhver besked modtaget fra en acceptor ignoreres, indtil der er modtaget en kopi fra hver acceptor i kvorummet. Ansøger (forslagsstiller) Sagsøgeren forsvarer klientens anmodning ved at forsøge at overbevise acceptanter til at acceptere denne anmodning og fungerer som en facilitator for at flytte protokollen fremad i tilfælde af konflikter. Studerende Eleverne fungerer som en protokolreplikationsfaktor. Når klientanmodningen er blevet forhandlet af acceptanterne, kan eleven handle (dvs. fuldføre anmodningen og sende et svar til klienten). Yderligere studerende kan tilføjes for at forbedre behandlingstilgængeligheden. Leder Paxos kræver en fremragende ansøger (kaldet leder) for at gøre fremskridt. Mange processer tror måske, at de er lederne, men protokollen garanterer kun fremskridt, hvis en af dem til sidst bliver valgt. Hvis to processer tror, de er lederne, kan de stoppe protokollen ved konstant at tilbyde modstridende opdateringer. I dette tilfælde er sikkerhedsegenskaberne dog bevaret.Et beslutningsdygtigt flertal er et flertal af alle klyngemedlemmer.
Q = N/2 + 1
For eksempel, hvis der er 6 medlemmer i klyngen, ville kvorumet være 4.
Kvorum udtrykker algoritmens sikkerhedsegenskaber, hvilket sikrer, at information om resultaterne bevares i mindst nogle af de overlevende processorer.
Kvorumer defineres som undermængder af et acceptorsæt, således at alle to undermængder (det vil sige vilkårlige to kvorummer) har mindst ét element til fælles. Et quorum er typisk ethvert flertal af de deltagende acceptanter. Overvej f.eks. sættet af acceptorer {A, B, C, D}, hvor flertallets beslutningsdygtighed vil være alle tre acceptorer: {A, B, C}, {A, C, D}, {A, B, D} eller {B,C,D}. Mere generelt kan acceptorer og quorum tildeles vilkårlige positive vægte, defineret som enhver delmængde af acceptorer med en kombineret vægt større end halvdelen af den samlede vægt af alle acceptorer.
Hvert forsøg på at bestemme en forhandlet værdi af v er lavet ved hjælp af propositioner, som kan eller måske ikke accepteres af acceptorerne. Hvert tilbud er unikt nummereret for en given ansøger. Værdien svarende til den nummererede sætning kan beregnes som en del af udførelsen af Paxos-protokollen, men er ikke påkrævet.
En stoptabel tilstandsmaskine er en, der kan stoppe arbejdet på en bestemt kommando. Sådanne automater bruges for eksempel til at implementere en konfigurationsændring i en replikeret automat: en rekonfigurerbar automat implementeres som en sekvens af stopbare automater, der hver opererer i sin egen konfiguration. En standsbar paxos implementerer en replikerbar standsningsmaskine.