8.5. Putting two parts together
Suppose that the number of devices is bouded by \( N = 10^7 \). When we use the GLE algorithm with parameters \( N=10^7 \) and \( p=10^{-2} \) then we will use 64 rounds and the number of selected devices is less than 10 with probability at least \(1-10^{-20} \). Next the selected group will use SLE with parameter \( L=69 \). This mixture of both algorithms will use totally 133 round and with probability at least \( 1-\frac{2}{10^{20}} \) will choose one leader. This probability is sufficient for all practical purposes.
Complexity of the algorithm
A more precise analysis shows that the proposed mixture of both algorithms runs in \( O(\log\log N) + O(\log \frac{1}{\varepsilon}) \) rounds, where \( N \) is an upper bound on devices and \(\varepsilon\) is the probability of a failure of this algorithm, i.e. the probability that after running both rounds of this algorithm more than two devices thinks that they are leaders. Presumably this is the best possible solution: further study should optimize constants occurring in the 'Big O' notations.