🥇 Schrödinger Katze ohne Box: Das Konsensproblem in verteilten Systemen

Stellen Sie sich vor, in einem Raum sind fünf Katzen eingesperrt. Um ihren Besitzer zu wecken, müssen sie sich gemeinsam darauf einigen, denn die Tür können sie nur zu fünft aufdrücken. Wenn eine der Katzen Schrödingers Katze ist und die anderen nichts von ihrer Entscheidung wissen, stellt sich die Frage: „Wie können sie das anstellen?“

In diesem Artikel erkläre ich Ihnen in einfachen Worten die theoretischen Grundlagen der verteilten Systeme und die Prinzipien ihrer Funktionsweise. Außerdem werde ich die zentrale Idee, die Paxos zugrunde liegt, kurz anreißen.

Wenn Entwickler Cloud-Infrastrukturen nutzen, mit verschiedenen Datenbanken arbeiten oder in Clustern aus vielen Knoten agieren, sind sie überzeugt, dass die Daten intakt, sicher und immer verfügbar sind. Aber woher kommen diese Garantien?

Im Wesentlichen sind die Garantien, die wir haben, die Garantien des Anbieters. Diese sind in der Dokumentation etwa so beschrieben: „Dieser Dienst ist ausreichend zuverlässig, er hat einen festgelegten SLA, machen Sie sich keine Sorgen, alles wird verteilt funktionieren, wie Sie es erwarten.“

Wir neigen dazu, an das Beste zu glauben, denn kluge Köpfe großer Unternehmen haben uns versichert, dass alles gut wird. Wir stellen uns nicht die Frage: Warum könnte das eigentlich funktionieren? Gibt es eine formale Begründung für die Richtigkeit solcher Systeme?

Kürzlich war ich auf einer Schule für verteilte Berechnungen und war von diesem Thema sehr inspiriert. Die Vorlesungen an der Schule erinnerten eher an Mathematikunterricht als an etwas, das mit Computersystemen zu tun hat. Doch genau so wurden damals die wichtigsten Algorithmen bewiesen, die wir jeden Tag benutzen, oft ohne es zu merken.

In den meisten modernen verteilten Systemen wird der Konsensalgorithmus Paxos und seine verschiedenen Modifikationen verwendet. Das Beste daran ist, dass die Begründung und die grundsätzlich mögliche Existenz dieses Algorithmus einfach mit Stift und Papier bewiesen werden kann. In der Praxis wird der Algorithmus in großen Systemen eingesetzt, die auf einer enormen Anzahl von Knoten in der Cloud arbeiten.

Eine einfache Illustration dessen, was als Nächstes folgt: die Aufgabe der zwei GeneräleLassen Sie uns zur Aufwärmung die Aufgabe der zwei Generäle besprechen.

Wir haben zwei Armeen – die Rote und die Weiße. Die weißen Truppen sind in der belagerten Stadt stationiert. Die roten Truppen unter dem Befehl der Generäle A1 und A2 sind auf beiden Seiten der Stadt positioniert. Die Aufgabe der Roten besteht darin, die weiße Stadt anzugreifen und zu gewinnen. Allerdings ist das Heer jedes roten Generals für sich genommen kleiner als das der Weißen.

Die Bedingungen für den Sieg der Roten: Beide Generäle müssen gleichzeitig angreifen, um einen numerischen Vorteil gegenüber den Weißen zu haben. Dazu müssen sich die Generäle A1 und A2 miteinander abstimmen. Wenn jeder separat angreift, werden die Roten verlieren.

Um sich abzustimmen, können die Generäle A1 und A2 Boten durch das Gebiet der weißen Stadt schicken. Ein Bote kann erfolgreich zu dem verbündeten General gelangen oder von den Gegnern abgefangen werden. Die Frage ist: Gibt es eine solche Abfolge der Kommunikation zwischen den roten Generälen (die Reihenfolge, in der Boten von A1 zu A2 und umgekehrt von A2 zu A1 geschickt werden), bei der sie garantiert eine Vereinbarung für den Angriff zur Stunde X erreichen? Hierbei wird unter Garantie verstanden, dass beide Generäle eine eindeutige Bestätigung erhalten, dass der Verbündete (der andere General) definitiv zur festgelegten Zeit X angreift.

Angenommen, A1 schickt einen Boten zu A2 mit der Nachricht: „Lass uns heute Nacht um Mitternacht angreifen!“. General A1 kann nicht angreifen, ohne eine Bestätigung von General A2 zu erhalten. Wenn der Bote von A1 angekommen ist, sendet General A2 eine Bestätigung mit der Nachricht: „Ja, lass uns heute die Weißen überfallen“. Aber nun weiß General A2 nicht, ob sein Bote angekommen ist oder nicht, er hat keine Garantie, dass der Angriff gleichzeitig erfolgen wird. Jetzt benötigt General A2 wieder eine Bestätigung.

Wenn wir ihre Kommunikation weiter ausführen, zeigt sich Folgendes: So viele Nachrichtenaustauschzyklen es auch geben mag, es gibt keine Möglichkeit, beide Generäle garantiert darüber zu informieren, dass ihre Nachrichten empfangen wurden (vorausgesetzt, einer der Boten könnte abgefangen werden).

Das Problem der zwei Generäle ist eine hervorragende Veranschaulichung eines sehr einfachen verteilten Systems, in dem es zwei Knoten mit unzuverlässiger Kommunikation gibt. Das bedeutet, wir haben keine 100% Garantie, dass sie synchronisiert werden. Über ähnliche Probleme in größerem Maßstab werden wir später im Artikel sprechen.

Wir führen das Konzept der verteilten Systeme ein.

Ein verteiltes System ist eine Gruppe von Computern (im Folgenden Knoten genannt), die Nachrichten austauschen können. Jeder einzelne Knoten ist eine autonome Einheit. Ein Knoten kann Aufgaben selbstständig bearbeiten, aber um mit anderen Knoten zu interagieren, muss er Nachrichten senden und empfangen.

Wie genau die Nachrichten implementiert sind und welche Protokolle verwendet werden, ist in diesem Kontext nicht von Interesse. Wichtig ist, dass die Knoten des verteilten Systems Daten austauschen können, indem sie Nachrichten senden.

Die Definition scheint nicht sehr kompliziert zu sein, jedoch müssen wir berücksichtigen, dass ein verteiltes System eine Reihe von Attributen aufweist, die für uns relevant sind.

Attribute verteilter Systeme

Nebenläufigkeit – die Möglichkeit gleichzeitiger oder konkurrierender Ereignisse im System. Darüber hinaus werden wir davon ausgehen, dass Ereignisse, die auf zwei verschiedenen Knoten auftreten, potenziell konkurrierend sind, solange wir keine klare Reihenfolge dieser Ereignisse haben. Und in der Regel haben wir eine solche klare Reihenfolge nicht.
Fehlen globaler Uhren. Wir haben keine klare Abfolge von Ereignissen aufgrund des Fehlens globaler Uhren. In der gewohnten Welt der Menschen sind wir daran gewöhnt, dass wir Uhren und eine absolute Zeit haben. Alles ändert sich, wenn es um verteilte Systeme geht. Selbst bei hochpräzisen Atomicuhren gibt es Drift, und es können Situationen auftreten, in denen wir nicht sagen können, welches von zwei Ereignissen zuerst passiert ist. Daher können wir uns auch nicht auf die Zeit verlassen.
Unabhängiger Ausfall von Systemknoten. Es gibt ein weiteres Problem: Etwas kann schiefgehen, einfach weil unsere Knoten nicht ewig funktionieren. Eine Festplatte kann ausfallen, eine virtuelle Maschine in der Cloud kann neu starten, das Netzwerk kann flackern und Nachrichten gehen verloren. Darüber hinaus sind Situationen möglich, in denen Knoten funktionieren, aber gegen das System arbeiten. Diese letzte Klasse von Problemen hat sogar einen eigenen Namen erhalten: das Problem der byzantinischen Generäle. Das bekannteste Beispiel für ein verteiltes System mit diesem Problem ist die Blockchain. Aber heute werden wir diese spezielle Klasse von Problemen nicht betrachten. Uns interessieren Situationen, in denen einfach einer oder mehrere Knoten ausfallen können.
Kommunikationsmodelle (Nachrichtenübertragungsmodelle) zwischen Knoten. Wir haben bereits festgestellt, dass Knoten durch den Austausch von Nachrichten kommunizieren. Es gibt zwei bekannte Modelle des Nachrichtenaustauschs: synchron und asynchron.

Kommunikationsmodelle zwischen Knoten in verteilten Systemen

Synchrones Modell – wir wissen genau, dass es eine endliche, bekannte Zeitspanne gibt, in der eine Nachricht garantiert von einem Knoten zu einem anderen gelangt. Wenn diese Zeit abgelaufen ist und die Nachricht nicht eingetroffen ist, können wir mit Sicherheit sagen, dass der Knoten ausgefallen ist. In einem solchen Modell haben wir eine vorhersehbare Wartezeit.

Asynchrones Modell – in asynchronen Modellen nehmen wir an, dass die Wartezeit endlich ist, aber es gibt keine solche Zeitspanne, nach der man garantieren kann, dass ein Knoten ausgefallen ist. Das heißt, die Wartezeit auf eine Nachricht von einem Knoten kann beliebig lang sein. Dies ist eine wichtige Definition, und wir werden später weiter darüber sprechen.

Das Konzept des Konsenses in verteilten Systemen

Bevor wir das Konzept des Konsenses formal definieren, betrachten wir ein Beispiel für eine Situation, in der wir ihn benötigen, nämlich – State Machine Replication.

Wir haben ein verteiltes Protokoll, das konsistent sein und identische Daten auf allen Knoten des verteilten Systems enthalten sollte. Wenn ein Knoten einen neuen Wert ermittelt, den er in das Protokoll aufnehmen möchte, besteht seine Aufgabe darin, diesen Wert allen anderen Knoten anzubieten, damit das Protokoll auf allen Knoten aktualisiert wird und das System in einen neuen konsistenten Zustand übergeht. Dabei ist es wichtig, dass die Knoten sich untereinander einigen: Alle Knoten müssen zustimmen, dass der vorgeschlagene neue Wert korrekt ist, und alle Knoten müssen diesen Wert akzeptieren, bevor sie gemeinsam den neuen Wert in das Protokoll schreiben können.

Mit anderen Worten: Kein Knoten hat widersprochen, dass er aktuellere Informationen hat und der vorgeschlagene Wert falsch ist. Die Vereinbarung zwischen den Knoten und die Zustimmung zu einem einheitlichen, anerkannten Wert ist der Konsens in einem verteilten System. Im Folgenden werden wir über Algorithmen sprechen, die es einem verteilten System ermöglichen, Konsens verlässlich zu erreichen.

Formell können wir den Konsensalgorithmus (oder einfach den Konsensalgorithmus) als eine Funktion definieren, die ein verteiltes System von Zustand A in Zustand B überführt. Dieser Zustand muss von allen Knoten akzeptiert werden, und alle Knoten müssen ihn bestätigen können. Wie sich herausstellt, ist diese Aufgabe alles andere als trivial.

Eigenschaften des Konsensalgorithmus

Der Konsensalgorithmus muss drei Eigenschaften aufweisen, damit das System weiterhin existiert und Fortschritte beim Übergang von einem Zustand in einen anderen erzielt:

Zustimmung – alle korrekt arbeitenden Knoten müssen denselben Wert akzeptieren (in Artikeln wird dieses Merkmal auch als Sicherheitsmerkmal bezeichnet). Alle Knoten, die derzeit funktionsfähig sind (nicht ausgefallen oder vom Rest getrennt), müssen zu einer Übereinstimmung kommen und einen bestimmten endgültigen gemeinsamen Wert akzeptieren.
Hier ist es wichtig zu verstehen, dass die Knoten in unserem betrachteten verteilten System eine Übereinstimmung anstreben. Das bedeutet, wir sprechen jetzt über Systeme, in denen etwas ausfallen kann (zum Beispiel kann ein Knoten ausfallen). In diesem System gibt es jedoch keine Knoten, die absichtlich gegen andere arbeiten (das Problem der byzantinischen Generäle). Durch dieses Merkmal bleibt das System konsistent.
Integrität — wenn alle korrekt funktionierenden Knoten denselben Wert anbieten v, dann muss jeder korrekt funktionierende Knoten diesen Wert akzeptieren v.
Beendigung – alle korrekt funktionierenden Knoten werden letztendlich einen bestimmten Wert annehmen (Liveness-Eigenschaft), was es dem Algorithmus ermöglicht, im System Fortschritte zu erzielen. Jeder einzelne korrekt funktionierende Knoten sollte früher oder später den endgültigen Wert annehmen und dies bestätigen: „Für mich ist dieser Wert wahr, ich stimme mit dem gesamten System überein.“

Beispiel für das Funktionieren eines Konsensalgorithmus

Während die Eigenschaften des Algorithmus möglicherweise nicht ganz verständlich sind, lassen Sie uns anhand eines Beispiels veranschaulichen, welche Phasen ein einfacher Konsensalgorithmus in einem System mit synchronem Nachrichtenaustausch durchläuft, in dem alle Knoten ordnungsgemäß funktionieren, Nachrichten nicht verloren gehen und nichts kaputtgeht (passiert das wirklich?).

Alles beginnt mit dem Vorschlag (Propose). Angenommen, ein Client hat sich mit einem Knoten namens „Knoten 1“ verbunden und eine Transaktion gestartet, indem er dem Knoten einen neuen Wert – O – überträgt. Ab diesem Moment nennen wir „Knoten 1“ proposer. Als proposer muss „Knoten 1“ nun das gesamte System darüber informieren, dass er neue Daten hat, und er sendet an alle anderen Knoten die Nachricht: „Sehen Sie! Ich habe den Wert „O“ erhalten und möchte ihn aufzeichnen! Bitte bestätigen Sie, dass Sie ebenfalls „O“ in Ihr Protokoll aufnehmen werden.“
Die nächste Phase ist die Abstimmung über den vorgeschlagenen Wert (Voting). Warum ist sie notwendig? Es könnte sein, dass andere Knoten aktualisierte Informationen erhalten haben, und sie verfügen über Daten zu derselben Transaktion.

Wenn der Knoten „Knoten 1“ seinen Vorschlag sendet, überprüfen die anderen Knoten die zugehörigen Daten in ihren Protokollen. Wenn es keine Widersprüche gibt, erklären die Knoten: „Ja, ich habe keine anderen Informationen zu diesem Ereignis. Der Wert „O“ ist die aktuellste Information, die wir haben.“
In jedem anderen Fall können die Knoten „Knoten 1“ antworten: „Hör mal! Ich habe aktuellere Informationen zu dieser Transaktion. Nicht „O“, sondern etwas Besseres.“
In der Abstimmungsphase kommen die Knoten zu einer Entscheidung: Entweder akzeptieren alle einen Wert oder einer von ihnen stimmt dagegen und zeigt an, dass er aktuellere Daten hat.
Wenn die Abstimmungsrunde erfolgreich war und alle „für“ gestimmt haben, wechselt das System in die nächste Phase – die Annahme des Wertes (Accept). „Knoten 1“ sammelt alle Antworten der anderen Knoten und meldet: „Alle haben dem Wert „O“ zugestimmt! Jetzt erkläre ich offiziell, dass „O“ unser neuer Wert ist, einheitlich für alle! Notiert es euch, vergesst es nicht. Schreibt es in euer Protokoll!“
Die anderen Knoten senden eine Bestätigung (Accepted), dass sie den Wert „O“ gespeichert haben; in der Zwischenzeit sind keine neuen Informationen eingegangen (eine Art zweiphasiger Commit). Nach diesem bedeutsamen Ereignis betrachten wir die verteilte Transaktion als abgeschlossen.

Der Konsensalgorithmus besteht in einfachen Fällen aus vier Schritten: Vorschlag (propose), Abstimmung (voting), Akzeptanz (accept) und Bestätigung der Akzeptanz (accepted).

Wenn wir in einem der Schritte keinen Konsens erzielen können, wird der Algorithmus neu gestartet, wobei die Informationen berücksichtigt werden, die die Knoten bereitstellen, die sich geweigert haben, den vorgeschlagenen Wert zu bestätigen.

Der Konsensalgorithmus in einem asynchronen System

Bis zu diesem Punkt verlief alles reibungslos, da wir von einem synchronen Nachrichtenmodell sprachen. Aber wir wissen, dass wir in der heutigen Welt alles asynchron erledigen. Wie funktioniert ein ähnlicher Algorithmus in einem System mit einem asynchronen Nachrichtenmodell, in dem wir davon ausgehen, dass die Wartezeit auf eine Antwort des Knotens beliebig lang sein kann (übrigens kann der Ausfall eines Knotens ebenfalls als Beispiel betrachtet werden, bei dem der Knoten beliebig lange antworten kann).

Jetzt, da wir wissen, wie der Konsensalgorithmus grundsätzlich funktioniert, richtet sich die Frage an die neugierigen Leser, die bis hierher gelesen haben: Wie viele Knoten in einem System mit N Knoten und einem asynchronen Nachrichtenmodell können ausfallen, damit das System weiterhin Konsens erreichen kann?

Die richtige Antwort und die Begründung finden Sie hinter dem Spoiler.Die richtige Antwort lautet: 0. Wenn auch nur ein Knoten in einem asynchronen System ausfällt, kann das System keinen Konsens erreichen. Diese Aussage wurde in der bekannten FLP-Theorem (1985, Fischer, Lynch, Paterson, Link zum Original am Ende des Artikels) bewiesen: „Die Unmöglichkeit, einen verteilten Konsens zu erreichen, wenn mindestens ein Knoten ausfällt“.

Leute, dann haben wir ein Problem, wir sind es doch gewohnt, dass alles asynchron ist. Und jetzt ist da so etwas. Wie geht es weiter?

Wir haben gerade über Theorie und Mathematik gesprochen. Was bedeutet „Konsens kann nicht erreicht werden“, wenn wir es von der mathematischen Sprache in unsere – ingenieurtechnische – übersetzen? Das bedeutet, dass „nicht immer ein Konsens erreicht werden kann“, d.h. es gibt einen Fall, in dem Konsens unerreichbar ist. Und welcher Fall ist das?

Dies stellt einen Verstoß gegen die oben beschriebene Liveness-Eigenschaft dar. Es gibt kein gemeinsames Einvernehmen und das System kann keinen Fortschritt erzielen (kann nicht innerhalb einer endlichen Zeit abgeschlossen werden), wenn wir keine Antwort von allen Knoten erhalten. Denn in einem asynchronen System haben wir keine vorhersehbare Antwortzeit, und wir können nicht wissen, ob ein Knoten ausgefallen ist oder einfach nur lange braucht, um zu antworten.

In der Praxis können wir jedoch eine Lösung finden. Angenommen, unser Algorithmus kann im Falle von Ausfällen lange arbeiten (potenziell unbegrenzt). In den meisten Situationen, in denen die meisten Knoten korrekt funktionieren, werden wir Fortschritte im System machen.

In der Praxis arbeiten wir mit teilweise synchronen Kommunikationsmodellen. Teilweise Synchronität wird so verstanden: Im Allgemeinen haben wir ein asynchrones Modell, aber formal wird ein Begriff von „globaler Stabilisationszeit“ an einem bestimmten Zeitpunkt eingeführt.

Dieser Zeitpunkt kann lange auf sich warten lassen, doch eines Tages wird er kommen. Der virtuelle Wecker wird läuten, und ab diesem Moment können wir die Zeitdifferenz vorhersagen, in der Nachrichten ankommen. Von diesem Augenblick an verwandelt sich das System von asynchron in synchron. In der Praxis haben wir es mit genau solchen Systemen zu tun.

Der Paxos-Algorithmus löst Konsensprobleme

Paxos ist eine Familie von Algorithmen, die das Konsensproblem für teilweise synchronisierte Systeme lösen, unter der Voraussetzung, dass einige Knoten ausfallen können. Der Schöpfer von Paxos ist Leslie Lamport. Er präsentierte einen formalen Beweis für das Bestehen und die Korrektheit des Algorithmus im Jahr 1989.

Doch der Beweis erb proved sich als alles andere als trivial. Die erste Veröffentlichung erschien erst im Jahr 1998 (33 Seiten) mit einer Beschreibung des Algorithmus. Es stellte sich heraus, dass sie äußerst schwer verständlich war, und im Jahr 2001 wurde eine Erläuterung des Artikels veröffentlicht, die 14 Seiten umfasste. Die Umfangsangaben der Veröffentlichungen sollen verdeutlichen, dass das Konsensproblem in der Tat nicht einfach ist und hinter solchen Algorithmen eine enorme Anstrengung der klügsten Köpfe steht.

Interessanterweise bemerkte Leslie Lamport in seinem Vortrag, dass es in dem zweiten erklärenden Artikel eine Aussage gibt, eine Zeile (er präzisierte nicht welche), die unterschiedlich interpretiert werden kann. Aus diesem Grund funktionieren viele moderne Implementierungen von Paxos nicht ganz korrekt.

Eine detaillierte Analyse von Paxos würde nicht nur einen Artikel erfordern, daher werde ich versuchen, die Grundidee des Algorithmus sehr kurz zu vermitteln. In den Links am Ende meines Artikels finden Sie Materialien für eine tiefere Einarbeitung in das Thema.

Rollen in Paxos

Im Algorithmus Paxos gibt es das Konzept von Rollen. Schauen wir uns die drei Hauptrollen an (es gibt Modifikationen mit zusätzlichen Rollen):

Proposers (manchmal auch als: Führer oder Koordinatoren bezeichnet). Das sind die Leute, die von einem neuen Wert des Nutzers erfahren und die Rolle des Führers übernehmen. Ihre Aufgabe ist es, eine Runde zur Vorschlag eines neuen Wertes einzuleiten und die weiteren Aktionen der Knoten zu koordinieren. Dabei erlaubt Paxos in bestimmten Situationen mehrere Führer.
Acceptors (Wähler). Dies sind Knoten, die über die Annahme oder Ablehnung eines bestimmten Wertes abstimmen. Ihre Rolle ist sehr wichtig, da sie die Entscheidung treffen, in welchen Zustand das System nach der nächsten Phase des Konsensalgorithmus übergehen wird (oder auch nicht).
Lernende. Knoten, die einfach den neuen angenommenen Wert annehmen und aufzeichnen, wenn sich der Zustand des Systems geändert hat. Sie treffen keine Entscheidungen, sondern erhalten nur Daten und können diese an den Endbenutzer weitergeben.

Ein Knoten kann in unterschiedlichen Situationen mehrere Rollen kombinieren.

Der Begriff Quorum

Wir nehmen an, dass wir ein System aus N Knoten haben. Und aus diesen können maximal F Knoten ausfallen. Wenn F Knoten ausfallen, muss unser Cluster mindestens 2F + 1 Acceptor-Knoten haben.

Dies ist notwendig, damit wir selbst in der schlimmsten Situation immer 'gute', korrekt arbeitende Knoten in der Mehrheit haben. Das heißt, F + 1 Die „guten“ Knoten, die sich bereit erklärt haben, und der endgültige Wert wird angenommen. Andernfalls könnte es zu einer Situation kommen, in der unsere verschiedenen lokalen Gruppen unterschiedliche Werte annehmen und sich nicht einigen können. Daher benötigen wir eine absolute Mehrheit, um im Voting zu gewinnen.

Das Grundkonzept des Paxos-Konsensalgorithmus

Der Paxos-Algorithmus umfasst zwei große Phasen, die jeweils in zwei Schritte unterteilt sind:

Phase 1a: Vorbereiten. In der Vorbereitungsphase informiert der Lieder (Proposer) alle Knoten: „Wir beginnen eine neue Abstimmungsrunde. Wir haben eine neue Runde. Die Nummer dieser Runde ist n. Jetzt werden wir abstimmen.“ Während er lediglich den Beginn eines neuen Zyklus ankündigt, gibt er noch keinen neuen Wert bekannt. Das Ziel dieser Phase besteht darin, eine neue Runde einzuleiten und allen seinen einzigartigen Nummern mitzuteilen. Die Rundenummer ist wichtig; sie muss größer sein als alle vorherigen Abstimmungsnummern aller vorherigen Leiter. Denn nur durch die Rundenummer können die anderen Knoten im System verstehen, wie aktuell die Daten des Leiters sind. Vermutlich verfügen die anderen Knoten bereits über Abstimmungsergebnisse aus wesentlich späteren Runden und können dem Leiter einfach mitteilen, dass er hinterherhängt.
Phase 1b: Versprechen. Wenn die Acceptors die Nummer der neuen Abstimmungsphase erhalten haben, sind zwei Ergebnisse möglich:
- Die Nummer n der neuen Abstimmung ist höher als die Nummer jeder vorherigen Abstimmung, an der der Acceptor teilgenommen hat. In diesem Fall sendet der Acceptor dem Leader ein Versprechen, dass er nicht an weiteren Abstimmungen mit einer niedrigeren Nummer als n teilnehmen wird. Falls der Acceptor bereits für etwas abgestimmt hat (d.h. er hat in der zweiten Phase bereits einen Wert angenommen), fügt er seinem Versprechen den angenommenen Wert und die Nummer der Abstimmung, an der er teilgenommen hat, hinzu.
- Andernfalls, wenn der Acceptor bereits von einer Abstimmung mit einer höheren Nummer weiß, kann er einfach die Vorbereitungsetappe ignorieren und nicht auf den Leader reagieren.
Phase 2a: Akzeptieren. Der Leader muss auf eine Antwort von einem Quorum (der Mehrheit der Knoten im System) warten, und wenn die erforderliche Anzahl von Antworten erhalten wird, hat er zwei Optionen, wie es weitergeht:
- Einige der Acceptor haben Werte gesendet, für die sie bereits abgestimmt haben. In diesem Fall wählt der Leader den Wert aus der Abstimmung mit der höchsten Nummer. Nennen wir diesen Wert x und sendet an alle Knoten eine Nachricht in der Form: „Accept (n, x)“, wobei der erste Wert die Abstimmungsnummer aus seinem eigenen Schritt Propose ist und der zweite Wert dasjenige, weshalb alle zusammengekommen sind, d.h. der Wert, für den wir tatsächlich abstimmen.
- Wenn keiner der Acceptor Werte geschickt hat, sondern einfach versprochen hat, in dieser Runde zu abstimmen, kann der Leader vorschlagen, dass sie für seinen Wert stimmen, also den Wert, weshalb er überhaupt Leader geworden ist. Nennen wir ihn y. Er sendet an alle Knoten eine Nachricht in der Form: „Accept (n, y)“, analog zum vorherigen Ergebnis.
Phase 2b: Akzeptiert. Die Acceptor-Knoten, die die Nachricht „Accept(…)“ vom Leader erhalten, stimmen ihm nur dann zu (senden an alle Knoten eine Bestätigung, dass sie mit dem neuen Wert einverstanden sind), wenn sie nicht einem (anderen) Leader versprochen haben, an Abstimmungen mit der Rundenummer n’ > nteilzunehmen, andernfalls ignorieren sie die Anfrage zur Bestätigung.
Wenn die meisten Knoten auf den Leader geantwortet haben und alle neuen Wert bestätigen, wird der neue Wert als akzeptiert angesehen. Hurra! Wenn jedoch die Mehrheit nicht erreicht wird oder es Knoten gibt, die sich weigern, den neuen Wert anzunehmen, beginnt alles von neuem.

So funktioniert der Paxos-Algorithmus. Jeder dieser Schritte hat viele Feinheiten, wir haben verschiedene Arten von Ausfällen, Probleme mit mehreren Leaders und vieles mehr kaum angesprochen, aber das Ziel dieses Artikels ist es, den Leser auf einer hohen Ebene mit der Welt der verteilten Berechnungen vertraut zu machen.

Es sollte auch beachtet werden, dass Paxos nicht einzigartig ist, es gibt auch andere Algorithmen, wie zum Beispiel Raft, aber das ist ein Thema für einen anderen Artikel.