Leader election
This product was added to computer science because of the content, defects on the quality assurance side of the editor. This is done to bring the quality of the articles from the computer science subject area to an acceptable level. Help us to eliminate the substantive shortcomings of this article and take part you in the discussion! ( ) Reason: Rather incomprehensible sourceless (Weblink 404 ), different opinions on the message complexity (see previous editing) - Howwi 16:50, August 2, 2009 (UTC)
The ring algorithm is a selection algorithm, with the system in a distributed, a process is identified with a particular task. This task can be for example a coordinator.
Requirements
- Topology: Unidirectional Ring
- Unique IDs
Expiration
The ring algorithm can be started from any process if it detects that the original coordinator has failed, or by a process that has just been rebooted and therefore the coordinator does not know yet. The choice intialisierende process sends an election message with its own process number (ID ) to the next available process in the ring. This adds to the message its own ID to, and sends it again to the next process in the ring.
Has the option send the ring once completely surrounded, the initiating process receives an election message, which already contains the unique ID. So the choice is completed. From the processes involved by registration in the election message, a new process for the specific task is now determined. Usually this is the process with the highest process number. The choice of message is now transformed into a coordination message that is sent back to each participating process of the ring. This message is the processes involved notified of the election results.
Pseudocode
Initiator
Send
If ID (K ) > max
max: = ID (K ) if r == id (K )
if max == id (K )
" I HAVE WON "
otherwise
"max HAS WON " otherwise
send
With n processes in the ring with up to n -1 election messages must be sent. Because of the choice which stop the process once the election know which processes are active, a coordination message will be sent only to this. This leads to a complexity of at most 2 (n- 1) respectively.