Timing- und Fehlermodelle

Timing- und Fehlermodelle legen fest, welche Annahmen ein verteiltes Algorithmus über Nachrichtenverzögerungen und Prozessorgeschwindigkeiten treffen darf und wie Komponenten ausfallen dürfen.

Definition

Ein Timing-Modell legt die Annahmen über Obergrenzen für die Nachrichtenübertragungszeit und die relative Prozessgeschwindigkeit fest, während ein Fehlermodell die Menge der Arten festlegt, in denen Prozesse und Kanäle von ihrem spezifizierten Verhalten abweichen können.

Scope

Dieses Thema behandelt die synchronen, asynchronen und partiell synchronen Timing-Modelle; die Taxonomie von Fehlern, die von Abstürzen (Fail-Stop) über Auslassungen und Timing-Fehler bis hin zu beliebigen (Byzantinischen) Fehlern reichen; und die Abstraktion von Fehlerdetektoren, die asynchrone Systeme und Timeout-basiertes Denken miteinander verbindet. Diese Modelle sind die Axiome, aus denen sowohl Möglichkeits- als auch Unmöglichkeitsergebnisse abgeleitet werden.

Core questions

• Welche Grenzen für Verzögerung und Geschwindigkeit darf ein Algorithmus annehmen, und wie hängen Timeouts davon ab?
• Welche Fehlerklassen – Absturz, Auslassung, Timing, Byzantinisch – muss ein Protokoll maskieren?
• Wie können asynchrone Systeme mit Fehlerdetektoren erweitert werden, um Unmöglichkeitsergebnisse zu umgehen?

Key theories

Partielle Synchronität

Reale Systeme sind weder vollständig synchron noch vollständig asynchron; das partiell synchrone Modell nimmt Grenzen für Verzögerung und Geschwindigkeit an, die eventuell gelten oder unbekannt sind, was ausreicht, um Konsens zu lösen und dabei realistisch zu bleiben.

Fehlermodell-Hierarchie

Fehler reichen von gutartigen Fail-Stop-Abstürzen über Sende-/Empfangs-Auslassungen und Timing-Verletzungen bis hin zu willkürlichem Byzantinischem Verhalten; die Schwere der Fehler, die ein Protokoll tolerieren muss, bestimmt den erforderlichen Replikationsfaktor und die Nachrichtenkomplexität.

Unzuverlässige Fehlerdetektoren

Ein abstrakter Fehlerdetektor liefert möglicherweise inkorrekte Hinweise darüber, welche Prozesse abgestürzt sind; die Charakterisierung des schwächsten Detektors, der ausreicht, um Konsens zu lösen, versöhnt asynchrone Strenge mit praktischen Timeout-basierten Implementierungen.

Clinical relevance

Produktionssysteme wählen implizit ein Timing- und Fehlermodell, wenn sie Timeouts festlegen, einen Replikationsfaktor wählen oder entscheiden, ob sie sich gegen böswillige Teilnehmer verteidigen; falsche Annahmen sind eine häufige Ursache für Split-Brain- und Datenverlust-Vorfälle.

History

Nachdem sich das asynchrone Modell als zu schwach für fehlertoleranten Konsens erwiesen hatte, führten Dwork, Lynch und Stockmeyer 1988 die partielle Synchronität ein, und Chandra und Toueg formalisierten 1996 unzuverlässige Fehlerdetektoren, die zusammen die Modellierungswerkzeuge bereitstellten, die eine praktische fehlertolerante Einigung ermöglichen.

Debates

Sind Timeouts eine Timing-Annahme oder ein Fehlerdetektor?

Eine Ansicht behandelt Timeouts als Kodierung einer (eventuellen) Synchronitätsgrenze; eine andere behandelt sie als Implementierung eines abstrakten Fehlerdetektors. Die beiden Rahmen sind weitgehend äquivalent, betonen aber unterschiedliche Designgrenzen zwischen dem Netzwerkmodell und dem Algorithmus.

Key figures

• Cynthia Dwork
• Nancy Lynch
• Larry Stockmeyer
• Tushar Chandra
• Sam Toueg

Seminal works

• dwork1988
• chandra1996
• lynch1996

Frequently asked questions

Warum kann eine zuverlässige Fehlererkennung in einem rein asynchronen System nicht implementiert werden?

Ohne Grenzen für die Nachrichtenverzögerung ist ein beliebig langsamer, aber lebendiger Prozess nicht von einem abgestürzten zu unterscheiden, sodass jeder Detektor manchmal falsch liegen muss. Aus diesem Grund werden asynchrone Systeme mit Timing-Annahmen oder unzuverlässigen Detektoren erweitert.