Uniform leader election protocols for radio networks

A radio network is a distributed system with no central arbiter, consisting of n radio transceivers, henceforth referred to as stations. We assume that the stations are identical and cannot be distinguished by serial or manufacturing number. The leader election problem asks to designate one of the stations as leader. A leader election protocol is said to be uniform if in each time slot every station transmits with the same probability. In a seminal paper Willard (1986) presented a uniform leader election protocol for single-channel single-hop radio stations terminating in log log n+o(log log n) expected time slots. It was open whether Willard\´s protocol featured the same time performance with "high probability". We propose a uniform leader election protocol that terminates, with probability exceeding 1-1/f for every f/spl ges/1, in log log n+o(log log n)+O(log f) time slots. We also prove that for every f/spl isin/e/sup O(n)/, in order to ensure termination with probability exceeding 1-1/f, Willard\´s protocol must take log log n+/spl Omega/(/spl radic/f) time slots. Finally, we provide simulation results that show that our leader election outperforms Willard\´s leader election protocol in practice.