Nachrichtenauslöschung nach Chang und Roberts

Van Wikipedia, de gratis encyclopedie

Der Algorithmus Nachrichtenauslöschung nach Chang und Roberts ist ein Maximal-Algorithmus für verteilte Systeme. Er findet den Knoten mit der größten ID. Voraussetzung ist, dass die Knoten in einem Ring angeordnet sind. Über einen solchen Prozess kann ein Koordinierungsknoten designiert werden, um verteilte Algorithmen zu delegieren, zu steuern oder Ergebnisse zusammenzuführen.

Grundlage ist der Bullyalgorithmus, dessen Nachrichtenkomplexität gesenkt wurde.

Voraussetzungen[Bearbeiten | Quelltext bearbeiten]

Idee[Bearbeiten | Quelltext bearbeiten]

In einem Ring von Knoten, die alle eine numerische ID haben, kann der Knoten mit der größten ID, falls noch nicht bekannt ermittelt werden.

Dazu schicken Knoten ihre eigene ID an ihre Nachbarknoten.

Empfängt ein Knoten eine Nachricht, in der eine ID größer als die eigene gespeichert ist, sendet er die empfangene 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 | Quelltext 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 | Quelltext bearbeiten]

Worst Case[Bearbeiten | Quelltext 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 | Quelltext 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 | Quelltext bearbeiten]

Die durchschnittliche Nachrichtenkomplexität beträgt bei k Initiatoren [1]

Für sehr große Ringe werden fast nie mehr Nachrichten benötigt als im Durchschnitt.

Weblinks[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. 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.