Verteilter Algorithmus - Distributed algorithm

Ein verteilter Algorithmus ist ein Algorithmus , der auf Computerhardware ausgeführt werden soll, die aus miteinander verbundenen Prozessoren besteht . Verteilte Algorithmen werden in verschiedenen Anwendungsbereichen des verteilten Rechnens verwendet , wie beispielsweise Telekommunikation , wissenschaftliches Rechnen , verteilte Informationsverarbeitung und Echtzeit- Prozesssteuerung . Zu den Standardproblemen, die durch verteilte Algorithmen gelöst werden, gehören die Wahl des Führers , der Konsens , die verteilte Suche , die Spanning-Tree- Generierung, der gegenseitige Ausschluss und die Ressourcenzuweisung .

Verteilte Algorithmen sind ein Untertyp von parallelen Algorithmen , die normalerweise gleichzeitig ausgeführt werden , wobei separate Teile des Algorithmus gleichzeitig auf unabhängigen Prozessoren ausgeführt werden und begrenzte Informationen darüber haben, was die anderen Teile des Algorithmus tun. Eine der größten Herausforderungen bei der Entwicklung und Implementierung verteilter Algorithmen besteht darin, das Verhalten der unabhängigen Teile des Algorithmus bei Prozessorausfällen und unzuverlässigen Kommunikationsverbindungen erfolgreich zu koordinieren. Die Wahl eines geeigneten verteilten Algorithmus zur Lösung eines gegebenen Problems hängt sowohl von den Merkmalen des Problems als auch von den Merkmalen des Systems ab, auf dem der Algorithmus ausgeführt wird, wie Art und Wahrscheinlichkeit von Prozessor- oder Verbindungsausfällen, Art der Kommunikation zwischen den Prozessen die durchgeführt werden können, und das Niveau der Zeitsynchronisation zwischen getrennten Prozessen.

Standardprobleme

Atomares Commit

Ein atomarer Commit ist eine Operation, bei der eine Reihe von unterschiedlichen Änderungen als eine einzige Operation angewendet wird. Wenn der atomare Commit erfolgreich ist, bedeutet dies, dass alle Änderungen übernommen wurden. Wenn ein Fehler auftritt, bevor der atomare Commit abgeschlossen werden kann, wird der "Commit" abgebrochen und es werden keine Änderungen übernommen.

Algorithmen zum Lösen des Atomic-Commit-Protokolls umfassen das Two-Phase-Commit-Protokoll und das Drei-Phasen-Commit-Protokoll .

Konsens

Konsensalgorithmen versuchen, das Problem zu lösen, dass sich mehrere Prozesse auf eine gemeinsame Entscheidung einigen.

Genauer gesagt muss ein Konsensprotokoll die folgenden vier formalen Eigenschaften erfüllen.

• Beendigung : Jeder korrekte Prozess entscheidet über einen Wert.
• Gültigkeit : Wenn alle Prozesse den gleichen Wert vorschlagen , dann entscheidet jeder richtige Prozess .${\displaystyle v}$${\displaystyle v}$
• Integrität : Jeder richtige Prozess entscheidet höchstens über einen Wert, und wenn er über einen Wert entscheidet , muss er von einem Prozess vorgeschlagen worden sein.${\displaystyle v}$${\displaystyle v}$
• Übereinstimmung : Wenn ein richtiger Prozess entscheidet , dann entscheidet jeder richtige Prozess .${\displaystyle v}$${\displaystyle v}$

Übliche Algorithmen zur Lösung von Konsens sind der Paxos-Algorithmus und der Raft-Algorithmus .

Verteilte Suche

Wahl des Leiters

Die Leader-Wahl ist der Prozess, bei dem ein einzelner Prozess als Organisator einer Aufgabe bestimmt wird, die auf mehrere Computer (Knoten) verteilt ist. Bevor die Aufgabe begonnen wird, wissen alle Netzwerkknoten nicht, welcher Knoten als "Leiter" oder Koordinator der Aufgabe dienen wird. Nachdem jedoch ein Leiterwahlalgorithmus ausgeführt wurde, erkennt jeder Knoten im gesamten Netzwerk einen bestimmten, einzigartigen Knoten als den Aufgabenleiter.

Gegenseitiger Ausschluss

Nicht blockierende Datenstrukturen

Zuverlässige Übertragung

Zuverlässiger Broadcast ist ein Kommunikationsprimitiv in verteilten Systemen. Ein zuverlässiger Broadcast wird durch die folgenden Eigenschaften definiert:

• Gültigkeit – Wenn ein korrekter Prozess eine Nachricht sendet, wird schließlich ein korrekter Prozess diese Nachricht übermitteln.
• Vereinbarung – Wenn ein korrekter Prozess eine Nachricht übermittelt, liefern alle korrekten Prozesse schließlich diese Nachricht.
• Integrität – jeder korrekte Prozess liefert die gleiche Nachricht höchstens einmal und nur dann, wenn diese Nachricht von einem Prozess gesendet wurde.

Eine zuverlässige Sendung kann eine sequentielle, kausale oder totale Ordnung haben.

Reproduzieren

Ressourcenzuweisung

Spanning-Tree- Generierung

Symmetriebrechung, zB Scheitelpunktfärbung

Verweise

Weiterlesen

• Christian Cachin; Rachid Guerraoui; Luís Rodrigues (2011), Einführung in die zuverlässige und sichere verteilte Programmierung (2. Aufl.), Springer, ISBN 978-3-642-15259-7
• C. Rodríguez, M. Villagra und B. Barán, Asynchronous team algorithms for Boolean Satisfiability , Bionetics2007, S. 66–69, 2007.

Externe Links

• Medien im Zusammenhang mit verteilten Algorithmen bei Wikimedia Commons
• MIT Open Courseware - Verteilte Algorithmen