Exercise 24: Build a run of the Ben-Or randomised consensus algorithm that never terminates.

[rotiroti]

Build a run of the Ben-Or randomised consensus algorithm that never terminates.

[simonesestito]

Can we assume a faulty random number generator?

[susannacifani]

I found an example of a run of the Ben-Or that never terminates online:

[aleiis]

The Ben-Or algorithm is designed to converge with a high probability within a finite number of rounds. The only way to prolong the state of indecision is when no majority is reached, resulting in no ratified value. The presence of more failures makes it increasingly challenging to achieve a majority consensus. However, a majority can still be reached if $N-F$ participants share the same preference. In such a scenario, where $F$ equals the floor of $\frac{(N-1)}{2}$, the random number generator should never produce the same number as new preferences for $N-F$ participants, causing the algorithm to continue indefinitely.

Obviously, the algorithm wouldn't make progress if $F > \frac{N}{2}$, so it also wouldn't ever terminate.