Solving consensus using S

By the definition of S some process is never suspected. Let us denote it by c for the rest of this section. Each process p has its own failure detector, denoted by D_p. We will use vectors with entries in the set $\{0,1,\bot\}$. We will make use of the notation $A\leq B$ if $a_i\neq\mathord{\perp}$implies $b_i\neq\mathord{\perp}$ for all i. Our vectors will be such that if $a_i=v \neq \bot$ then $b_i \in \{v, \bot\}$. In other words, it will never be the case that a_i=1 and b_i=0. We will also use the operations $\oplus$ and $\ominus$, which operate element-wise on vectors of $\{\mathord{\perp},0,1\}$. On each element $v\in\{\mathord{\perp},0,1\}$, they have the following properties.

So, the way $\oplus$ operates is akin to union and that of $\ominus$is akin to intersection. Armed with these tools we propose the following protocol in three phases. The protocol for a process p is given in Figure 7.1. In the protocol, v_p stands for the input bit.

    

Figure 7.1: (n-1)-resilient protocol using S

In the proof of correctness we will rely on the following three lemmas.

Lemma 12548

After phase 1 is complete, $V_c\leq V_p$ for all processes p which complete phase 1.

Proof. We will show that

$$V_c(i)=v_i\neq\mathord{\perp}\;\Longrightarrow\;\forall p(V_p(i)=v_i).$$ (8)

Let r be the first round when v_i is seen by c. If $r\leq n-2$, c will send a message containing v_i to all other processes. By perpetual weak accuracy , these processes will receive v_i in the next round. For the case r=n-1 first observe that a process will echo a value v_i only the first time this value is seen. If c receives v_i at round n-1 this means that the value has been echoed n-1 times, i.e. every other process has already seen it. $\Box$

Lemma 12566

After phase 2 is complete, V_c=V_p for all processes p which complete phase 2.

Proof. All processes will have received V_c. Since V_c is the smallest vector, we will always have that

$$V_c(i)\neq\mathord{\perp}\;\Longrightarrow\;V_p(i)\neq\mathord{\perp}.$$ (9)

By the definition of $\ominus$ we will also have

$$V_c(i)=\mathord{\perp}\;\Longrightarrow\;V_p(i)=\mathord{\perp}$$ (10)

after phase 2.$\Box$

Lemma 12574

$V_c\neq(\mathord{\perp},\mathord{\perp},\ldots,\mathord{\perp})$.

Proof. V_c contains its own input.$\Box$are now ready for the theorem.

Theorem 12577

The above protocol achieves consensus even if there is only one correct processor.

Proof. Limited bureaucracy follows from the algorithm and the strong completeness of the detectors. The only places where deadlock can occur is on row 7.3 and row 7.3 in the algorithm. If a process q is not faulty, the message it has broadcasted will eventually reach p. If q is faulty it will eventually be detected by D_p, by the definition of strong completeness.

Non-triviality follows from the algorithm. If all input values are 0(1), the positions in V_c will contain either $\mathord{\perp}$ or 0(1). Thus, all processes will decide on 0(1).

Agreement follows from the lemmas. Since a process p decides according to the contents of V_p and V_p=V_c for all p, all processes decide on the same value.$\Box$