Verteilter wechselseitiger Ausschluss und Leader-Wahl

Wechselseitiger Ausschluss (Mutual Exclusion) und Leader-Wahl sind klassische Koordinationsprobleme: Sicherstellen, dass höchstens ein Prozess auf eine kritische Ressource zugreift, und Auswählen eines einzelnen, ausgezeichneten Koordinators unter gleichrangigen Prozessen.

Definition

Verteilter wechselseitiger Ausschluss garantiert, dass höchstens ein Prozess gleichzeitig eine gemeinsam genutzte Ressource hält, während gleichzeitig der eventuelle Zugriff für alle Anfragenden sichergestellt wird; die Leader-Wahl wählt deterministisch genau einen Prozess als Koordinator aus, wobei alle Prozesse dem Ergebnis zustimmen.

Scope

Dieses Thema behandelt genehmigungsbasierte Algorithmen für den wechselseitigen Ausschluss (Lamports Zeitstempel-Algorithmus, Ricart-Agrawala, Maekawas Quorum-Ansatz) und tokenbasierte Algorithmen, zusammen mit ihrer Nachrichtenkomplexität und Fairness-Eigenschaften; sowie Leader-Wahl-Algorithmen für Ringe (Chang-Roberts) und allgemeine Netzwerke (der Bully-Algorithmus), einschließlich ihrer Annahmen über Identifikatoren und Synchronität. Diese Primitive wiederholen sich in Koordinationsdiensten und replizierten Systemen.

Core questions

• Wie können Prozesse den Zugriff auf eine gemeinsam genutzte Ressource nur über Nachrichten serialisieren?
• Welche Kompromisse gibt es hinsichtlich Nachrichtenkomplexität und Fairness zwischen genehmigungsbasierten und tokenbasierten Schemata?
• Wie wird ein eindeutiger Leader gewählt, und wie wird die Wahl nach dem Ausfall des Leaders erneut ausgelöst?

Key theories

Genehmigungsbasierter wechselseitiger Ausschluss

Algorithmen wie Ricart-Agrawala ordnen Anfragen nach logischen Zeitstempeln und gewähren den Eintritt, sobald ein Anfragender die Erlaubnis von allen (oder einem Quorum von) Peers erhalten hat, wodurch Fairness mit begrenzten Nachrichtenkosten pro Eintritt in den kritischen Abschnitt erreicht wird.

Tokenbasierter wechselseitiger Ausschluss

Ein eindeutiger Token zirkuliert oder wird bei Bedarf angefordert, und nur sein Inhaber darf den kritischen Abschnitt betreten, was den Nachrichtenverkehr reduziert, aber Mechanismen zur Wiederherstellung eines verlorenen Tokens nach Ausfällen erfordert.

Leader-Wahl

Wahlalgorithmen wie Chang-Roberts für Ringe und der Bully-Algorithmus für allgemeine Netzwerke verwenden Prozessidentifikatoren, um auf einen einzigen Koordinator mit der höchsten Priorität zu konvergieren, den alle korrekten Prozesse erkennen.

Clinical relevance

Die Leader-Wahl wird immer dann aufgerufen, wenn ein repliziertes System einen primären oder Koordinator auswählen muss, und verteiltes Sperren verallgemeinert den wechselseitigen Ausschluss; beides wird als Kerndienste von Koordinationssystemen, die in der gesamten Cloud-Infrastruktur verwendet werden, bereitgestellt.

History

Lamports Arbeit über logische Uhren aus dem Jahr 1978 führte einen zeitstempelbasierten Algorithmus für den wechselseitigen Ausschluss ein; Ricart und Agrawala optimierten ihn 1981, Maekawa führte kurz darauf Quoren ein, und Garcia-Molinas Bully-Algorithmus von 1982 formalisierte die Leader-Wahl und lieferte dem Feld seine kanonischen Koordinationsalgorithmen.

Key figures

• Leslie Lamport
• Glenn Ricart
• Ashok Agrawala
• Hector Garcia-Molina

Seminal works

• ricart1981
• garcia-molina1982
• lynch1996

Frequently asked questions

Wie unterscheidet sich der verteilte wechselseitige Ausschluss von einer Sperre auf einem einzelnen Rechner?

Es gibt keinen gemeinsamen Speicher oder zentralen Sperrverwalter, auf den man sich verlassen kann, daher müssen sich die Prozesse ausschließlich durch den Austausch von Nachrichten koordinieren und Nachrichtenverzögerungen und Ausfälle explizit behandeln, was eine Sperre auf einem einzelnen Rechner als selbstverständlich annehmen kann.