Prozessorausfälle bei verteilten Computern, die nicht abstürzen oder byzantinisch sind

13

Es gibt zwei Haupttypen von Prozessorausfällen in verteilten Computermodellen:

(1) Absturzfehler: Ein Prozessor stoppt und startet nie wieder. (2) Byzantinische Ausfälle: Prozessoren verhalten sich widersprüchlich und böswillig.

Meine Frage ist:

Welche anderen Arten von Prozessorausfällen wurden untersucht, die sich nicht auf Abstürze oder byzantinische Ausfälle reduzieren lassen?

Auch eine genauere Frage:

Wurde ein Modell untersucht, bei dem mit einiger Wahrscheinlichkeit ein Prozess zum Zeitpunkt $t$ und ansonsten ausgeschaltet ist? Also blinkt jeder Prozess sozusagen ein und aus.

Am meisten interessiert mich, wie diese Misserfolge mit Konsensproblemen und anderen Problemen mit verteilten Vereinbarungen zusammenhängen.

Vielen Dank.

reference-request dc.distributed-comp Aaron Sterling
quelle

@Aaron: Ich hatte vor einigen Jahren einen Kurs über "verteilte Systeme" und einen weiteren über "fehlertolerante Systeme", aber ich beschäftige mich nicht wirklich mit diesen Themen. Dennoch denke ich, dass das dynamische Fehlermodell des Schlüsselworts Ihnen helfen kann.

MS Dousti

1

Ich vermute, das im Bereich der Selbststabilisierung verwendete Fehlermodell reduziert sich nicht auf Absturzfehler oder byzantinische Fehler. Eine Möglichkeit, dies mit byzantinischen Fehlern in Verbindung zu bringen: Sie können ein vorübergehendes byzantinisches Verhalten haben, aber wenn ein solches Verhalten aufhört, muss ein sich selbst stabilisierendes System einen korrekten Zustand erreichen.

Jukka Suomela

1

Zu Ihrer genaueren Frage: Wenn ein Prozessor mit der Wahrscheinlichkeit

"ein" ist , klingt dies für mich sehr nach einem asynchronen Modell, bei dem Prozessoren immer eingeschaltet sind, Nachrichten jedoch beispielsweise

Runden benötigen, um ihr Ziel zu erreichen. Könnten Sie vielleicht klarstellen, inwiefern dies von dem Modell abweicht, an das Sie gedacht haben?

p

$p$

1 / p

$1/p$

Jukka Suomela

1

@ Aaron: Ich weiß nicht wirklich, wie viel diese Art von Modellen untersucht wurden. Wenn Sie jedoch einen deterministischen synchronen Algorithmus

mit der Laufzeit

, können Sie einfach den

Synchronisierer verwenden, um

im asynchronen Modell zu simulieren , und die erwartete Laufzeit würde ungefähr

betragen . (Der

Synchronisierer garantiert lediglich, dass Ihre Nachbarn in der Simulation von

niemals mehr als einen Zeitschritt vor oder hinter Ihnen sind .)

A

$A$

T

$T$

α

$\alpha$

A

$A$

T / p

$T/p$

α

$\alpha$

A

$A$

Jukka Suomela

2

@Aaron: Ich habe mit Michel Raynal die Theorie des Distributed Computing übernommen und er hat ein drittes Modell beschrieben, bei dem Nachrichten zufällig abgelegt werden können. In diesem Modell kann es vorkommen, dass eine Nachricht im Hintergrund nicht zugestellt wird. Dies bedeutet jedoch nicht unbedingt, dass der Knoten ausgefallen ist. Es geht eher um Verbindungsausfälle als um Knotenausfälle "fair lossy channel model". Weitere Informationen finden Sie hier: Ruhender, einheitlicher und zuverlässiger Broadcast als Einführungsumfrage zu Orakeln mit Ausfalldetektoren - Michel Raynal ( ftp.irisa.fr/techreports/2000/ PI-1356.ps.gz )

M. Alaggan

12

Kopiert aus den Kommentaren zur Frage nach Anfrage.

Ich habe mit Michel Raynal die Theorie des verteilten Rechnens übernommen und er beschrieb ein drittes Modell, bei dem Nachrichten zufällig abgelegt werden können. In diesem Modell kann es vorkommen, dass eine Nachricht im Hintergrund nicht zugestellt wird. Dies bedeutet jedoch nicht unbedingt, dass der Knoten ausgefallen ist. Es geht eher um Verbindungsausfälle als um Knotenausfälle "fair lossy channel model". Weitere Informationen finden Sie hier: Ruhender, einheitlicher und zuverlässiger Broadcast als Einführungsumfrage zu Orakeln mit Ausfalldetektoren - Michel Raynal (ftp.irisa.fr/techreports/2000/ PI-1356.ps.gz)

M. Alaggan
quelle

10

Aufgrund der mit der byzantinischen Fehlertoleranz verbundenen hohen Ressourcenkosten wurden natürlich Fehlermodelle mit immer strengeren Annahmen analysiert, insbesondere im Hinblick auf den Ressourcenbedarf, um Fehler von eingeschränktem Typ zu tolerieren. ( Azadmanesh und Kieckhafer, 2002 ) liefern eine sehr schöne Taxonomie (siehe Abb. 1).

Die Art des Fehlermodus zwischen vollständig asymmetrischem byzantinischem Verhalten ( Knoten erforderlich ) und gutartigen Absturzfehlern ( Knoten), die Sie suchen und die bereits von anderen oben erwähnt wurden, ist die Klasse von Symmetrische (omissive) Fehler , bei denen von einigen Empfängern keine Nachrichten empfangen werden, aber von keinem Knoten jemals eine wertfehlerhafte (gegnerische) Nachricht empfangen wird, für die nur Knoten erforderlich sind, um Fehler zu tolerieren . Das obige Papier fasst auch die Ressourcenanforderungen für gemischte Szenarien zusammen. $3f+1$ $f+1$ $2f+1$ $f$

Eine andere Möglichkeit, Annahmen zum Fehlermodus zu modellieren, besteht darin, sich von der knotenzentrierten Sichtweise zu entfernen, bei der der Nachrichtenverlust als Fehler des Absenders modelliert wird, und das Verbindungsfehlermodell zu verwenden, bei dem es sich nur um eine doppelte Sichtweise handelt, sobald die Inkonsistenzen vorliegen, die sie verursachen können das System berücksichtigt werden. Dieses Modell wurde von ( Schmid, Weiss und Rushby, 2002 ) untersucht, wobei ein Unmöglichkeitsergebnis von ( Gray, 1978 ) umgangen wurde , das eine deterministische Lösung des Coordinated Attack-Problems unter Verbindungsfehlern zeigt.

Martin Schwarz
quelle

8

Ich weiß nicht, ob @M. Alaggan sprach über diese Art von Fehlern, aber sie sehen auf jeden Fall ähnlich aus: vorübergehende Fehler.

In dem Modell der DVFS , wo man die Frequenz und Spannung ändern , um den Energieverbrauch zu reduzieren, und Zhu Aydin in diesem Papier (PDF) verwendet , um ein Fehlermodell für DVFS. Sie berücksichtigen vorübergehende Ausfälle, die beispielsweise durch Softwarefehler verursacht werden. Sie machen nur die Ausführung der aktuellen Aufgabe ungültig, und der von diesem Fehler betroffene Prozessor kann die ihm zugewiesene nachfolgende Aufgabe (falls vorhanden) wiederherstellen und ausführen.

$\lambda$

λ (f) = λ_{p} e^{d \frac{f_{m a x} - f}{f_{m a x} - f_{m i n}}},

$\begin{equation} \label{fault} \lambda(f)=\lambda_p \; e^{d\frac{f_{max}-f}{f_{max}-f_{min}}}, \end{equation}$

f_{m i n} \leq f \leq f_{m a x}

$f_{min}\leq f \leq f_{max}$

d \geq 0

$d\geq0$

λ_{p}

$\lambda_p$

f_{m a x}

$f_{max}$

p

$p$

T_{i}

$T_i$

p

$p$

f_{i}

$f_i$

R_{i} (f_{i}) = e^{- λ (f_{i}) \times E x e c u t i o n T i m e (T_{i}, f_{i})} .

$R_i(f_i)=e^{-\lambda(f_i)\times Execution~Time(T_i,f_i)}.$

Es tut mir leid, dies so lange nach dem ursprünglichen Beitrag zu posten, aber ich fand diese Frage, als ich an diesem Thema arbeitete :). Wenn Sie DVFS nicht studieren, sind diese Fehler immer noch vorhanden. Die Formeln sind wahrscheinlich immer noch gültig (oder anpassbar). Weitere Informationen zu vorübergehenden Ausfällen ohne DVFS finden Sie hier .

Gopi
quelle

4

Bezüglich der bereits erwähnten Auslassungsversagermodelle schauen Sie sich NeigerToueg an , das verschiedene Arten von solchen berücksichtigt.

Wurde ein Modell untersucht, bei dem mit einiger Wahrscheinlichkeit ein Prozess zum Zeitpunkt t ein- und ansonsten ausgeschaltet ist? Also blinkt jeder Prozess sozusagen ein und aus.

Das klingt nach einem Crash-Recovery-Modell. Mir ist kein Modell bekannt, bei dem Prozesse wahrscheinlich ein- oder ausgeschaltet sind. Es gibt auch Varianten, bei denen Prozesse für einige Zeit byzantinisch sind und sich dann erholen, wobei im Laufe der Zeit alle Prozesse byzantinisch sein können (meistens jedoch für die Taktsynchronisierung).

Beachten Sie, dass, wenn Sie mit "aus" meinen, dass ein Prozess nur keinen Fortschritt macht (er verliert seinen Status nicht und Nachrichten gehen nicht verloren, weil der Empfänger "aus" ist), das, was Sie sich ansehen, als asynchron bezeichnet wird System. Im Shared-Memory-Kontext könnte Ihre Frage dann in engem Zusammenhang mit diesem Aspnes- Papier stehen.

Martin B.
quelle

1

Es könnte andere Arten von Fehlern geben. Beispielsweise könnten einige Prozessoren (z. B. unter Broadcast- oder Multicast-Protokollen) überlastet werden und könnten nicht alle eingehenden Nachrichten verarbeiten. Dies führt dazu, dass der Prozessor für einige Prozessoren im verteilten System als offline angezeigt wird.

Mohammad Al-Turkistany
quelle

Prozessorausfälle bei verteilten Computern, die nicht abstürzen oder byzantinisch sind

Antworten: