Konsens und Koordination

Konsens und Koordination befassen sich damit, wie unabhängige Prozesse, die nur über Nachrichten kommunizieren, sich trotz Verzögerungen und Ausfällen auf einen gemeinsamen Wert oder eine gemeinsame Aktion einigen können.

Definition

Konsens ist das Problem, bei dem eine Menge von Prozessen, von denen jeder einen Wert vorschlägt, sich alle auf einen einzigen gemeinsamen Wert einigen, sodass die Entscheidung gültig ist, alle korrekten Prozesse übereinstimmen und jeder korrekte Prozess schließlich eine Entscheidung trifft, selbst wenn einige Prozesse ausfallen.

Scope

Dieser Bereich umfasst das Konsensproblem und seine Varianten (Einigung, atomarer Broadcast, Gültigkeit, Terminierung), das grundlegende FLP-Unmöglichkeitsergebnis für deterministischen asynchronen Konsens, praktische Konsensprotokolle wie Paxos und Raft, byzantinisch fehlertolerante Einigung sowie die klassischen Koordinationsprobleme der gegenseitigen Ausschließung und der Leader-Wahl. Es bildet den theoretischen und praktischen Kern des fehlertoleranten verteilten Rechnens.

Sub-topics

• Byzantinische Fehlertoleranz
• Verteilter Konsens
• Verteilter wechselseitiger Ausschluss und Leader-Wahl
• Paxos und Raft

Core questions

• Unter welchen Zeit- und Fehlermodellen ist Konsens lösbar, und wann ist er nachweislich unmöglich?
• Wie umgehen praktische Protokolle die FLP-Unmöglichkeit, während sie die Sicherheit bewahren?
• Wie viel Replikation ist erforderlich, um Absturz- im Vergleich zu byzantinischen Fehlern zu tolerieren?
• Wie können Prozesse den Zugriff auf gemeinsame Ressourcen koordinieren oder einen Leader zuverlässig wählen?

Key theories

FLP-Unmöglichkeit

In einem vollständig asynchronen System kann kein deterministisches Protokoll Konsens garantieren, wenn auch nur ein einziger Prozess abstürzen kann, da ein langsamer Prozess nicht von einem ausgefallenen unterschieden werden kann; dieses Ergebnis motiviert partielle Synchronität, Randomisierung und Fehlerdetektoren.

Quorum-basierter Konsens

Protokolle wie Paxos erzielen Einigung, indem sie überlappende Mehrheiten (Quoren) fordern, um Vorschläge zu akzeptieren, wodurch sichergestellt wird, dass sich zwei beliebige Entscheidungen an einem korrekten Prozess überschneiden und somit über Runden und Leader-Wechsel hinweg konsistent bleiben.

Grenzen der byzantinischen Einigung

Um eine Einigung zu erzielen, wenn bis zu f Prozesse sich beliebig verhalten können, sind im klassischen synchronen Setting mindestens 3f+1 Prozesse erforderlich, eine enge Grenze, die das Design aller byzantinisch fehlertoleranten Systeme prägt.

Clinical relevance

Konsens ist das Rückgrat zuverlässiger Infrastrukturen: Koordinationsdienste, replizierte Datenbanken, verteilte Sperren und Blockchains verwenden alle ein Konsensprotokoll, um Replikate konsistent zu halten. Dies macht diesen Bereich direkt verantwortlich für die Dauerhaftigkeits- und Verfügbarkeitsgarantien moderner Cloud-Systeme.

History

Das Papier über die byzantinischen Generäle von 1982 und das FLP-Unmöglichkeitsergebnis von 1985 umrissen die Grenzen der Einigung; Lamports Paxos (1989 zirkuliert, 1998 veröffentlicht) lieferte ein praktisches asynchron-sicheres Protokoll, und spätere Arbeiten zur byzantinischen Fehlertoleranz und Raft machten Konsens sowohl robust gegenüber bösartigen Fehlern als auch für Implementierer zugänglich.

Debates

Macht die FLP-Unmöglichkeit Konsens in der Praxis unerreichbar?

FLP schließt ein deterministisches Protokoll aus, das in einem vollständig asynchronen Modell immer sowohl sicher als auch lebendig ist, aber praktische Systeme umgehen dies, indem sie eventuelle Synchronität annehmen oder Randomisierung verwenden, wodurch die Sicherheit bedingungslos bleibt und die Lebendigkeit erreicht wird, wann immer sich das Netzwerk verhält.

Key figures

• Leslie Lamport
• Nancy Lynch
• Michael Fischer
• Michael Paterson
• Barbara Liskov

Seminal works

• fischer1985
• lamport1998
• lamport1982byz

Frequently asked questions

Warum gilt Konsens als das schwierigste Problem in verteilten Systemen?

Weil viele andere Koordinationsaufgaben – atomarer Broadcast, replizierte Zustandsmaschinen, verteilte Sperren – auf Konsens reduziert werden können, und Konsens selbst im asynchronen Absturz-Fehlermodell nachweislich nicht deterministisch lösbar ist, sodass jede Lösung sorgfältige Annahmen bezüglich des Timings oder der Zufälligkeit treffen muss.

Wie hängt Konsens mit replizierten Datenbanken zusammen?

Eine replizierte Datenbank hält ihre Replikate konsistent, indem sie sich auf die Reihenfolge der Operationen einigt, was genau eine Abfolge von Konsensentscheidungen ist; deshalb betten Systeme wie verteilte Schlüssel-Wert-Speicher ein Konsensprotokoll in ihren Kern ein.