Zusammenfassung

  • Fischer, Lynch und Paterson zeigen: Für jedes deterministische, partiell korrekte Konsensprotokoll existiert in ihrem asynchronen Modell mit höchstens einem ausgefallenen Prozess ein zulässiger Lauf, der nie entscheidet.
  • Eine bivalente Konfiguration lässt beide Entscheidungswerte offen. Weil unabhängige Ereignisse vertauschbar sind, kann ein kritisches Ereignis aufgeschoben werden, während Prozesse und Nachrichten trotzdem fair bedient werden.
  • Partielle Synchronität, Fehlerdetektoren und Zufall verändern die Voraussetzungen. Ein Timeout kann eine Aktion auslösen, beweist aber keinen Ausfall.

Ein Rechner schweigt, und der Rest des Clusters muss handeln. Ist er abgestürzt oder nur langsam? Ohne obere Zeitgrenze erzeugen beide Zustände dieselbe Beobachtung. Genau diese fehlende Unterscheidbarkeit macht aus einem betrieblichen Warten eine theoretische Grenze.

Michael J. Fischer, Nancy A. Lynch und Michael S. Paterson formulierten sie 1985 in Impossibility of Distributed Consensus with One Faulty Process. Der oft zitierte Satz „Konsens ist unmöglich“ ist zu grob. Bewiesen wird die Existenz mindestens eines zulässigen, nicht entscheidenden Ablaufs in einem genau bezeichneten Modell—nicht das Scheitern jedes Ablaufs.

Zuverlässige Nachrichten ohne Frist

Die Prozesse arbeiten deterministisch und kommunizieren über Nachrichten. Es gibt keine Schranke für ihre relative Geschwindigkeit, keine maximale Übertragungszeit und keine synchronisierten Uhren. Eine Nachricht darf beliebig spät oder in anderer Reihenfolge eintreffen. Sie wird jedoch nicht einfach verworfen: An einen nicht ausgefallenen Prozess gerichtete Nachrichten müssen schließlich zugestellt werden, wenn er weiter Empfangsschritte ausführt.

Ein zulässiger Lauf enthält höchstens einen fehlerhaften Prozess und erfüllt diese Zustellungsbedingung. Ein nicht fehlerhafter Prozess führt unendlich viele Schritte aus. Die Beweiskonstruktion lebt daher nicht von einem dauerhaft verschluckten Paket. Sie kann alle Prozesse und wartenden Nachrichten fair berücksichtigen und dennoch die Entscheidung hinauszögern.

Schon die schwache Terminierungsforderung—irgendein Prozess entscheidet in jedem zulässigen Lauf—lässt sich nicht garantieren. Damit fallen erst recht stärkere Fortschrittsversprechen.

Bivalenz hält zwei Zukunftswege offen

Eine Konfiguration besteht aus den lokalen Prozesszuständen und dem Nachrichtenpuffer. Ist in jeder entscheidenden Fortsetzung nur 0 möglich, ist sie 0-valent; entsprechend 1-valent für 1. Bivalent heißt, dass beide Werte weiterhin erreichbar sind.

Zunächst muss es eine bivalente Anfangskonfiguration geben. Wären alle Anfangszustände univalent, ließe sich beim schrittweisen Ändern einzelner Eingaben ein benachbartes Paar mit entgegengesetzter Valenz finden. Fiele genau der Prozess aus, dessen Eingabe die Zustände unterscheidet, könnten die anderen Prozesse die beiden Welten nicht auseinanderhalten—sollten aber verschieden entscheiden.

Dann betrachtet der Beweis ein anwendbares Ereignis, etwa die Zustellung einer bestimmten Nachricht. Würde dieses Ereignis nach jedem möglichen Aufschub zwingend eine eindeutige Valenz erzeugen, müsste es einen kritischen Übergang geben. Schritte verschiedener Prozesse kommutieren jedoch: erst A und dann B führt in denselben Zustand wie erst B und dann A. Das entstehende Quadrat zwingt vermeintlich gegensätzliche Valenzen in dieselbe Konfiguration und erzeugt einen Widerspruch.

Folglich findet der Scheduler stets einen endlichen Umweg, nach dem das ausgewählte Ereignis ausgeführt wird und der Zustand bivalent bleibt. Wiederholt er dies fair über Prozesse und Nachrichten, entsteht ein unendlicher zulässiger Lauf ohne Entscheidung.

Kein Etikett für jeden Stillstand

Dass ein solcher Lauf existiert, heißt nicht, dass er typisch ist. Ein reales System kann fast immer entscheiden, weil die Umgebung günstiger ist oder weil seine Architektur stärkere Annahmen macht. FLP entzieht lediglich das bedingungslose Versprechen.

Ein stockender Leader-Wahlgang belegt deshalb noch kein FLP-Phänomen. Paketverlust, Speicherstau, fehlerhafte Mitgliedschaft, korrelierte Ausfälle und Softwarebugs sind eigenständige Ursachen. Wer FLP nennt, müsste zeigen, welches Modell galt, wie Sicherheit die nächsten Schritte einschränkte und weshalb Verzögerung und Ausfall ununterscheidbar blieben.

Fortschritt hat einen Annahmepreis

Dwork, Lynch und Stockmeyer beschrieben partielle Synchronität: Grenzen können existieren, ohne bekannt zu sein, oder erst nach einem unbekannten Stabilisierungszeitpunkt gelten. Ein Protokoll darf Fortschritt erwarten, sobald diese stärkere Phase eingetreten ist.

Die Fehlerdetektoren von Chandra und Toueg fügen Informationen mit definierten Vollständigkeits- und Genauigkeitseigenschaften hinzu. Sie zaubern aus Schweigen keine Gewissheit. Randomisierte Protokolle wie Ben-Ors ändern dagegen die deterministische Voraussetzung und versprechen Terminierung probabilistisch.

Keiner dieser Wege widerlegt FLP. Jeder benennt die zusätzliche Ressource, die den Fortschritt trägt.

Gemeinschaftliche Urheberschaft, bleibende Methode

Nancy Lynch schildert rückblickend, wie sie und Fischer 1982 mit der Arbeit begannen und Paterson später zum Beweis beitrug. Die drei Namen gehören zusammen. Lynchs breiteres Werk machte darüber hinaus die präzise Modellierung von Annahmen zu einer Grundtechnik der verteilten Informatik.

Ein belastbares System veröffentlicht deshalb seine Ausfallgrenze, Zeitannahmen, Detektoreigenschaften und den Punkt, an dem Sicherheit Vorrang vor Verfügbarkeit erhält. FLP verbietet Konsens nicht. Es verbietet, versteckte Bedingungen als universelle Garantie auszugeben.

Quellen