Message erasure according to Chang and Roberts

The algorithm " message deletion according to Chang and Roberts " is a maximum algorithm for distributed systems . It is used to select the node with the largest ID from nodes that are arranged in a ring . The basis is the face-off algorithm , the message complexity of which has been reduced.

requirements

Topology : unidirectional ring
Unique IDs

idea

As long as the maximum node is not yet known, each node becomes an initiator at some point and sends its ID to its neighbor. When someone receives a message that has an ID greater than their own, they will forward the message. If his ID is greater than the one stored in the message, he will swallow the message.

If a message makes an entire cycle, the initiator knows that it has the largest ID and informs the others by means of another cycle.

Pseudocode

initiator

Sende <ID, ID> an nächsten Knoten

A node K receives (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

Message complexity

Worst case

The worst case occurs when the nodes are sorted according to their IDs on the ring and initiate in the opposite direction.

In this case, the 1st initiator (who also has the lowest ID) would have to send a message, the 2nd initiator would have to send 2 messages and the nth initiator would have to send n messages.

${\ displaystyle \ sum _ {k = 0} ^ {n} (nk) => O (n ^ {2})}$ In addition, n messages are required to inform the other nodes.

Best case

In the best case, the largest node becomes the initiator first. If no further node starts a cycle until the final ring cycle, a message complexity of n can be achieved for the selection, with n messages again being necessary here to inform the other nodes. So the message complexity is ${\ displaystyle O (n).}$

Average case

The average message complexity is with k initiators ${\ displaystyle O (n \ log k).}$

Very large rings almost never require more messages than the average.

Web links

Lecture "Distributed Systems" ( Memento from September 15, 2007 in the Internet Archive ) at the University of Mannheim

Individual evidence

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

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