A Randomized Protocol for Consensus

We describe a protocol which was originally proposed by Ben Or [8]. The protocol runs forever but every non-faulty process makes a decision in finitely many steps. With high probability however, this number of steps is huge. The exercises explore some possible modifications to improve the situation somewhat. In spite of the fact that Ben Or's protocol is not practical (because of the huge amount of ``bureaucracy'' it generates) this result is important because it indicates that by using randomization the impossibility of consensus can be circumvented. Indeed, the search for good randomized solutions for the consensus problem has been an active area of research. For instance, recent solutions for the shared-memory model- where a set of n processes access asynchronously a common shared memory via read and write operations- require as few as $O(n \log^2 n)$ expected operations per process. Furthermore, these solutions are (n-1)-resilient (see, for instance, [2,3]). In fact, by using randomization a protocol can cope even with Byzantine failures! (see, for example, [28]).

We now turn to Ben Or's protocol, which is illustrated in Figure 6.1. In the protocol v stands for any value different from $\bot$ and $a_p:={\ooalign {\hfil\raise-.2ex\hbox{\$}\hfil\crcr\mathhexbox20D}}$means that the value of a_p is set at random to be 0 or 1 with uniform probability. Although the protocol goes on forever the decision value of a process is unique- once a decision is made it cannot be changed. We can assume that the decide instruction has the property that once the first value is output, all subsequent invocations output the same value. The protocol is f-resilient as long as f<n/2 and assumes that channels are FIFO. It consists of an infinite repetition of ``asynchronous rounds''. During round r only messages which are timestamped with round number r are processed. The protocol consists of an endless broadcast of a-values and b-values. The initial a-value of a process is set to be equal to the input bit and can therefore be either 0 or 1. Thereafter, the a- and b-values can be in the set $\{0,1,\bot\}$ and are determined as follows. During phase 1 of round r, each process waits for the first n-f a-values timestamped with r and sets its own new b-value as a function of these. During the second phase of round r each process sends its own b-value (timestamped with r) to all, including oneself, and waits for the first n-f b-values with timestamp r. Depending on these, it then sets its own new a-value and decides whether to commit to a final value. If the set of b-values does not satisfy a certain condition, the new a-value is set at random. Once the new a-value is determined it is sent to all (including oneself) with the new timestamp. And so on.

  

Figure 6.1: BenOr's protocol for process p

We now prove that the three requirements of Non Triviality, Agreement and Limited Dithering are satisfied.

We start with Non Triviality. Suppose that all input bits are 0. Then, all processes decide 0 at round 1. To see this just follow the protocol through round 1. Each process starts by sending 0 to all. Therefore every correct process will set the b-value to 0 (line 6) and send it to all. Then, every process still running will receive 0's with timestamp 1 from n-f distinct processes and hence will decide 0 (line 11). The same reasoning holds for the case when all inputs are 1.

Let a_pr and b_pr denote the a-value and b-value of process p at round r, respectively. To establish Agreement and Limited Dithering we shall make use of a simple but important observation.

Proposition 12407

 For all r, either $b_{pr} \in \{1,\bot\}$ for all p or $b_{pr} \in \{0,\bot\}$ for all p.

Proof. Suppose to the contrary that, at some round r, there are two processes p and q such that b_pr=0 and b_qr=1. From the b-value deciding rule (lines 6 and 7) it follows that p received 0's from n-f distinct processes and q received 1's from n-f distinct processes. This means that there are at least $2(n-f) \le n$ processes in the system. But this is a contradiction since n>2f.$\Box$establish Agreement, suppose that at round r process p decides on some value v. Suppose also that round r is the first round where a decision is made. We want to show that every correct process decides v by round r+1. Suppose without loss of generality that p decides on 0. First, it is impossible that two processes p and q deciding at round r decide on different values, or otherwise some b-values would be 0 and others would be 1, violating Proposition 6.1. Since p decides on it has received 's from n-f distinct processes. This means that every other process at round r receives 0's from at least $n-2f \ge 1$processes. By line 12, every process still running will set its new a-value for round r+1 to 0 (including p, by line 11). Therefore at the beginning of phase 1 of round r+1 every process sends 0 to all. At this point, the same reasoning used in the case of Non Triviality allows us to conclude that every process which has not already decided on 0 at round r will do so at round r+1.

It then remains to prove Limited Dithering. It is here that randomization enters into the picture.

In order to get an intuition of how randomization is used, suppose that the inputs are split in half; half of them being zeroes and half of them being ones. In this case, every process will set its b-value to $\bot$ (line 7). Since all b-values are $\bot$, each process will set the next a-value at random With high probability, about half of the new a-values will be zeroes and about half will be ones. Which again will force a random determination of all new a-values, and so on.

It is conceivable that this goes on indefinitely but this event has probability zero. How long can this go on? It follows from Proposition 6.1 that if $A_r=(a_{1r},a_{2r},\ldots,a_{nr})$ denotes the vector of the new a-values then, either A_r is of the kind

$$A_r = (v,\ldots,{\ooalign {\hfil\raise-.2ex\hbox{\$}\hfil\cr... ...{\ooalign {\hfil\raise-.2ex\hbox{\$}\hfil\crcr\mathhexbox20D}})$$

or of the kind

$$A_r = (\bar{v}, \ldots,\dagger,\ldots,\dagger,\ldots, {\ooal... ...\ooalign {\hfil\raise-.2ex\hbox{\$}\hfil\crcr\mathhexbox20D}}).$$

where $a_{ir}={\ooalign {\hfil\raise-.2ex\hbox{\$}\hfil\crcr\mathhexbox20D}}$ means that the value is set at random and $a_{ir}=\dagger$means that process i is dead (and hence it can be ignored). In other words, it is never the case that a_ir=v and $a_{jr}=\bar{v}$. This implies that there is always a positive probability that all new proposal coincide, i.e. that either a_ir=v for all i still running or $a_i=\bar{v}$ for all i still running. Since processes flip coins independently, this probability is at least 2^-n. When this happens we say that a landslide takes place. The argument for Non Triviality already seen shows that in case of a landslide every non faulty process will decide by the end of the next round. Now, for any round r

$$\mbox{Pr}[\mbox{\sl no landslide at $r$}] \le 1 - \frac{1}{2^n}.$$

Since the coin flips are independent, the probability of having no landslide for k consecutive rounds is then

$$\mbox{Pr}[\mbox{\sl no landslide for first $k$ rounds}] \le \left (1 - \frac{1}{2^n} \right )^k.$$

This probability goes to zero as k goes to infinity. It takes however, exponentially many steps before the value is very small. The value is about 1/e when k=2ⁿ which is exponential in n. So, if we run the protocol for k=c 2ⁿ rounds then

$$\mbox{Pr}[\mbox{\sl landslide within $k$ rounds}] \ge 1 - \left (1 - \frac{1}{2^n} \right )^k \ge 1-\frac{1}{e^c}.$$

This probability goes very quickly to 1 as c grows. A slightly more sophisticated analysis shows that an exponential number of rounds is, with high probability, both necessary and sufficient.