Konsensusalgoritmer

Konsensusalgoritmer är metoder inom distribuerade system som gör att flera oberoende noder kan enas om ett gemensamt tillstånd eller en händelseordning, trots att vissa noder kan falla eller att nätverket fördröjs. De används främst i system som använder replikering av statsmaskiner för att garantera konsekvent beteende över flera noder.

De viktigaste krav som ofta definieras för konsensus är säkerhet (alla som deltar i beslutsprocessen kommer överens om samma logiska ordning när systemet är fungerande), levedyktighet/förlopp (systemet gör framsteg och avslutar beslut även vid fel eller fördröjningar) och validitet (beslutet baseras på aktörernas tidigare tillstånd). I asynkrona nätverk är fullständig garanti svårt på grund av FLP-impossibiliteten; praktiska algoritmer antar partiell synkronitet eller eventual konsensus och använder mekanismer som ledareval eller vyändringar.

Kända kategorier och exempel: crash fault tolerant (CFT) algoritmer som Paxos och Raft som fokuserar på fel på noder utan villfarelser i kommunikation; Byzantine fault tolerant (BFT) algoritmer som PBFT och Tendermint som klarar felaktiga eller illvilliga noder. I blockkedjeteknik används Nakamoto-konsensus (proof-of-work) och varianter som proof-of-stake i andra system, där deltagarna konkurrerar i att skapa nya tillståndsblock.

Användningsområden: konsekvent replikering i databaser, distribuerade filsystem och tjänster som kräver konsekvent ordning. Prestanda mäts i genomströmning och latens samt antal noder som kan tolereras. Ledareval och vyändringar är vanliga mekanismer för att uppnå framsteg.

Utmaningar inkluderar skalbarhet, partiell synkronitet, nätverkspartitioner, energiförbrukning i vissa modeller, samt ekonomiska och säkerhetsaspekter i öppna nätverk. Val av algoritm beror på antaganden om fel, kommunikation och prestandakrav.