Modelle verteilter Systeme

Modelle verteilter Systeme sind die abstrakten Annahmen – über Architektur, Zeitverhalten, Kommunikation und Ausfälle –, die definieren, worauf ein verteilter Algorithmus sich verlassen kann und was er tolerieren muss.

Definition

Ein verteiltes System ist eine Sammlung unabhängiger Computer, die nur durch den Austausch von Nachrichten kommunizieren und ihren Benutzern als ein einziges kohärentes System erscheinen; ein Systemmodell ist die Menge von Annahmen über Prozesse, Kommunikationskanäle, Zeitverhalten und Ausfälle, unter denen ein solches System analysiert wird.

Scope

Dieser Bereich umfasst die architektonischen und physikalischen Modelle verteilter Systeme (Clients, Server, Peers und mehrschichtige Organisationen), die Zeitmodelle, die synchrone von asynchroner Ausführung unterscheiden, die grundlegenden Fehlermodelle (Absturz, Auslassung, Zeitfehler und byzantinisch) sowie die Kommunikationsabstraktionen der Nachrichtenübermittlung, des gemeinsamen Speichers, des Fernaufrufs und der Middleware. Diese Modelle bilden den Rahmen für jedes Ergebnis in diesem Bereich: Ein Algorithmus, der unter einem Modell korrekt ist, kann unter einem anderen unmöglich sein, daher ist die explizite Angabe des Modells eine Voraussetzung für die Argumentation über Korrektheit und Leistung.

Sub-topics

• Nachrichtenübermittlung und gemeinsamer Speicher
• Remote Invocation und Middleware
• System- und Architekturmodelle
• Timing- und Fehlermodelle

Core questions

• Welche Annahmen über Zeitverhalten, Kommunikation und Ausfälle erfordert ein gegebener verteilter Algorithmus?
• Wie unterscheiden sich synchrone und asynchrone Modelle, und warum verändert die Unterscheidung, was berechenbar ist?
• Welche Klassen von Prozess- und Kanalfehlern muss ein Protokoll tolerieren, um korrekt zu sein?
• Wann sollte ein System um Nachrichtenübermittlung im Vergleich zu einer Shared-Memory- oder Remote-Invocation-Abstraktion strukturiert sein?

Key theories

Synchrone versus asynchrone Modelle

In einem synchronen Modell gibt es bekannte Grenzen für Nachrichtenverzögerung und relative Prozessorgeschwindigkeit, was die Verwendung von Timeouts zur Fehlererkennung ermöglicht; in einem asynchronen Modell existieren solche Grenzen nicht, was die Fehlererkennung grundsätzlich unzuverlässig macht und vielen Unmöglichkeitsergebnissen zugrunde liegt.

Hierarchie der Fehlermodelle

Prozess- und Kanalfehler werden von gutartig bis schwerwiegend klassifiziert – Absturz (Fail-Stop), Auslassung, Zeitfehler und willkürlich (Byzantinisch) – wobei stärkere Garantien erforderlich sind, um schwerwiegendere Fehler zu maskieren; das gewählte Modell bestimmt sowohl die erreichbare Ausfallsicherheit als auch die Kosten eines Protokolls.

Kommunikationsabstraktionen

Verteilte Berechnungen basieren auf einer kleinen Menge von Interaktionsprimitiven – asynchrone und synchrone Nachrichtenübermittlung, verteilter gemeinsamer Speicher und Remote Procedure oder Method Invocation – jede mit unterschiedlichen Semantiken für Zustellung, Reihenfolge und Fehler, die das Design auf höherer Ebene prägen.

Clinical relevance

Die Wahl des richtigen Modells ist die erste Designentscheidung in jedem realen System: Cloud-Plattformen, Datenbanken und Koordinationsdienste deklarieren alle ein (oft teilweise synchrones) Zeitmodell und ein Fehlermodell, und diese Entscheidungen bestimmen, welche Konsistenz-, Verfügbarkeits- und Fehlertoleranzgarantien das System versprechen kann.

History

Die frühe Forschung zu verteilten Systemen in den 1970er und 1980er Jahren zielte darauf ab, die minimalen Annahmen zu identifizieren, unter denen verteilte Koordination möglich ist, und führte zur synchronen/asynchronen Dichotomie und einer Taxonomie von Fehlern. Diese Modelle wurden in Lehrbüchern von Lynch, Attiya und Welch, Tanenbaum und van Steen sowie Coulouris und Kollegen konsolidiert und wurden zum gemeinsamen Vokabular für das gesamte Fachgebiet.

Debates

Wie realistisch ist das asynchrone Modell für praktische Systeme?

Das reine asynchrone Modell ist nachweislich am schwierigsten zu programmieren und schließt eine zuverlässige Fehlererkennung aus, doch die meisten realen Netzwerke sind nur zeitweise langsam; teilweise synchrone Modelle und Fehlerdetektoren entwickelten sich als pragmatischer Mittelweg, der Strenge bewahrt und gleichzeitig Timeouts zulässt.

Key figures

• Leslie Lamport
• Nancy Lynch
• Andrew S. Tanenbaum
• Maarten van Steen

Seminal works

• lynch1996
• tanenbaum2017
• attiya2004

Frequently asked questions

Warum ist das Zeitmodell so wichtig?

Weil es bestimmt, ob Timeouts vertrauenswürdig sind. In einem synchronen Modell ermöglichen begrenzte Verzögerungen einem Prozess, sicher zu schließen, dass ein stiller Peer ausgefallen ist; in einem asynchronen Modell sind ein langsamer Prozess und ein abgestürzter ununterscheidbar, was die Ursache für mehrere berühmte Unmöglichkeitsergebnisse ist.

Was ist ein byzantinischer Fehler?

Ein byzantinischer (willkürlicher) Fehler ist ein Fehler, bei dem eine fehlerhafte Komponente sich auf jede beliebige Weise verhalten kann, einschließlich des Sendens widersprüchlicher oder bösartiger Nachrichten. Das Tolerieren solcher Fehler ist weitaus kostspieliger als das Tolerieren einfacher Abstürze und erfordert spezielle Konsensprotokolle.