Synchronisation2

Question 1

Aus was besteht der Gesamtzustand eines Systems?

Answer 1

• lokalen Zuständen der Einzelkomponenten (deren rozesse) und
• allen Nachrichten, die sich zur Zeit in der Übertragung befinden.

Question 2

Ist es möglich einen globalen Systemzustand exakt zu bestimmen?

Answer 2

Nein, da jeder Prozess seine eigene Uhr hat. So lässt sich kein globaler Zeitpunkt festlegen, an dem alle Prozesse ihre Zustände festhalten sollen.

Question 3

Was ist bei einem verteiltem Schnappschuss zu beachten?

Answer 3

Die Einzelkomponenten dürfen ihre lokalen Schnappschüsse
zu unterschiedlichen Zeitpunkten machen, solange die
Happens-Before-Relationship nicht verletzt ist.

Question 4

Beschreiben sie den Lamport/Chandy-Algorithmus

Answer 4

• Voraussetzung: alle Prozesse sind paarweise über FIFO-Kanäle miteinander verbunden.
• Die Prozesse verständigen sich über Markierungsnachrichten über die Notwendigkeit der Speicherung eines Systemzustands.
• Ein oder mehrere Prozesse starten den Algorithmus, d.h. es können mehrere Schnappschüsse gleichzeitig erstellt werden.
• Das System läuft unterdessen ungehindert weiter.

Question 5

Was macht der initiierende Prozess beim Lamport/Chandy-Algorithmus?

Answer 5

• speichere lokalen Zustand
• starte Aufzeichnungsmodus für alle Eingangskanäle
• sende Markierungen in alle Ausgangskanäle

Question 6

Was passiert wenn ein Prozess eine Markierung beim Lamport/Chandy-Algorithmus bekommt? (NICHT im Aufzeichnungsmodus)

Answer 6

• speichere lokalen Zustand von Pi
• speichere den Zustand von c als leere Liste
• starte Aufzeichnungsmodus für alle anderen Eingangskanäle
• sende Markierungen in alle Ausgangskanäle

Question 7

Was passiert wenn ein Prozess eine Markierung beim Lamport/Chandy-Algorithmus bekommt? (im Aufzeichnungsmodus)

Answer 7

• speichere den Zustand von c als die Liste aller im Aufzeichnungsmodus über c eingegangene Nachrichten
• beende Aufzeichnungsmodus für c
• falls keine weiteren Eingangskanäle im Aufzeichnungsmodus, Aufzeichnung des lokalen Schnappschusses vollständig.

Question 8

Beschreiben sie kurz den Bully-Algorithmus

Answer 8

• jeder Prozess kommuniziert mit jedem

- stärkerer Prozess bekommt AUSWAHL-Nachricht von schwächerem→ stärkerer übernimmt Auswahlprozess

Question 9

Beschreiben sie kurz den Ring-Algorithmus

Answer 9

• begrenzte Kommunikation entlang Ring

- erfordert, dass übernächster Nachfolger gefunden werden kann

Question 10

Beschreiben sie kurz die Wahl in Ad-hoc-Netzen

Answer 10

• spannt dynamisch Erreichbarkeitsbaum auf

- hierarchische Auswahl des besten Anführers