View
49
Download
2
Category
Preview:
DESCRIPTION
Paxos. The 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. - PowerPoint PPT Presentation
Citation preview
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
Recommended