Der Algorithmus Nachrichtenauslöschung nach Chang und Roberts ist ein Maximal-Algorithmus für verteilte Systeme. Er dient dazu, aus Knoten, die in einem Ring angeordnet sind, den Knoten mit der größten ID auszuwählen. Grundlage ist der Bullyalgorithmus, dessen Nachrichtenkomplexität gesenkt wurde.
Voraussetzungen Bearbeiten
- Topologie: Unidirektionaler Ring
- Eindeutige IDs
Idee Bearbeiten
Solange der maximale Knoten noch nicht bekannt ist, wird jeder Knoten irgendwann zum Initiator und sendet seine ID an seinen Nachbarn. Wenn jemand eine Nachricht empfängt, in der eine ID größer als die eigene gespeichert ist, sendet er die Nachricht weiter. Wenn seine ID größer als die in der Nachricht gespeicherte ist, verschluckt er die Nachricht.
Wenn eine Nachricht einen gesamten Ringdurchlauf schafft, weiß der Initiator, dass er die größte ID hat, und informiert die anderen mit einem weiteren Ringdurchlauf.
Pseudocode Bearbeiten
Initiator
Sende <ID, ID> an nächsten Knoten
Ein Knoten K empfängt (r, max)
wenn ID(K) < max sende <r, max> an nächsten Knoten
wenn r == ID(K) "ICH HABE GEWONNEN" Informiere alle anderen Knoten durch weiteren Ringdurchlauf
Nachrichtenkomplexität Bearbeiten
Worst Case Bearbeiten
Der Worst Case tritt ein, wenn die Knoten nach ihren IDs auf dem Ring sortiert sind und in entgegengesetzter Richtung initiieren.
In dem Fall müsste der 1. Initiator (der gleichzeitig die kleinste ID hat) eine Nachricht versenden, der 2. Initiator müsste 2 Nachrichten versenden und der n-te Initiator müsste n Nachrichten versenden.
Zusätzlich sind n Nachrichten nötig um die anderen Knoten zu informieren.
Best Case Bearbeiten
Im besten Fall wird der größte Knoten als erster zum Initiator. Wenn bis zum finalen Ringdurchlauf kein weiterer Knoten einen Durchlauf startet, kann so eine Nachrichtenkomplexität von n für die Auswahl erreicht werden, wobei auch hier nochmals n Nachrichten nötig sind um die anderen Knoten zu informieren. Die Nachrichtenkomplexität ist also
Average Case Bearbeiten
Die durchschnittliche Nachrichtenkomplexität beträgt bei k Initiatoren
Für sehr große Ringe werden fast nie mehr Nachrichten benötigt als im Durchschnitt.
Weblinks Bearbeiten
- (Memento vom 15. September 2007 im Internet Archive) an der Universität Mannheim
Einzelnachweise Bearbeiten
- D. Rotem, E. Korach and N. Santoro, Analysis of a distributed algorithm for extrema-finding in a ring, J. Parallel Distributed Comput. 4 (1987) 575-591.