Verteiltes System

Wesen und Einordnung

Ein verteiltes System ist ein Zusammenschluss unabhängiger Recheneinheiten, die als Knoten bezeichnet werden. Ein Knoten kann ein Gerät (Hardware) oder ein Prozess (Software) sein. Für den Benutzer erscheinen alle Knoten idealerweise als ein einziges Gesamtsystem. Das Teilgebiet der Informatik, das sich mit solchen Systemen und ihren Algorithmen beschäftigt, heißt verteiltes Rechnen oder verteilte Verarbeitung (englisch distributed computing).

Man unterscheidet vor allem drei Formen:

• In einem Client-Server-System greifen viele Clients auf einen oder mehrere Server zu.
• Bei einer verteilten Anwendung wird das verteilte System durch die Programmierung der Anwendung geschaffen.
• Bei einem verteilten Betriebssystem ist das Betriebssystem selbst verteilt. Für Benutzer und Anwendungen bleibt diese Verteilung verborgen.

Gründe für den Einsatz

Verteilte Systeme ermöglichen echte Nebenläufigkeit. Mehrere Prozesse können gleichzeitig ausgeführt werden. Außerdem sind sie meist besser skalierbar als ein einzelner Computer: Durch das Hinzufügen weiterer Rechner lässt sich die Leistungsfähigkeit relativ einfach erhöhen.

Ein weiterer Zweck ist die Bereitstellung entfernter Ressourcen, wie es beispielsweise bei der Wikipedia der Fall ist. Die Ausfallsicherheit kann durch Redundanz steigen. Dabei stellen mehrere Rechner dieselbe Funktionalität bereit, sodass beim Ausfall eines Rechners ein anderer diese Aufgabe übernehmen kann.

Auch wirtschaftliche Gründe spielen eine Rolle. Statt eines teuren Supercomputers können preisgünstige Rechner vernetzt werden. Volunteer-Computing-Projekte wie SETI@home nutzen dafür nicht benötigte Rechenleistung von Einzelplatzrechnern. Nachdem SETI@home im März 2020 sein Ende am 31. März 2020 bekannt gegeben hatte und das Interesse durch die COVID-19-Pandemie gestiegen war, erreichte Folding@home als erstes Computing-System 1 exaFLOPS. Es simulierte Proteinfaltung für Forschungen zu COVID-19 und erreichte am 13. April eine Geschwindigkeit von ca. 2.43 x86 exaFLOPS – einige Male schneller als der vorherige Rekordhalter, der Supercomputer Summit.

Weitere Einsatzgründe sind der Fernzugriff auf Ressourcen wie Drucker, die Kooperation im Rahmen von Computer Supported Cooperative Work und die Lastverteilung.

Transparenz

Für Benutzer und Anwendungen soll die Art der Verteilung nicht relevant und idealerweise nicht erkennbar sein. Ein verteiltes System verhält sich dann transparent, also gleichsam durchsichtig: Der Nutzer hat den Eindruck, mit einem einzigen Gesamtsystem zu arbeiten.

Zentrale Probleme

Ein verteiltes System kann teilweise ausfallen, wenn einzelne Rechner oder Teile des Netzwerks betroffen sind. Deshalb sollte es keinen Single Point of Failure geben, also keine einzelne Komponente, deren Ausfall das gesamte System gefährdet. Mit der Anzahl der beteiligten Prozesse steigt außerdem die Wahrscheinlichkeit eines Fehlverhaltens eines Prozesses.

Teilausfälle sind oft schwer zu erkennen. Heartbeats oder regelmäßiges Anpingen können dabei helfen, sind aber nicht vollständig zuverlässig. Wegen unterschiedlicher Verarbeitungsgeschwindigkeiten entsteht ein besonders starker Nicht-Determinismus. Dadurch werden die Synchronisierung und die Nebenläufigkeitskontrolle anspruchsvoll. Diese Kontrolle ist vor allem für Transaktionen und den Zugriff auf gemeinsame Ressourcen mit Mutexen wichtig. Außerdem können Deadlocks auftreten.

Gesamtzustände, also die Summe der Zustände aller beteiligten Prozesse, und Abläufe lassen sich nachträglich oft nicht vollständig nachvollziehen. Das erschwert die Fehlerdiagnose.

Verteilte Systeme besitzen keinen gemeinsamen Speicher. Sie kommunizieren daher durch das Versenden und Empfangen von Nachrichten. Nachrichten können verfälscht, dupliziert oder verloren werden. Ihre Laufzeit ist unvorhersehbar; eine lange Antwortzeit lässt sich deshalb nicht sicher von einem Systemausfall unterscheiden. Zudem kann die Kommunikation abgehört oder absichtlich manipuliert werden und muss möglicherweise über eine Infrastruktur wie das Internet erfolgen, die nicht vollständig für gruppenbasierte Kommunikation geeignet ist.

Bei komplexen Prozessen wird häufig ein gemeinsamer Zeitbegriff benötigt. Die den Prozessen bekannte Zeit muss dabei nur mit kleinen Abweichungen übereinstimmen. So können verteilte Transaktionen sicherer durchgeführt werden, weil Timeouts verhindern, dass ausgesendete Nachrichten veraltet verwendet werden. Zusätzlich erschwert die verteilte Struktur die zentrale Administration, besonders bei nicht-strukturierten Topologien und bei Millionen unterschiedlich konfigurierter Rechner, die fremden Personen gehören können.

Kommunikationsmodelle

Für verteilte Systeme werden unterschiedliche Kommunikationsmodelle betrachtet:

• Im asynchronen Modell haben Prozesse nur den Zustand aktiv oder passiv. Nur ein aktiver Prozess versendet Nachrichten. Er kann jederzeit passiv werden; ein passiver Prozess kann nur durch eine Nachricht reaktiviert werden.
• Im synchronen Modell haben Nachrichten selbst keine Laufzeit. In der Praxis wird dieses Verhalten durch synchrone Kommunikation erreicht.
• Im Atommodell besitzen Nachrichten zwar eine Laufzeit, Prozesse selbst jedoch keine Laufzeit.

Wichtige Algorithmen

Algorithmen zur Uhren-Synchronisation dienen dazu, Ereignisse zeitlich zu ordnen oder die Uhren verschiedener Prozesse anzugleichen. Logische Uhren messen nicht die physikalische Zeit. Sie vergeben eindeutige Zeitstempel und erzeugen einen monoton steigenden Zeitwert, mit dem die Kausalordnung von Ereignissen erkennbar wird. Beispiele sind der Mittelwert-Algorithmus, logische Zeitstempel nach Lamport und die Vektoruhr. Für die Synchronisation physikalischer Uhren werden unter anderem der Algorithmus von Cristian, der Berkeley-Algorithmus und das Network Time Protocol verwendet.

Broadcastalgorithmen verteilen eine Information im gesamten Netz. Beispiele sind der Flooding-Algorithmus und der Echo-Algorithmus.

Auswahlalgorithmen wählen aus einer Menge identischer Knoten einen eindeutigen Knoten aus. Eine zweite Kategorie bilden Maximumsalgorithmen: Sie wählen aus Knoten mit eindeutiger ID den Knoten mit der größten ID. Genannt werden unter anderem der Bullyalgorithmus, die Nachrichtenauslöschung nach Chang und Roberts, randomisierte Auswahl in bidirektionalen Ringen, die Las-Vegas-Auswahl für anonyme Ringe, der Hirschberg/Sinclair-Auswahlalgorithmus, Wahlalgorithmen auf Bäumen, der Echo-Algorithmus, der Itai-Rodeh-Algorithmus für anonyme unidirektionale Ringe und der Algorithmus von Peterson für Ringe.

Zur Nebenläufigkeitskontrolle gehören Locking- und Mutex-Algorithmen, serverbasierte Mutex, der Token Ring, der Ricart-Agrawala-Algorithmus, der Maekawa-Algorithmus mit Voting-Sets sowie Verfahren für partitionierte Systeme. Verflochtene Synchronisation (Braided Synchronization) ermöglicht atomare Transaktionen über Shards hinweg, indem Konsensinstanzen dynamisch miteinander verknüpft werden.