8.2. Breaking symmetry
There a lot of results which claim more or less the following results: is a group of devices run simultaneously the same algorithm and starts with the same initial state, then after arbitrary number of steps all of them are in the same state. And this implies that they cannot choose a leader.
Randomize breaking symmetry
One of way of solving this problem, called randomize breaking symmetry, is to equip each device in a generator of random numbers. We may, for example, use these generators at the beginning of the algorithm for choosing initial state of algorithm at each device - and after this phase devices starts to be distinguishable.
Let us recall that a random variable \( X \) has a geometric distribution with parameter p (\( X \sim Geo(p) \)), where \( 0 \lt p \lt 1\) if \( \Pr(X=n) = (1-p)^{n-1} p\) for each natural number \( n\geq 1\). It can be easily checked that if \( X \sim Geo(p) \), then \( E(X) = \frac{1}{p} \), where \( E(X) \) denotes the expected value of the random variable \( X \).