Consensus in Asynchronous Systems

In this lecture we study the consensus problem in message-passing, asynchronous systems. In such systems each process runs according to its own clock; no assumption is made about the relative speeds of different clocks. Processes communicate solely by sending messages which are neither corrupted nor lost, but there is no guarantee on the time of delivery. This scenario is actually prevalent in real systems such as distributed networks. The problem we want to study is the same consensus problem defined in the context of Byzantine Agreement, with the important modification that we will consider a more benign type of fault. As before, we have a set of n>1 processes denoted by $p_1, \dots ,p_n$. For each i, p_i has an input bit, $x_i \in \{0,1\}$, and is to decide on an output bit, d_i. The protocol should satisfy the following three conditions:

Non-triviality : If x_i = 0 (1) for all i, then each correct process decides (1).

Agreement : All correct processes make the same decision.

Limited dithering : Eventually all correct processes come to a decision.

Note that we consider Limited Dithering instead of Limited Bureacracy . This will make our lower bound result stronger. The only type of malfunctioning we want to cope with are An important difference is that we will be considering crash failures : a process may crash (or die), i.e. stop functioning forever. A process who dies is said to be faulty , and correct otherwise. The message-passing mechanism is secure and point-to-point: messages are send directly to the recipient and are neither corrupt nor lost. There is however no guarantee on the time of delivery. Intuitively, reaching consensus in such systems is impossible because processes cannot tell whether another process is dead or just temporarily isolated from the outside world because its messages are delayed; if they wait the might do so forever, and if they decide the might find out that the other process already came to a different decision. This rough intuition is formalized in the following seminal result by Fischer, Lynch, and Paterson [18].

Theorem 12173

 There is no 1-resilient deterministic protocol for consensus in message-passing, asynchronous systems. That is, no protocol can tolerate 1 crash failure.

This result highlights the enormous difference existing between synchronous and asynchronous systems. As we saw, if the system is synchronous up to n/3 - 1 malicious faults can be tolerated- the protocol works correctly in spite of the arbitrary behaviour of (almost) one third of the processes. If the system is asynchronous however, not even one crash failure- a much more benign kind of fault- can be tolerated. This result does depends on the asynchronous nature of the system and not on other assumptions. For instance, the same impossibility result (and in fact essentially the same proof) extends to shared-memory systems, where processes communicate by asynchronously reading and writing a shared memory accessible to all (see, for instance, [4,27]).

We now turn to the proof of the Theorem 5.1. First off, we give a formalization of the model. Message passing is performed by means of Send and Receive operations. There is a buffer of messages B containing messages that have been sent but not yet received. The buffer contains pairs of the form (p,m) where m is the message and p is the recipient. $\mbox{\bf Send}(q, (p,m)$ ``sends'' the message m to process p by adding (p,m) to the buffer. To get a message, q samples the buffer with $\mbox{\bf Receive}(q)$. If there are no messages for q, q will simply receive a null marker, $\bot$. If there are messages ready for q in the buffer, either q will receive any one of them-- say m, which will cause (q,m) to be removed from the buffer-- or q will receive $\bot$. However, each message is received within a finite number of attempts. The message delivery discipline can be assumed to be anything. To make the lower bound result more interesting we assume that message delivery is fair in the following sense: if a message (p,m) is sent, and if p performs infinitely many $\mbox{\bf Receive}(p)$ operations, then m will be delivered to p after finitely many attempts.

A process is modeled as a deterministic automaton, possibly with infinitely many states. A process p works in steps; in each step, p performs $\mbox{\bf Receive}(p)$, computes (in a finite time) the next state, and sends a finite number of messages. Moreover, we may assume that each correct process goes on like this forever; we can always modify our protocol to satisfy this.

We continue with some definitions: A configuration C is a vector containing the process states and the message buffer content. An event is a pair e=(p,m) where p is a process and m is a message or the null marker, $\bot$. The event e=(p,m) is applicable to a configuration C if (p,m) is in the buffer, or if $m = \bot$, i.e. $(p,\bot)$ is always applicable. When e = (p,m) is applicable to C, the reception of m by p defines the next step in the system. This will give a new configuration, which we write as e(C). We let e₁ e₂ (C) denote e₂(e₁(C)), and so forth. We record the following definition for future reference.

Definition 12221

 A run (from C) is a (possibly empty) sequence of events that can be applied in turn, starting from C.

Finally, a configuration D is accessible if it can be reached from an initial configuration, i.e. if $D=\sigma(C)$ for some initial configuration C and run $\sigma$.From now on, when we talk of a configuration, we mean an accessible configuration. We classify configurations into three categories:

• A configuration is 0-valent if some process has decided or if in all configuration which are accessible from it the decision value is ;
• A configuration is 1-valent if some process has decided 1 or if in all configuration which are accessible from it the decision value is 1;
• A configuration C is bivalent if sor some of the configuration accessible from it the decision value is and for others the decision value is 1.

A configuration is univalent if it is either 0-valent or 1-valent.

Definition 12233

We say that a run is admissible if each process, with possibly one exception, takes an infinite number of steps.

We are ready now for the the proof, which is by by contradiction. The contradiction is reached by assuming that a 1-resilient protocol exists and by exhibiting an admissible run of the protocol where all processes remain forever undecided, therefore violating Limited Dithering. Notice that an admissible run embodies the notion of fairness since each process, except perhaps one, takes infinitely many steps without deciding.

Lemma 12234

 There is a bivalent initial configuration.

Proof. Let C₀ be the initial configuration where x_i = 0 for all i, and for $1 \leq j \leq n$, let C_j be the initial configuration where x_i = 1 for $1 \leq i \leq j$ and x_i = 0 for all remaining i. Notice that the non-triviality property implies that C₀ is 0-valent and C_n is 1-valent. We now show that at least one configuration among $C_1, \dots , C_{n-1}$ is bi-valent. For if not, let j be the lowest number such that C_j is 1-valent. Obviously, C_j-1 must then be 0-valent. Since we suppose our protocol to be 1-resilient, we can let p_j be dead from the beginning; there is still a finite run $\sigma$(thus not involving p_j) from C_j such that a decision is made. But x_j is the only input bit where C_j-1 and C_j differ. Therefore, $\sigma$ is a run also from C_j-1, and in particular, it will lead to the same decision there. This will contradict either C_j-1 being 0-valent or C_j being 1-valent.$\Box$

The following is an easy technical lemma which will come handy.

Lemma 12270

 (Commutativity Lemma) Let $\sigma _1$ and $\sigma _2$ be runs from C, and suppose that the set of processes taking steps in $\sigma _1$ is disjoint from the set of processes taking steps in $\sigma _2$. Then $\sigma _1 \sigma _2$ and $\sigma _2 \sigma _1$ are both runs from C, and they lead to the same configuration.

Proof. Homework.$\Box$

Let C be a configuration and e=(p,m) an event applicable to C. Notice that if e is applicable to C it remains applicable until its corresponding step is executed. A run $\sigma=e_1 e_2 \ldots e_n$ is e-free if it does not contain e.

Lemma 12285

 Let C be bivalent, and let e be any applicable event. Then there is a (possibly empty) e-free run $\sigma$ such that $e(\sigma (C))$ is bivalent.

With this lemma we can prove the theorem. To see this, construct an admissible run by starting with an initial bivalent configuration C₀, whose existence is guaranteed by Lemma 5.1, as follows. Let $p_1,p_2,\ldots,p_n$ be any ordering of the processes. Pick any applicable event e₁=(p₁,m₁) and apply the lemma, thereby obtaining a second bivalent configuration $C_1 = e_1( \sigma_1 (C_0))$.To make things more concrete, e₁=(p₁,m₁) can be selected such that m₁ was the first message ever sent to p₁ or $\bot$ if there is none. Then, apply the lemma again by picking an event e₂=(p₂,m₂) applicable to C₁ (notice $p_1\ne p_2$), obtaining another bivalent configuration $C_2 = e_2( \sigma_2(C_1))$. As before, m₂ can be the first message ever sent to p₂ still present in the buffer. By proceeding in a round robin fashion- making p_i perform step e_1+kn (k ge 0)- we obtain an infinite admissible run where every process remains forever undecided and yet takes infinitely many steps.

Proof. Assume there is no such $\sigma$. Then e(C) must be uni-valent; assume without loss of generality that it is 0-valent. We want to show the existence of an e-free run $\sigma _0$ leading from C to a configuration D such that e(D) is 1-valent. This means that on the way from C to D, there must be two neighboring configurations A and B such that B = f(A), where f is some event where e(A) is 0-valent and e(B) is 1-valent. We illustrate the situation in Figure 5.1. To prove the existence of such a run notice first that since C is bi-valent, there is a run $\sigma _1$ such that $E = \sigma _1(C)$ is 1-valent. Then, we distinguish between two cases:

• If $\sigma _1$ is e-free, let $\sigma _0 := \sigma _1$ and we are done because $D := \sigma _0 (C) = E$ is 1-valent and, obviously, e(D) is also 1-valent.
• Otherwise, let $\sigma _0$ be the largest e-free prefix of $\sigma _1$, and let $D := \sigma _0 (C)$. By assumption, $e(D) = e(\sigma _0 (C))$ cannot be bivalent. And since there is a (possibly empty) run from e(D) to E, e(D) cannot be 0-valent, so it must be 1-valent.

  

Figure 5.1: Finding A and B

Focus then on A and B=f(A) (refer always to Figure 5.1). We first show that the processes taking steps in e and f cannot be different. For if they were, according to Lemma  5.2, we would have e(B) = e(f(A)) = f(e(A)). This is impossible, since e(B) is 1-valent, and e(A) is 0-valent. Thereafter, we show that we will still end up with a contradiction. Let p be the process taking steps in e and f. Since our protocol is supposed to be 1-resilient, there is a run $\rho$ in which p does not take any steps, leading from A to some configuration R where a decision has been taken. See Figure 5.2.

  

Figure 5.2: R cannot be univalent

However, the decision can neither be 0 nor 1:

• By Lemma  5.2, we have $\rho (e(B)) = \rho (e(f(A))) = e(f(\rho (A))) = e(f(R))$.Since e(B) is 1-valent, R cannot be 0-valent.
• But according to Lemma  5.2, we also have $\rho (e(A)) = e(\rho (A)) = e(R)$. Since e(A) is 0-valent, R cannot be 1-valent.

$\Box$