Exercise 25: Consider an asynchronous system of 5 processes that run the Ben-Or

[rotiroti]

Consider an asynchronous system of 5 processes that run the Ben-Or randomized consensus algorithm. The number of failures that the system allows is 2. Show that, if at 2 failures occurs, then the probability that the protocol terminates after $x$ rounds is smaller than $\alpha^x$, for some $\alpha$.

[anto707]

Could this be modelled with a geometric distribution? If we see the probability of success (termination in a specific round) as the probability of picking all the same bits (all 0s or all 1s) in the coin flip step?

[riccardoscuto]

I asked BingAI and he wrote this, what do you think?

The Ben-Or randomized consensus algorithm is a fundamental algorithm in distributed computing, designed to solve consensus in an asynchronous message-passing system where processes can fail by crashing.

In the specific case, where there are 5 processes and up to 2 can fail, the algorithm can still reach consensus if a majority of processes are correct. However, the termination of the algorithm is probabilistic, and it’s not guaranteed to terminate in a fixed number of rounds.

The probability of termination after $x$ rounds being smaller than $\alpha^x$, for some $\alpha$, is a common way to express the fact that the probability of termination decreases exponentially with the number of rounds. This is due to the randomized nature of the algorithm: in each round, each process flips a coin (i.e., generates a random bit), and the decision (consensus) is based on the majority of the coin flips. If there is no majority (i.e., a tie), the processes proceed to the next round and repeat the process.

[aleiis]

The variable $X \sim \text{Geom}(p)$ represents the number of rounds required for the algorithm to achieve a round success with a probability of $p$. In order for a round to be considered successful, a minimum of three processes must have the same preference, either '1' or '0'.

The probability $p$ depends on the number of failures, and there are three distinct cases that determine its value:

• If $F = 0$ then $p = 1$
• if $F = 1$ then $p = \frac{10}{16}$
• If $F = 2$ then $p = \frac{2}{8}$

Since $X$ follows a geometric distribution, the probability that the protocol terminates after $x$ rounds (or more) is:
$P(X > x) = (1-p)^x$.

[simonesestito]

The probability $p$ depends on the number of failures, and there are three distinct cases that determine its value:

• If $F = 0$ then $p = 1$

How can $p$ be equal to $1$?

[aleiis]

How can $p$ be equal to $1$?

If there are no failures the system with 5 participants will always reach a majority either on '0' or '1' on the first round.