Ring algorithm

This article was due to content flaws on the quality assurance side of the computer science editorial added. This is done in order to bring the quality of the articles from the subject area of computer science to an acceptable level. Help to eliminate the shortcomings in this article and take part in the discussion ! ( + )

Reason: Rather incomprehensible, no source (web link 404), different opinions on the complexity of the message (see previous processing ) - Howwi 16:50, Aug. 2, 2009 (CEST)

The ring algorithm is a selection algorithm with which a process with a special task is determined in a distributed system . This task can be a coordinator, for example.

requirements

Topology : unidirectional ring
Unique IDs

procedure

The ring algorithm can be started by any process if it detects that the original coordinator has failed, or by a process that has just been restarted and therefore does not yet know the coordinator. The process initiating the election sends a voting message with its own process number (ID) to the next available process in the ring. This adds its own ID to the message and in turn sends it to the next process in the ring.

Once the voting message has completely circled the ring, the initiating process receives a voting message that already contains its own ID. That ends the election. A new process for the special task is now determined from the processes involved in the entry in the election message. Usually this is the process with the highest process number. The election message is now converted into a coordination message, which is again sent to each participating process in the ring. This message informs the processes involved of the election result.

Pseudocode

initiator

Sende <ID, ID> an nächsten Knoten

A node K receives <r, max>

wenn ID(K) > max
    max := ID(K);

wenn r == ID(K)
    wenn max == ID(K)
         "ICH HABE GEWONNEN"
    sonst
          "max HAT GEWONNEN"

sonst
    sende <r, max> an nächsten Knoten

Message complexity

In the case of processes in the ring, a maximum of voting messages must be sent. Since the process that holds the election knows after the election which processes are active, a coordination message is only sent to them. This leads to a complexity of maximum or . ${\ displaystyle n}$ ${\ displaystyle n-1}$ ${\ displaystyle 2 (n-1)}$ ${\ displaystyle {\ mathcal {O}} (n)}$