Konsensusprotokoller

Konsensusprotokoller er metoder som lar et distribuert system bli enige om en felles beslutning om tilstand eller rekkefølge av operasjoner, selv om noen noder feiler eller ikke kan kommunisere. De verner om nøyaktighet og konsistens ved at alle ikke-feilende noder når samme beslutning, og de forsøker samtidig å opprettholde fremdrift i systemet.

Kategorisering og nøkkelfakta. Protokollene deles ofte inn i crash fault-tolerante (CFT) og Byzantine fault-tolerante (BFT) varianter. CFT-protokoller tolererer at enkelte noder feiler ved å krasje, men krever vanligvis minst 2f+1 noder for å tåle f feil. BFT-protokoller må tåle bysantiske feil (alvorlig feiladferd eller ondsinnede noder) og krever minst 3f+1 noder for å sikre sikkerhet og fremdrift. Begge typer søker å sikre sikkerhet (ingen uenighet om historikk mellom ikke-feilende noder) og fremdrift (systemet avslutter beslutninger innen rimelig tid).

Gjenkjennelige eksempler og arbeidsmåte. Paxos og Raft er kjente CFT-familier som ofte brukes i databasesystemer og koordineringstjenester; de legger vanligvis en leder til å styre beslutningsflyten og bruker logg- eller commit-mekanismer for å oppnå enighet. PBFT, Tendermint og HotStuff representerer BFT-familien og håndterer bysantisk feiltoleranse gjennom flerdelte stemmeprosesser og faser av korreksjon og bekreftelse, noe som gjør dem mer motstandsdyktige mot ondsinnede deltakere.

Anvendelser og utfordringer. Konsensusprotokoller brukes i distribuerte databaser, koordinasjonstjenester og blockchain-nettverk. Utfordringer inkluderer nettverksforsinkelse, partisjonering, sikkerhet mot ondsinnede noder og balanse mellom sikkerhet og ytelse. Teoretiske begrensninger, som FLP-teoremet i fullt asynkrone nettverk, viser at full garanti for både sikkerhet og framdrift er avhengig av visse antakelser om timing og feiltoleranse.