🥇Schrödingers Katze ohne Kiste: Das Konsensproblem in verteilten Systemen

Stellen wir uns vor. In einem Raum sind 5 Katzen eingesperrt, und 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 die Katze Schrödingers ist und die anderen Katzen nichts von ihrer Entscheidung wissen, stellt sich die Frage: „Wie können sie das tun?“

In diesem Artikel werde ich Ihnen in einfachen Worten die theoretischen Grundlagen der Welt der verteilten Systeme und deren Arbeitsprinzipien erläutern. Außerdem werde ich oberflächlich die Hauptidee hinter Paxos betrachten.

Wenn Entwickler Cloud-Infrastrukturen, verschiedene Datenbanken und Cluster mit einer großen Anzahl von Knoten nutzen, sind sie sich sicher, dass die Daten intakt, gesichert und jederzeit verfügbar sind. Aber woher kommen die Garantien?

Im Grunde genommen sind die Garantien, die wir haben, die Garantien des Anbieters. Diese werden in der Dokumentation ungefähr wie folgt beschrieben: „Dieser Service ist zuverlässig genug, er hat ein vorgegebenes SLA, machen Sie sich keine Sorgen, alles wird verteilt funktionieren, wie Sie es erwarten.“

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

Vor kurzem bin ich zu einer Schule für verteilte Berechnungen gefahren und war von diesem Thema sehr inspiriert. Die Vorlesungen in der Schule erinnerten mehr an Mathematikanalysis, als an etwas, das mit Computersystemen zu tun hat. Aber genau so wurden zur damaligen Zeit die entscheidenden Algorithmen bewiesen, die wir jeden Tag nutzen, 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 prinzipiell die Möglichkeit, dass dieser Algorithmus existiert, einfach mit Stift und Papier bewiesen werden kann. Gleichzeitig wird der Algorithmus in der Praxis in großen Systemen eingesetzt, die auf einer riesigen Anzahl von Knoten in Clouds laufen.

Eine einfache Illustration dafür, worum es gleich gehen wird: das Problem der zwei Generäle.Lassen Sie uns zur Auflockerung die Aufgabe der zwei Generäle betrachten..

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 Kommando der Generäle A1 und A2 sind auf beiden Seiten der Stadt positioniert. Die Aufgabe der Roten ist es, die weiße Stadt anzugreifen und zu siegen. Allerdings ist die Armee jedes roten Generals für sich genommen kleiner als die der Weißen.

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

Um sich zu verständigen, können die Generäle A1 und A2 Boten durch das Gebiet der weißen Stadt senden. Ein Bote kann den verbündeten General erfolgreich erreichen oder von den Gegnern abgefangen werden. Frage: Gibt es eine solche Abfolge von Kommunikationen zwischen den roten Generälen (eine Sequenz von Boten, die von A1 zu A2 und umgekehrt von A2 zu A1 gesendet werden), bei der sie garantiert eine Einigung über den Angriff zur Stunde X erreichen? Hierbei wird unter Garantien verstanden, dass beide Generäle eine eindeutige Bestätigung erhalten, dass der Verbündete (der andere General) genau zur vereinbarten Zeit X angreift.

Angenommen, A1 sendet einen Boten zu A2 mit der Botschaft: „Lass uns heute 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 Botschaft: „Ja, lass uns heute die Weißen überrennen“. Doch jetzt weiß General A2 nicht, ob sein Bote angekommen ist oder nicht, er hat keine Garantien, dass der Angriff gleichzeitig erfolgt. Nun benötigt auch General A2 wieder eine Bestätigung.

Wenn man ihre Kommunikation weiter ausführt, wird sich Folgendes herausstellen: Egal wie viele Zyklen des Nachrichtenaustauschs es gibt, es gibt keinen Weg, beide Generäle garantiert darüber zu informieren, dass ihre Nachrichten erhalten wurden (vorausgesetzt, dass einer der Boten abgefangen werden kann).

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

Wir führen den Begriff der verteilten Systeme ein.

Ein verteiltes System ist eine Gruppe von Computern (im Folgenden als Knoten bezeichnet), die Nachrichten austauschen können. Jeder einzelne Knoten ist eine gewisse autonome Entität. Der Knoten kann Aufgaben eigenstä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, interessiert uns in diesem Kontext nicht. Wichtig ist, dass die Knoten des verteilten Systems Daten miteinander austauschen können, indem sie Nachrichten senden.

Die Definition selbst scheint nicht sehr komplex zu sein, aber man muss bedenken, dass ein verteiltes System eine Reihe von Attributen hat, die für uns wichtig sein werden.

Attribute vernetzter Systeme

Nebenläufigkeit – die Möglichkeit des Auftretens gleichzeitiger oder konkurrierender Ereignisse im System. Darüber hinaus werden wir davon ausgehen, dass Ereignisse, die an zwei verschiedenen Knoten aufgetreten sind, potenziell konkurrierend sind, solange wir keine klare Reihenfolge haben, in der diese Ereignisse aufgetreten sind. Und normalerweise haben wir diese nicht.
Fehlen globaler Uhren. Wir haben keine klare Reihenfolge der Ereignisse aufgrund des Fehlens globaler Uhren. In der normalen Welt der Menschen sind wir es gewohnt, dass wir Uhren haben und die Zeit absolut ist. Alles ändert sich, wenn es um verteilte Systeme geht. Selbst hochpräzise Atomuhren haben einen Drift, und es kann Situationen geben, in denen wir nicht sagen können, welches der beiden Ereignisse zuerst aufgetreten ist. Daher können wir uns auch nicht auf die Zeit verlassen.
Unabhängiger Ausfall der Knoten im System. Es gibt ein weiteres Problem: Etwas kann einfach schiefgehen, weil unsere Knoten nicht ewig sind. Eine Festplatte kann ausfallen, eine virtuelle Maschine in der Cloud kann neu gestartet werden, das Netzwerk kann aussetzen und Nachrichten können verloren gehen. Darüber hinaus kann es Situationen geben, in denen Knoten funktionieren, aber dabei 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 den Knoten. Wir haben bereits festgestellt, dass Knoten über den Austausch von Nachrichten kommunizieren. Es gibt zwei bekannte Modelle für den Nachrichtenaustausch: synchron und asynchron.

Kommunikationsmodelle zwischen Knoten in verteilten Systemen

Synchrones Modell – wir wissen genau, dass eine endliche, bekannte Zeitdifferenz besteht, nach der eine Nachricht garantiert von einem Knoten zum 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 gehen wir davon aus, dass die Wartezeit endlich ist, jedoch gibt es keine solche Zeitdifferenz, nach deren Ablauf wir garantieren können, dass der Knoten ausgefallen ist. Das heißt, die Wartezeit auf eine Nachricht von einem Knoten kann beliebig lang sein. Dies ist eine wichtige Definition, über die wir weiter sprechen werden.

Der Begriff des Konsenses in verteilten Systemen

Ehe wir den Begriff Konsens formal definieren, betrachten wir ein Beispiel, in dem er benötigt wird, nämlich – State Machine Replication.

Wir haben ein gewisses verteiltes Protokoll. Wir möchten, dass es konsistent ist und identische Daten auf allen Knoten des verteilten Systems enthält. Wenn einer der Knoten einen neuen Wert erfährt, den er im Protokoll speichern möchte, besteht seine Aufgabe darin, diesen Wert allen anderen Knoten vorzuschlagen, damit das Protokoll auf allen Knoten aktualisiert wird und das System in einen neuen konsistenten Zustand übergeht. Dabei ist es wichtig, dass sich die Knoten untereinander einigen: Alle Knoten stimmen zu, dass der vorgeschlagene neue Wert korrekt ist, alle Knoten haben diesen Wert akzeptiert, und nur in diesem Fall können alle den neuen Wert im Protokoll speichern.

Mit anderen Worten: Keiner der Knoten hat widersprochen, dass er aktuellere Informationen hat und dass der vorgeschlagene Wert falsch ist. Die Vereinbarung zwischen den Knoten und die Einigung über einen einheitlichen, akzeptierten Wert ist der Konsens in einem verteilten System. Im Folgenden werden wir über Algorithmen sprechen, die es dem verteilten System ermöglichen, konsistent Konsens zu erreichen.

Formell gesagt können wir den Konsensalgorithmus (oder einfach Konsensalgorithmus) als eine Funktion definieren, die ein verteiltes System von Zustand A nach Zustand B überführt. Dabei ist dieser Zustand von allen Knoten akzeptiert, und alle Knoten können ihn bestätigen. Wie sich herausstellt, ist diese Aufgabe alles andere als trivial, wie es auf den ersten Blick scheint.

Eigenschaften des Konsensalgorithmus

Der Konsensalgorithmus muss drei Eigenschaften aufweisen, damit das System weiterhin besteht und einen Fortschritt beim Übergang von einem Zustand zum nächsten hat:

Einigungszustimmung – alle korrekt funktionierenden Knoten müssen denselben Wert akzeptieren (dieses Merkmal wird in den Artikeln auch als Sicherheitsmerkmal bezeichnet). Alle Knoten, die derzeit funktionsfähig sind (nicht ausgefallen oder desynchronisiert sind), müssen sich einigen und einen bestimmten endgültigen gemeinsamen Wert annehmen.
Hier ist es wichtig zu verstehen, dass die Knoten in dem von uns betrachteten verteilten System sich einigen wollen. Das heißt, wir sprechen jetzt über Systeme, in denen einfach etwas ausfallen kann (zum Beispiel kann ein bestimmter Knoten ausfallen), aber in diesem System gibt es keine Knoten, die absichtlich gegen andere arbeiten (wie bei dem Problem der byzantinischen Generäle). Aufgrund dieser Eigenschaft bleibt das System konsistent.
Integrität – wenn alle korrekt funktionierenden Knoten denselben Wert vorschlagen v, bedeutet das, dass jeder korrekt funktionierende Knoten diesen Wert annehmen muss. v.
Beendigung – alle korrekt funktionierenden Knoten müssen schließlich einen bestimmten Wert annehmen (Lebensfähigkeitseigenschaft), was dem Algorithmus Fortschritt im System ermöglicht. Jeder einzelne korrekt funktionierende Knoten muss irgendwann 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 die Funktionsweise des Konsensalgorithmus

Während die Eigenschaften des Algorithmus möglicherweise nicht ganz klar sind, wollen wir an einem Beispiel veranschaulichen, welche Phasen der einfachste Konsensalgorithmus in einem System mit synchronem Nachrichtenmodell durchläuft, in dem alle Knoten ordnungsgemäß funktionieren, Nachrichten nicht verloren gehen und nichts kaputt geht (passiert das tatsächlich?)).

Alles beginnt mit dem Vorschlag zur Hand und zum Herzen (Propose). Angenommen, ein Client hat sich mit dem Knoten namens „Knoten 1“ verbunden und eine Transaktion gestartet, indem er dem Knoten den neuen Wert – O – übermittelt hat. Ab diesem Moment nennen wir „Knoten 1“ proposer. Als proposer muss „Knoten 1“ nun das gesamte System darüber informieren, dass er frische Daten hat, und er sendet an alle anderen Knoten Nachrichten: „Seht her! Mir wurde der Wert „O“ übermittelt, und ich möchte ihn speichern! Bitte bestätigt, dass auch ihr „O“ in euer Protokoll aufnehmen werdet.“
Die nächste Phase ist die Abstimmung über den vorgeschlagenen Wert (Voting). Warum ist sie notwendig? Es könnte sein, dass anderen Knoten aktuellere Informationen zugetragen wurden und sie Daten zu derselben Transaktion haben.

Wenn der Knoten „Knoten 1“ seinen Vorschlag sendet, überprüfen die anderen Knoten in ihren Protokollen die Daten zu diesem Ereignis. Wenn es keine Widersprüche gibt, erklären die Knoten: „Ja, ich habe keine anderen Daten 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 zu! Ich habe aktuellere Daten 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 dafür waren, geht das System in die nächste Phase über – die Annahme des Wertes (Accept). „Knoten 1“ sammelt alle Antworten der anderen Knoten und teilt mit: „Alle haben dem Wert „O“ zugestimmt! Jetzt erkläre ich offiziell, dass „O“ unser neues, einheitliches Wert ist! Schreibt es euch in euer Notizbuch, vergesst es nicht. Tragt es in euer Protokoll ein!“
Die anderen Knoten senden eine Bestätigung (Accepted), dass sie den Wert „O“ in ihr Protokoll aufgenommen haben, und es gab in der Zwischenzeit keine neuen Informationen (eine Art zweiphasiger Commit). Nach diesem denkwürdigen Ereignis betrachten wir die verteilte Transaktion als abgeschlossen.

So besteht der Konsensalgorithmus im einfachsten Fall aus vier Schritten: propose, Abstimmung (voting), Annahme (accept), Bestätigung der Annahme (accepted).

Wenn wir in einem Schritt keinen Konsens erreichen konnten, wird der Algorithmus neu gestartet, unter Berücksichtigung der Informationen, die die Knoten, die sich weigerten, den vorgeschlagenen Wert zu bestätigen, bereitstellen.

Konsensalgorithmus in einem asynchronen System

Bis jetzt lief alles glatt, denn es ging um ein synchrones Kommunikationsmodell. Aber wir wissen, dass wir in der modernen Welt alles asynchron machen. Wie funktioniert also ein ähnlicher Algorithmus in einem System mit asynchronem Nachrichtenaustausch, in dem wir annehmen, dass die Wartezeit auf eine Antwort von einem Knoten beliebig lang sein kann (zumal man auch den Ausfall eines Knotens als Beispiel betrachten kann, wenn der Knoten beliebig lange antworten kann).

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

Die richtige Antwort und die Begründung sind hinter dem Spoiler.Die richtige Antwort: 0. Wenn in einem asynchronen System auch nur ein Knoten ausfällt, kann das System keinen Konsens erreichen. Diese Aussage ist in dem bestimmten Kreisen bekannten FLP-Theorem (1985, Fischer, Lynch, Paterson, Link zum Original am Ende des Artikels) bewiesen: „Die Unmöglichkeit, 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 das. Wie geht es weiter?

Wir haben gerade über Theorie, über Mathematik gesprochen. Was bedeutet es, dass „Konsens nicht erreicht werden kann“, wenn wir aus der mathematischen Sprache in unsere Ingenieursprache übersetzen? Das bedeutet, dass „nicht immer erreicht werden kann“, d.h. es gibt einen Fall, in dem Konsens nicht erreichbar ist. Aber was ist das für ein Fall?

Das ist genau das Versagen der liveness property, die oben beschrieben wurde. Wir haben kein gemeinsames Einvernehmen, und das System kann keinen Fortschritt haben (kann nicht innerhalb einer endlichen Zeit abgeschlossen werden), wenn wir keine Antwort von allen Knoten haben. 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 antwortet.

Aber in der Praxis können wir eine Lösung finden. Nehmen wir an, unser Algorithmus könnte im Falle von Ausfällen lange arbeiten (potenziell unbegrenzt). Doch in den meisten Situationen, wenn die Mehrheit der Knoten korrekt funktioniert, werden wir Fortschritt im System haben.

In der Praxis haben wir es mit teilweise synchronen Kommunikationsmodellen zu tun. Teilweise Synchronität bedeutet, dass wir im Allgemeinen ein asynchrones Modell haben, aber formal wird ein gewisses Konzept der "globalen Stabilisationszeit" an einem bestimmten Moment eingeführt.

Dieser Moment kann unbegrenzt lange auf sich warten lassen, aber eines Tages muss er eintreten. Ein virtueller Wecker wird klingeln und ab diesem Moment können wir die Zeitdifferenz vorhersagen, die benötigt wird, damit die Nachrichten ankommen. Ab diesem Moment wird das System von asynchron in synchron umgewandelt. In der Praxis haben wir es genau mit solchen Systemen zu tun.

Der Paxos-Algorithmus löst Konsensprobleme.

Paxos ist eine Familie von Algorithmen, die das Konsensproblem für teilweise synchrone Systeme lösen, vorausgesetzt, dass einige Knoten ausfallen können. Der Urheber von Paxos ist Leslie Lamport. Er schlug 1989 einen formalen Beweis für die Existenz und Korrektheit des Algorithmus vor.

Aber der Beweis stellte sich als alles andere als trivial heraus. Die erste Veröffentlichung erschien erst 1998 (33 Seiten) mit einer Beschreibung des Algorithmus. Wie sich herausstellte, war er äußerst schwer verständlich, und im Jahr 2001 wurde eine Erläuterung zu dem Artikel veröffentlicht, die 14 Seiten umfasste. Die Seitenzahlen wurden erwähnt, um zu zeigen, dass das Konsensproblem in Wirklichkeit alles andere als einfach ist und hinter solchen Algorithmen immense Mühen der klügsten Köpfe stehen.

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

Eine ausführliche Analyse der Funktionsweise von Paxos müsste mindestens einen Artikel umfassen, daher werde ich versuchen, die Hauptidee des Algorithmus sehr kurz zu vermitteln. In den Links am Ende meines Artikels finden Sie Materialien für ein tiefergehendes Studium dieses Themas.

Rollen in Paxos

Im Paxos-Algorithmus gibt es das Konzept der Rollen. Lassen Sie uns die drei Hauptrollen betrachten (es gibt Modifikationen mit zusätzlichen Rollen):

Proposers (auch können die Begriffe: Leiter oder Koordinatoren verwendet werden). Das sind die Leute, die von einem neuen Wert des Benutzers erfahren und die Rolle des Leaders übernehmen. Ihre Aufgabe ist es, eine Runde zur Einführung eines neuen Wertes zu starten und die weiteren Schritte der Knoten zu koordinieren. Paxos erlaubt dabei das Vorhandensein mehrerer Leader in bestimmten Situationen.
Akzeptoren (Wähler). Das sind Knoten, die für die Annahme oder Ablehnung eines bestimmten Wertes stimmen. Ihre Rolle ist sehr wichtig, denn von ihnen hängt die Entscheidung ab, in welchen Zustand das System nach der nächsten Phase des Konsensalgorithmus übergeht (oder nicht übergeht).
Lerner. Knoten, die einfach den neuen angenommenen Wert akzeptieren und aufzeichnen, wenn sich der Zustand des Systems ändert. Sie treffen keine Entscheidungen, sondern erhalten lediglich Daten und können diese an den Endbenutzer weitergeben.

Ein Knoten kann in verschiedenen Situationen mehrere Rollen kombinieren.

Das Konzept des Quorums

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

Dies ist notwendig, damit wir immer, selbst in der schlechtesten Situation, eine Mehrheit aus "guten", korrekt funktionierenden Knoten haben. Das heißt, F + 1 "gute" Knoten, die zugestimmt haben, und der finale Wert wird angenommen. Andernfalls könnte es zu einer Situation kommen, in der verschiedene lokale Gruppen unterschiedliche Werte annehmen und sich nicht einigen können. Daher benötigen wir eine absolute Mehrheit, um in der Abstimmung zu gewinnen.

Die allgemeine Idee des Paxos-Konsensusalgorithmus

Der Paxos-Algorithmus besteht aus zwei großen Phasen, die jeweils in zwei Schritte unterteilt sind:

Phase 1a: Vorbereiten. In der Vorbereitungsphase informiert der Führer (proposer) alle Knoten: „Wir beginnen eine neue Phase der Abstimmung. Wir haben eine neue Runde. Die Nummer dieser Runde ist n. Jetzt beginnen wir zu votieren“. Er informiert lediglich über den Beginn eines neuen Zyklus, ohne jedoch einen neuen Wert bekannt zu geben. Die Aufgabe dieses Schrittes ist es, eine neue Runde einzuleiten und allen seine einzigartige Nummer mitzuteilen. Die Rundenummer ist wichtig; sie muss größer sein als alle vorherigen Abstimmungsnummern von allen vorherigen Führern. Denn nur durch die Rundenummer werden andere Knoten im System verstehen, wie aktuell die Daten des Führers sind. Wahrscheinlich haben die anderen Knoten bereits Abstimmungsergebnisse aus deutlich späteren Runden und werden dem Führer einfach mitteilen, dass er hinterherhinkt.
Phase 1b: Versprechen. Wenn die Akzeptorknoten die Nummer der neuen Abstimmungsphase erhalten, sind zwei Ergebnisse möglich:
- Die Nummer n der neuen Abstimmung ist größer als die Nummer jeder vorherigen Abstimmung, an der der Akzeptor teilgenommen hat. In diesem Fall sendet der Akzeptor dem Führer ein Versprechen, dass er nicht mehr an Abstimmungen mit einer Nummer teilnehmen wird, die kleiner ist als n. Wenn der Akzeptor bereits für etwas abgestimmt hat (d.h. wenn er in der zweiten Phase einen Wert angenommen hat), fügt er seinem Versprechen den angenommenen Wert und die Abstimmungsnummer, an der er teilgenommen hat, hinzu.
- Andernfalls, wenn der Akzeptor bereits von einer Abstimmung mit einer höheren Nummer weiß, kann er einfach die Vorbereitungsphase ignorieren und dem Führer nicht antworten.
Phase 2a: Akzeptieren. Der Führer muss auf eine Antwort von der Mehrheit (überwiegender Teil der Knoten im System) warten, und wenn die erforderliche Anzahl von Antworten erhalten wurde, hat er zwei Möglichkeiten:
- Einige der Akzeptoren haben Werte geschickt, für die sie bereits abgestimmt haben. In diesem Fall wählt der Führer den Wert aus der Abstimmung mit der höchsten Nummer. Nennen wir diesen Wert x, und er sendet allen Knoten eine Nachricht in der Form: „Akzeptieren (n, x)“, wobei der erste Wert die Abstimmungsnummer aus seinem eigenen Schritt Propose ist und der zweite Wert das ist, wofür sich alle versammelt haben, d.h. der Wert, für den wir tatsächlich abstimmen.
- Wenn keiner der Acceptor die Werte geschickt hat und sie einfach nur versprochen haben, in dieser Runde abzustimmen, kann der Leader ihnen vorschlagen, für seinen Wert zu stimmen, das ist der Wert, wegen dem er überhaupt Leader geworden ist. Nennen wir ihn y. Er sendet an alle Knoten eine Nachricht der Art: „Accept (n, y)“, ähnlich wie im vorherigen Ergebnis.
Phase 2b: AkzeptiertWenn die Acceptors die Nachricht „Accept(…)“ vom Leader erhalten, stimmen sie nur dann mit ihm überein (senden allen Knoten eine Bestätigung, dass sie dem neuen Wert zustimmen), wenn sie einem (anderen) Leader nicht versprochen haben, an Abstimmungen mit der Rundennummer teilzunehmen n’ > n, andernfalls ignorieren sie die Bestätigungsanfrage.
Wenn die Mehrheit der Knoten dem Leader geantwortet hat und alle den neuen Wert bestätigt haben, wird der neue Wert als akzeptiert angesehen. Hurra! Wenn jedoch die Mehrheit nicht erreicht ist oder einige Knoten sich weigern, den neuen Wert zu akzeptieren, beginnt alles von neuem.

So funktioniert der Paxos-Algorithmus. Jeder dieser Schritte hat viele Feinheiten, wir haben praktisch keine verschiedenen Arten von Ausfällen, die Probleme mehrerer Leader und vieles mehr betrachtet, aber das Ziel dieses Artikels ist es, den Leser auf einer hohen Ebene mit der Welt der verteilten Berechnungen vertraut zu machen.

Es ist auch erwähnenswert, dass Paxos nicht das einzige seiner Art ist, es gibt auch andere Algorithmen, wie zum Beispiel Raft, aber das ist schon ein Thema für einen anderen Artikel.