Nachrichtenreihenfolge und Multicast

Gruppenkommunikation liefert eine Nachricht an eine Reihe von Prozessen mit spezifischen Zuverlässigkeits- und Ordnungsgarantien, die von FIFO über kausale bis hin zu totaler Ordnung reichen.

Definition

Multicast liefert eine einzelne Nachricht an jedes Mitglied einer Prozessgruppe; Ordnungsgarantien beschränken die relative Zustellungsreihenfolge von Nachrichten, wobei FIFO die Reihenfolge pro Sender beibehält, kausal die 'happened-before'-Ordnung bewahrt und die totale Ordnung alle Nachrichten in derselben Sequenz an jedes Mitglied liefert.

Scope

Dieses Thema behandelt zuverlässiges Multicast und die Hierarchie der Zustellungsreihenfolgen – FIFO, kausal und total (atomar) – deren Implementierungen unter Verwendung von Sequenznummern, logischen Uhren und Sequenzer- oder Token-Schemata sowie das Virtual-Synchrony-Modell, das geordnetes Multicast mit konsistenten Gruppenmitgliedschaftsänderungen integriert. Es wird gezeigt, dass die totale (atomare) Broadcast-Ordnung in ihrer Leistungsfähigkeit dem Konsens entspricht.

Core questions

• Welche Zuverlässigkeits- und Ordnungsgarantien benötigt eine Anwendung von der Gruppenkommunikation?
• Wie werden kausale und totale Zustellungsreihenfolgen effizient implementiert?
• Warum ist der Total-Order-Broadcast äquivalent zum Konsens?

Key theories

Ordnungshierarchie

Zustellungsreihenfolgen bilden eine Hierarchie – FIFO ist schwächer als kausal, was wiederum schwächer ist als die totale Ordnung – jede wird durch zusätzliche Metadaten wie Sequenznummern pro Sender, Vektor-Zeitstempel oder eine global vereinbarte Sequenz erzwungen.

Virtuelle Synchronität

Virtuelle Synchronität präsentiert Änderungen der Gruppenmitgliedschaft und Multicast-Nachrichten in einer konsistenten Reihenfolge für alle Mitglieder, sodass Prozesse dieselbe Abfolge von Ereignissen und Ansichtsänderungen sehen, was den Aufbau replizierter Dienste vereinfacht.

Atomarer Broadcast gleich Konsens

Total-Order (atomarer) Broadcast und Konsens sind aufeinander reduzierbar, sodass jede Lösung für das eine eine Lösung für das andere liefert und beide dieselben Lösbarkeitsgrenzen unter Asynchronität und Fehlern teilen.

Clinical relevance

Geordnetes, zuverlässiges Multicast ist die Grundlage für State-Machine-Replikation, Publish-Subscribe-Systeme und replizierte Datenbanken, bei denen jede Replik dieselben Aktualisierungen in derselben Reihenfolge anwenden muss, um konsistent zu bleiben.

History

Birman und Joseph führten in den 1980er Jahren mit dem ISIS-System die virtuelle Synchronität und geordnetes Multicast ein; die Beziehung zwischen atomarem Broadcast und Konsens wurde in den 1990er Jahren geklärt, und Defago, Schiper und Urbans Übersicht von 2004 systematisierte die vielen Algorithmen für die totale Ordnung.

Key figures

• Kenneth Birman
• Thomas Joseph
• Andre Schiper
• Leslie Lamport

Seminal works

• birman1987
• defago2004
• lamport1978

Frequently asked questions

Was ist der Unterschied zwischen kausaler und totaler Ordnung?

Die kausale Ordnung beschränkt nur Nachrichten, die kausal miteinander verbunden sind, und lässt gleichzeitige Nachrichten frei, in unterschiedlichen Reihenfolgen an verschiedenen Prozessen zugestellt zu werden. Die totale Ordnung erfordert, dass jeder Prozess alle Nachrichten in der identischen Sequenz zustellt, was strenger ist und so schwierig wie Konsens.