VairableSpeeds Protocol

The nodes are in the form of a ring.

leader := null
token := u
For round $r\in 1,2,\ldots$:
  Send $leader token$ to neighbors every $2^{token}$ rounds
  on receiving $leader v$:
    if $v < token$:
      set $token \leftarrow v$
    if $v = u$:
      $leader \leftarrow u$
      halt

Notes

This protocol is from Distributed algorithms. Nancy A. Lynch. 1997
The round complexity of the protocol is \(O(n\cdot 2^{u_{min}})\)
The communication complexity is \(O(n)\).
The protocol presented above needs the nodes to start at the same time.
- Define people who wake up before hearing any message as starters, and others as non-starters.
- Starters send "wakeup u" to neighbors.
- All nodes forward this to neighbors.
- A starter on receiving a wakeup message then starts the above protocol.
- Nodes update token using the wakeup messages as an optimization.