vs4.2 1

4.2 Gruppenkommunikation(group communication)

Bedeutet: Sendeoperation bezieht sich auf mehrere Adressaten- die Mitglieder einer Prozessgruppe (process group)

Rundruf, Rundsendung, Rundmeldung(multicast; an alle Prozesse: broadcast)(Gegenteil: unicast)

Motivation: - Replikation von Code und/oder Daten- Auffinden von Objekten im Netz- Informationsdienste- Konferenzsysteme, Kooperationssysteme (CSCW)- . . . . .

vs4.2 2

Klassifikation in verschiedenen Dimensionen:

Adressierung: - benannte Prozeßgruppen: send m to group (mit Operationen zum Betreten/Verlassen einer Gruppe)- ad-hoc-Prozeßgruppen: send m to procset

Offenheit: - geschlossene Gruppe: nur Mitglieder können senden- offene Gruppe: jeder kann senden

Zuverlässigkeit: - keine Garantie, daß jeder die Nachricht erhält- atomar: Nachricht erreicht alle oder keinen- k-zuverlässig: Nachricht erreicht n ≥ k Teilnehmer

Reihenfolge: s.u.

vs4.2 3

Implementierung:

Gruppenverwaltung:- zentralisiert- verteilt

Nachrichtenübertragung:- mit multicast-fähiger Netz-Hardware- mit speziellen Multicast-Protokollen- per Einzeladressierung

vs4.2 4

4.2.1 Ordnung der Nachrichten

In welcher Reihenfolge treffen Rundrufe bei den Empfängern ein?

ungeordnet: keine Anforderung (d.h. nicht notwendig FIFO)

FIFO: mehrere Nachrichten eines Senders kommen in der Reihenfolge ihres Absendens bei allen Empfängern an. (Wie bei Unicast leicht durch Folgenumerierung zu gewährleisten.)

Kausalordnung (causally ordered, virtually synchronous) : FIFO bei allen Nachrichten, die in einer Kausalitätskette gesendet werden.

Totale Ordnung (loosely synchronous) : Nachrichten werden überall in der gleichen Reihenfolge erhalten.

vs4.2 5

Totale Ordnung

impliziert

Kausalordnung

impliziert

FIFO

impliziert

ungeordnet

vs4.2 6

4.2.2 Sicherung der Kausalordnung

Prozess p erhöht in seiner „Vektorzeit“ P vor dem Senden Pp um 1 und heftet dann P als Zeitstempel t an die Nachricht an.

Vor.: Zuverlässige Nachrichtenübertragung (!)

Eine von p bei q eintreffende Nachricht mit Zeitstempel t wird vom Nachrichtensystem solange zurückgestellt (d.h. nicht abgeliefert), bis gilt:

tp = Qp + 1 (garantiert FIFO-Ordnung)und i p: ti ≤ Qi (garantiert Kausalordnung:

alle Nachrichten, die p gesehenhat, hat auch q gesehen)

Beim Abliefern einer Nachricht von p bei q wird Qp um 1 erhöht.

(CBCAST im System ISIS, Birman/Joseph 1987, Cornell Univ.)

vs4.2 7

4.2.3 Sicherung der Totalordnung

durch künstliche Serialisierung unabhängiger Rundrufe

entweder mittels Sequencer, d.i. zusätzliche Station, über die alle Rundrufe vermittelt werden

oder mittels Prozeßring mit kreisender Marke(vgl. Token Ring in Hardware, 4.2.4),die die Sendeberechtigung gibt

Garantiert werden typischerweise zuverlässige totalgeordneteRundrufe auch bei Nachrichtenverlust, evtl. sogar Stationsausfall

vs4.2 8

Struktur des Sequencer-Protokolls:

p: send m to G veranlaßt Senden von (m,G) an Sequencer s (unzuverlässiger Unicast)

s schickt m an alle Mitglieder von G (unzuverlässiger Multicast) Die send-Anweisung ist erst dann abgeschlossen, wenn bei der ausführenden Station die Nachricht m von s zurückkommt.

Details: - Durchnumerierung der Unicasts und Multicasts - Timeout bei den beteiligten Prozessen - Geschichtspuffer beim Sequencer

(Verteiltes Betriebssystem Amoeba, Kaashoek/Tanenbaum 1989)

vs4.2 9

Variante des Protokolls:

- p macht Rundruf direkt, auch an s: (p,n,m)- s reagiert mit Rundruf (p,n,OK,i)- erst mit Erhalt dieser Nachricht ist die erste „offiziell“

Aufwand:

Original: 2 lange Nachrichten, aber nur 1 Multicast

Variante: 2 Multicasts, aber nur eine Nachricht ist lang

Achtung! Diese Verfahren skalieren nicht für große Systeme! Andere Verfahren z.B. für Internet-Multicast.

vs4.2 10

4.2.4 Hardware-unterstützte Rundrufe in Lokalnetzen

Ethernet:

Kollisionsfreie Übertragung (durch Netzsteuerung nach eventuell wiederholten Versuchen sichergestellt) resultiert in Nachrichtenempfang in allen Stationen (einer Gruppe).

Pufferüberlauf wird durch Software verhindert.

Streng serielle Behandlung aller Rundrufe garantiert Totalordnung (sogar „perfect synchrony“ statt nur „virtual/loose synchrony“)

vs4.2 11

Token Ring:

Senden kann nur wer im Besitz einer Marke ist.

Erst wenn die Nachricht wieder beim Sender angekommen ist, wird die Marke weitergereicht, d.h.

Serialität der Rundrufe und damit ebenfalls Totalordnung.

4.2.5 Gruppenkomunikation mit Java

Multicast Sockets: IP Multicast (ohne explizite Gruppen, 2.4.2)

JGroups: + zuverlässige Gruppenkommunikation,Ordnung nach Wunsch FIFO, kausal oder total

String props="UDP:PING:FD:STABLE:NAKACK:UNICAST:" + "FRAG:FLUSH:GMS:VIEW_ENFORCER:STATE_TRANSFER:QUEUE"; Message send_msg; Object recv_msg; Channel channel = new JChannel(props); channel.connect("MyGroup");

send_msg = new Message(null, null, "Hello world"); channel.send(send_msg); recv_msg = channel.receive(0); System.out.println("Received " + recv_msg);

channel.disconnect(); channel.close();

statt Voreinstellung typischerweise "UDP(mcast_addr=...;mcast_port=...)"