Entspricht die Linearisierbarkeit dem Konsensproblem?

9

In der Einleitung dieses Papiers Schließlich linearisierbare gemeinsame Objekte (PODC'10) haben die Autoren die folgende Aussage ohne Referenzen präsentiert:

Die Linearisierbarkeit kann jedoch nur dann erreicht werden, wenn ein Konsens gelöst werden kann.

Hier ist die Linearisierbarkeit die stärkste bekannte Konsistenz-Eigenschaft von gemeinsam genutzten Objekten, die in der Veröffentlichung Linearisierbarkeit: Eine Korrektheitsbedingung für gleichzeitige Objekte vorgeschlagen wird .

Die folgende Aussage verwirrt mich aufgrund der folgenden Argumente:

In dem Artikel "Robustes Speichern von Speicher in Nachrichtenübermittlungssystemen" (JACM95) wissen wir, dass Linearisierbarkeit im asynchronen Nachrichtenübermittlungssystem erreicht werden kann, während eine Minderheit von Prozessabstürzen toleriert wird:

Jeder wartungsfreie Algorithmus, der auf atomaren Single-Writer-Multi-Reader-Registern basiert, kann in Nachrichtenübermittlungssystemen automatisch emuliert werden, vorausgesetzt, dass mindestens ein Großteil der Prozessoren nicht fehlerhaft ist und verbunden bleibt.

Andererseits hat das Papier Unmöglichkeit eines verteilten Konsenses mit einem fehlerhaften Prozess (JACM85) das Unmöglichkeitsergebnis eines Konsenses selbst mit nur einem Prozessabsturz bewiesen:

Das Konsensproblem betrifft ein asynchrones Prozesssystem, von dem einige möglicherweise unzuverlässig sind. Das Problem besteht darin, dass sich die zuverlässigen Prozesse auf einen Binärwert einigen. In diesem Artikel wird gezeigt, dass jedes Protokoll für dieses Problem die Möglichkeit einer Nichtbeendigung aufweist, selbst bei nur einem fehlerhaften Prozess.

Können wir daher zu folgendem Schluss kommen:

Konsens ist stärker als Linearisierbarkeit?

Was ist falsch an meinen Argumenten? Gibt es einige direkte Referenzen für die Äquivalenzschlussfolgerung ?

Hengxin
quelle
1
Bei weitem kein Experte für verteiltes Rechnen, aber es scheint mir, dass der Grund, warum Sie Ihr Ergebnis ableiten können, in den Annahmen liegt, die in den Ergebnissen in der JACM85-Referenz getroffen wurden. Die Linearisierbarkeit entspricht möglicherweise dem Konsens über ein bestimmtes Berechnungsmodell. Dies ist jedoch möglicherweise nicht der Fall, wenn wir unser Berechnungsmodell stark einschränken.
Chazisop

Antworten:

4

Was Sie falsch machen, ist: "Wir wissen, dass Linearisierbarkeit im asynchronen Nachrichtenübermittlungssystem erreicht werden kann, während eine Minderheit von Prozessabstürzen toleriert wird." Wir wissen das nicht und tatsächlich ist es falsch.

Das Zitat aus dem JACM95-Papier zeigt, dass Single-Writer-Multi-Reader-Register mithilfe der Nachrichtenübermittlung implementiert werden können. Und nur diese Art von Registern oder andere Objekte, die aus solchen Registern implementiert werden können (bei einer geringen Anzahl von Abstürzen). Dies umfasst beispielsweise Multi-Writer-Multi-Reader-Register (MWMR).

Im Gegensatz dazu ist die Linearisierbarkeit nicht auf Objekte beschränkt, die unter Verwendung von Einzelleser-Mehrleserregistern implementiert werden können. Ein Beispiel für solche Objekte sind solche, die (atomare) Lese-, Änderungs- und Schreiboperationen unterstützen.

Wie Attiya et al. (Abschnitt 7) hervorheben, können solche Objekte von MWMR-Registern nicht genau implementiert werden, da sie eine Konsenslösung ermöglichen (vgl. Wartefreie Synchronisation durch Herlihy) und somit die Implementierbarkeit dem FLP-Ergebnis widersprechen würde.

Martin B.
quelle
Entschuldigung für die Verspätung. 1. Da die Linearisierbarkeit eine lokale Eigenschaft ist , denke ich nicht, dass die Anzahl der betroffenen Objekte der Punkt ist. Könnten Sie bitte weiter erklären? 2. Was ist deine Bedeutung der Verwendung von „dh“ beziehen atomicity of operations on a single objectmit sequential specifications are not violated?
Hengxin
Wahr. Lassen Sie mich noch einmal darüber nachdenken ...
Martin B.
Ich habe die Antwort komplett umgeschrieben ... Ich denke jetzt macht es Sinn. Ich erinnere mich nicht, was ich vorher gedacht habe.
Martin B.
Ich denke, Ihr aktuelles Argument macht Sinn. Nach Ihrer Antwort überprüfte ich das Papier Eventually Linearizable Shared Objects (PODC'10)und stellte fest, dass beliebige Objekte (anstelle von nur SWMR-Registern) berücksichtigt wurden.
Hengxin
Vielen Dank für Ihre Aufmerksamkeit und Bemühungen. Arbeiten Sie an der Theorie des verteilten Rechnens / der Parallelität? Würde es Ihnen dann etwas ausmachen, mein anderes Problem zu bewerten : Atomic Snapshot-Algorithmen für baumstrukturierte gemeinsam genutzte Register ? Denken Sie, dass es ein Problem ist, das es wert ist, studiert zu werden?
Hengxin