Asymptotic Analysis of a Leader Election Algorithm

Christian Lavault, Guy Louchard

Itai and Rodeh showed that, on the average, the communication of a leader election algorithm takes no more than $LN$ bits, where $L\simeq 2.441716$ and $N$ denotes the size of the…