TimeSlice Algorithm

This is a leader election protocol in a ring. The protocol works as follows: 

leader := null
Phase $v\in 1,2,\ldots$:
  For round $r\in 1,2\ldots,n$:
    If $u = v$ and $leader \ne null$:
      send $leader u$ to neighbors
  on $leader m$ from neighbor:
    $leader \leftarrow m$
    send $leader m$ to neighbors
    halt

Notes

  • This protocol is from Distributed algorithms. Nancy A. Lynch. 1997.
  • This protocol uses silence in synchrony.
  • This has a communication complexity of \(O(n)\).
  • This protocol assumes that all nodes know \(n\).
  • This has a round complexity of \(O(u_{min}n)\) where \(u_{min}\) is the smallest uid among all the \(n\) nodes.
  • This protocol works even if the ring is unidirectional.