Korrektheitsnachweise klassischer Paxos und Fast Paxos

Ich lese die Zeitung "Fast Paxos" von Leslie Lamport und bleibe bei den Korrektheitsbeweisen sowohl von klassischem Paxos als auch von schnellem Paxos.

Der Konsistenz halber sollte der vom Koordinator in Phase in Runde gewählte Wert ausreichen2 a $v$$2a$$i$

$CP(v,i):$ Für jede Runde wurde oder könnte in Runde kein anderer Wert als gewählt werden .v $j < i$$v$$j$

Für klassisches Paxos wird der Beweis (Seite 8) in drei Fälle aufgeteilt: , und , wobei die größte runde Zahl ist, in der ein Akzeptor dem Koordinator durch eine Nachricht der Phase berichtet hat . Ich habe das Argument für den dritten Fall nicht verstanden:j = k j < k k 1 $k < j < i$$j = k$$j < k$$k$$1b$

Fall . Wir können induktiv annehmen, dass die Eigenschaft gehalten wurde, als der Akzeptor in Runde für gestimmt hat . Dies impliziert, dass in Runde kein anderer Wert als wurde oder gewählt werden könnte .$j < k$a 0 v k v $CP$$a_0$$v$$k$$v$$j$

Meine Frage ist:

1. Warum können wir annehmen, dass die Eigenschaft gehalten wird, wenn der Akzeptor in Runde für gestimmt hat ?a 0 v $CP$$a_0$$v$$k$

Es scheint, dass wir die mathematische Induktion verwenden. Was sind also die Basis, die induktive Hypothese und die induktiven Schritte?

Für Fast Paxos gilt dasselbe Argument (Seite 18). Es sagt,

Fall . Für jedes in wurde oder könnte in Runde kein anderer Wert als gewählt werden .v V v $j < k$$v$$V$$v$$j$

Meine Frage ist:

2. Wie wird das erreicht? Warum steht hier insbesondere "For any in "?$v$$V$

Meiner Meinung nach beruht der Korrektheitsnachweis für den Fall (rekursiv) auf jenen für Fälle von und . k < j < i j = $j < k$$k < j < i$$j = k$

Wie können wir also den Fall abschließen, ohne zuerst vollständig zu beweisen (dh den Unterfall von j = k zu vermissen, wobei V mehr als einen Wert enthält)?$j < k$$j = k$$j = k$$V$

Warum können wir annehmen, dass die Eigenschaft CP gehalten wird, wenn der Akzeptor a0 in Runde k für v gestimmt hat? Es scheint, dass wir die mathematische Induktion verwenden. Was sind also die Basis, die induktive Hypothese und die induktiven Schritte?

Sie sehen eine starke Induktion . In der einfachen Induktion nehmen Sie an, dass die Eigenschaft für und beweisen, dass sie für . Bei starker Induktion nehmen Sie an, dass die Eigenschaft für für alle und beweisen, dass sie für .n = m + 1 ∀ n : n < m n = m + $n=m$$n=m+1$$\forall n: n<m$$n=m+1$

Basis (glaube ich): . Das heißt, die Nullrunde (da die Runden bei 1 beginnen). Dies ist trivial wahr, weshalb es wahrscheinlich nicht explizit angegeben wurde.$j = 0$

Induktiver Schritt : Es sei ; beweise mit .C P ( v , j + 1 ) j < $\forall n, n \le j : CP(v; n)$$CP(v; j+1)$$j < i$

Ob Sie es glauben oder nicht, dies ist nur eine Beweisskizze . Der eigentliche Beweis ist in der Tageszeitung des Parlaments zu finden . (Einige halten das Papier für kryptisch, andere für humorvoll.)

Wie wird das erreicht?

Meiner Meinung nach beruht der Korrektheitsnachweis für den Fall (rekursiv) auf jenen für Fälle von und .k < j < i j = $j<k$$k<j<i$$j=k$

Wie können wir also den Fall abschließen, ohne zuerst vollständig zu beweisen (dh den Unterfall von vermissen, wobei mehr als einen Wert enthält)?j = k j = k $j<k$$j=k$$j=k$$V$

Dies ist wieder eine starke Induktion, so dass der Fall von den Fällen und , aber durch die Induktionshypothese , nämlich von der vorhergehenden Paxos-Runde.k < j j = $j<k$$k<j$$j=k$

Allgemeine Tipps für die Beweise von Lamport.

Lamport verwendet eine Technik hierarchischer Beweise. Zum Beispiel sieht die Struktur des Proofs auf den Seiten 7-8 ungefähr so ​​aus:

• Angenommen, ; beweise mit . C P ( v , j + 1 ) j < $\forall n, n \le j : CP(v; n)$$CP(v; j+1)$$j < i$
  1. Beobachtung 1
  2. Beobachtung 2
  3. Beobachtung 3
  4. $k = argmax (...)$
  5. Fall k = 0
  6. Fall k> 0
     • case k <j
     • case k = j
     • case j <k

Lamport tendiert dazu, eine andere Art von Hierarchie zu verwenden. Er wird einen einfacheren Algorithmus beweisen und dann beweisen, dass ein komplexerer Algorithmus auf den einfacheren Algorithmus abgebildet (oder "erweitert" ) wird. Dies scheint auf Seite 18 nicht zu geschehen, aber es ist etwas, worauf Sie achten müssen. (Der Proof auf Seite 18 scheint eine Modifikation des Proofs auf den Seiten 7-8 zu sein, keine Erweiterung .)

Lamport verlässt sich stark auf starke Induktion ; er neigt auch dazu, in Mengen statt in Zahlen zu denken . Sie erhalten also möglicherweise leere Mengen, in denen andere Nullen oder Nullen haben würden. oder stellen Sie Gewerkschaften ein, bei denen andere zusätzliche Möglichkeiten hätten.

Der Nachweis der Korrektheit asynchroner Nachrichtenübermittlungssysteme erfordert eine allwissende Sicht auf das System in Bezug auf die Zeit . Wenn Sie beispielsweise Aktionen in Runde in Betracht ziehen , denken Sie daran, dass die Aktionen für einige Runde möglicherweise nicht zeitlich verlaufen sind! . Und doch nennt Lamport diese potenziell zukünftigen Ereignisse in der Vergangenheitsform.j < $i$$j < i$

Lamports-Systeme und Beweise haben in der Regel eine Variable oder eine Reihe von Variablen, die nur in eine Richtung gehen dürfen. Nur inkrementelle Zahlen und nur das Hinzufügen zu Mengen. Dies wird ausgiebig in seinen Beweisen verwendet. Zum Beispiel zeigt Lamport auf Seite 8, wie er die zukünftige Fähigkeit von neutralisierte, weitere Stimme abzugeben:$a$

... Da es Satz bis auf eine Nachricht senden, anschließend eine Abstimmung kann nicht in jeder Runde geworfen nummeriert weniger als ....i a $rnd[a]$$i$$a$$i$

Es ist definitiv ein Hirnstrecker, um diese Art von Systemen zu beweisen.

(Update) : Liste die Invarianten auf; Lamport verwendet bei der Entwicklung und seinen Beweisen viele Invarianten. Sie sind manchmal über die Beweise verstreut; manchmal sind sie nur im maschinengeprüften Proof enthalten. Grund über jede Invariante; warum ist es dort Wie interagiert es mit den anderen Invarianten? Wie hält jeder Schritt im System diese Invariante aufrecht?

Vollständige Offenlegung : Ich hatte Fast Paxos erst gelesen, als ich gebeten wurde, diese Frage zu beantworten. und sah nur die Seiten zitiert. Ich bin Ingenieur und kein Mathematiker. Meine Arbeit mit Lamport basiert lediglich auf der Notwendigkeit, verteilte Großsysteme richtig zu erfinden und zu warten.

Meine Antwort hängt stark von meiner Erfahrung mit Lamports Arbeit ab. Ich habe mehrere Protokolle und Beweise von Lamport gelesen. Ich unterhalte professionell ein Paxos-basiertes System. Ich habe ein Hochdurchsatz-Konsensprotokoll geschrieben und bewiesen und wieder professionell ein darauf basierendes System gepflegt (ich versuche, mein Unternehmen dazu zu bringen, dass ich ein Papier veröffentlichen kann). Ich habe mit Lamport an einer unbedeutenden Veröffentlichung zusammengearbeitet, in der ich ihn dreimal getroffen habe (die Veröffentlichung steht noch aus.)