LCR Protocol

The nodes are in a ring. Every node has a UID \(u\).

Non-halting main protocol

$send := null$
$status := null$
for every round $r$ do
  send the current value of $send$ to process $u+1$
  if the incoming message is $v$, a UID, then
    case
      $v>u$: $send \leftarrow v$
      $v=u$: $status \leftarrow leader$
      $v<u$: do nothing
    endcase

Notes

  • This is from Distributed algorithms. Nancy A. Lynch. 1997
  • This is also called the LCR Algorithm (Le Lann, Chang and Roberts)
  • This protocol needs \(n\) rounds for the node with the highest UID to output itself as the leader.
  • This algorithm as is does not halt.
  • The communication complexity is \(O(n^{2})\) (Since in every round, every one sends a message to their neighbor)
  • The round complexity is \(O(n)\).
  • This protocol works even if the nodes do not start at the same time.

Modification to allow halting

$leader := null$
on $status \ne null$:
  $leader \leftarrow u$
  send $report u$ to $u+1$
  halt
on receiving $report v$:
  $leader \leftarrow v$
  send $report v$ to $u+1$
  halt