Verteilter Konsens

Verteilter Konsens ist das Problem, eine Reihe von Prozessen dazu zu bringen, sich auf einen einzigen Wert zu einigen, trotz Nachrichtenverzögerungen und Prozessausfällen, und er ist die zentrale Abstraktion des fehlertoleranten Rechnens.

Definition

Konsens erfordert, dass jeder fehlerfreie Prozess, ausgehend von einer vorgeschlagenen Eingabe, schließlich einen Ausgabewert festlegt, sodass alle fehlerfreien Prozesse denselben Wert festlegen (Einigung), der Wert von einem Prozess vorgeschlagen wurde (Gültigkeit) und jeder fehlerfreie Prozess schließlich eine Entscheidung trifft (Terminierung).

Scope

Dieses Thema behandelt die formale Spezifikation des Konsenses (Einigung, Gültigkeit, Integrität und Terminierung), das FLP-Unmöglichkeitstheorem und die Wege, wie es umgangen wird – partielle Synchronität, unzuverlässige Fehlerdetektoren und Randomisierung – sowie die Äquivalenz von Konsens mit atomarem Broadcast und replizierten Zustandsmaschinen. Es behandelt die Einstellung von Absturzfehlern; die byzantinische Einstellung wird in einem verwandten Thema behandelt.

Core questions

• Was genau muss ein Protokoll garantieren, um ein korrekter Konsensalgorithmus zu sein?
• Warum ist deterministischer asynchroner Konsens selbst bei einem einzigen Absturz unmöglich?
• Welche zusätzlichen Annahmen – Synchronität, Fehlerdetektoren, Zufälligkeit – stellen die Lösbarkeit wieder her?

Key theories

FLP-Unmöglichkeit

Kein deterministisches Protokoll löst Konsens in einem asynchronen Nachrichtenübertragungssystem, wenn auch nur ein Prozess abstürzen kann, da jedes Protokoll eine Ausführung hat, die so gesteuert werden kann, dass sie unendlich läuft, ohne eine Entscheidung zu treffen.

Fehlerdetektor-Ansatz

Die Erweiterung eines asynchronen Systems um einen unzuverlässigen Fehlerdetektor, der schließlich genau ist, stellt die Lösbarkeit des Konsenses wieder her, und der schwächste ausreichende Detektor wurde präzise charakterisiert.

Randomisierter Konsens

Das Erlauben von Münzwürfen durch Prozesse ermöglicht es dem Konsens, mit Wahrscheinlichkeit eins zu terminieren, selbst in einem vollständig asynchronen System, indem deterministische Terminierung gegen probabilistische Terminierung getauscht wird, um die FLP-Barriere zu umgehen.

Clinical relevance

Jedes stark konsistente verteilte System – replizierte Logs, Koordinationsdienste, Konfigurationsspeicher – löst intern Konsens, sodass die hier etablierten Garantien und Grenzen direkt festlegen, was solche Systeme bezüglich Konsistenz und Verfügbarkeit versprechen können.

History

Das FLP-Theorem von 1985 etablierte die fundamentale Unmöglichkeit; Ben-Ors randomisiertes Protokoll von 1983 und Chandra und Touegs Fehlerdetektor-Framework von 1996 zeigten dann zwei komplementäre Wege auf, Konsens lösbar zu machen, und definierten damit die Forschungsagenda für die folgenden Jahrzehnte.

Key figures

• Michael Fischer
• Nancy Lynch
• Michael Paterson
• Tushar Chandra
• Sam Toueg
• Michael Ben-Or

Seminal works

• fischer1985
• chandra1996
• ben-or1983

Frequently asked questions

Wenn Konsens unmöglich ist, wie erreichen ihn dann reale Systeme?

Die Unmöglichkeit gilt nur für ein deterministisches Protokoll, das in einem vollständig asynchronen Modell immer terminieren muss. Reale Systeme halten die Sicherheit bedingungslos aufrecht und verlassen sich für die Terminierung auf eventuelle Synchronität oder Zufälligkeit, sodass sie niemals die Einigung verletzen und Fortschritte machen, wann immer das Netzwerk sich gut verhält.