PaxosThe ultimate consensus ?

Vortragsaufbau

Teil I – Einführung• Funktionsweise des Paxos – Algorithmus• Kommunikationsprimitiven• Rundenablauf• Beispielrunden

Teil 2 – Paxos formal• Paxos als I/O – Automat• Beweis von Validity und Agreement

PAXOS Name einer alten griechischen Hochkultur Leslie Lamport beschrieb den Paxos-

Algorithmus als Ergebnis archäologischer Studien dieser Kultur (L.Lamport[98]-„The part-time parliament“)

Höchst fehlertoleranter Distributed-Consesus-Algorithmus, der Validity, Agreement und unter Umständen auch Termination garantiert

Complete Paxos

Basic Paxos

Sichert Validity und Agreement Termination nur unter der Annahme eines einzigen Leaders

Externe Primitiven von PAX

NewRound(value) : Startet eine neue Runde RndSuccess(value‘) : Meldet eine Entscheidung

Neue Runden können beliebig oft gestartet werden.

Validity & Agreement

Validity: Trivial Agreement: Alle per RndSuccess(v) gemeldeten v

müssen identisch sein

Komponenten von PAX

2 unabhängige Komponenten Leader-Komponente bietet die externen

Primitiven NewRnd(v) und RndSuccess(v‘) Acceptor dient nur interner Kommunikation

Interne Kommunikation

Jede Leader-Komponente kommuniziert nur mit Acceptor-Komponenten (auch mit der eigenen)

Runden Paxos läuft in Form von „Runden“ aus N x P Es existiert eine Ordnung auf den Runden:

r < r‘ gdw. (r.n < r‘.n) oder ( (r.n = r‘.n) und (r.p < r‘.p) )

Jede Runde r hat maximal 1 zugehörige Leader-Komponente

Jede Nachricht zwischen Leader und Acceptors trägt diese Rundennummer r

Component states

Rot: „Aktuelle Rundennummer“ Grün: „Höchste bekannte erfolgreiche Runde“ Blau: „Value der höchsten bekannten erfolgreichen Runde“

NewRound(v)

Leader: CurRnd := CurRnd + 1 HighestRnd := 0

RndVal := v

Collect()^r

Leader sendet Collect()^CurRnd an alle Acceptor

Join(r‘,v‘)^r

Acceptors: IF (r > Commit) Commit = r ; Send(Join, LastR, LastV)^r

Leader: IF (r‘ > HighestRnd) HighestRnd = r‘ ; RndVal = v‘

Store(val)^r

Sobald der Leader von einer Mehrheit der Prozesse Join-Nachrichten bekommen hat, sendet er allen Acceptors ein Store(RndVal)^CurRnd

Accept()^r

Acceptors: if ( r >= Commit ) Commit = r ; LastR = r ; LastV = val; Send(Accept)^r

Leader: Sobald von einer Mehrheit der Acceptors Accept-Nachrichten empfangen wurde, wird RndSuccess(RndVal) ausgeführt.

Kompaktes Beispiel

Frage

Was passiert wenn nun ein andere Leader eine Runde 1‘ mit einem anderen Value v‘ startet ?

Angenommen der neue Leader hat eine höhere

Prozessnummer, d.h. seine Runde 1‘ ist höher als die Runde 1 des alten Leaders.

Kompaktes Beispiel (Forts.)

Teil II

Paxos als I/O - Automat