Next: The lower bound Up: Lecture 7 Previous: Properties of failure detectors

# 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 Dp. We will use vectors with entries in the set . We will make use of the notation if implies  for all i. Our vectors will be such that if then . In other words, it will never be the case that ai=1 and bi=0. We will also use the operations and , which operate element-wise on vectors of . On each element , they have the following properties.

So, the way operates is akin to union and that of 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, vp stands for the input bit.

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

Lemma 12548

After phase 1 is complete, for all processes p which complete phase 1.

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

Lemma 12566

After phase 2 is complete, Vc=Vp for all processes p which complete phase 2.

Proof. All processes will have received Vc. Since Vc is the smallest vector, we will always have that
 (9)
By the definition of  we will also have
 (10)
after phase 2.

Lemma 12574

.

Proof. Vc contains its own input.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 Dp, by the definition of strong completeness.

Non-triviality follows from the algorithm. If all input values are 0(1), the positions in Vc will contain either  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 Vp and Vp=Vc for all p, all processes decide on the same value.

Next: The lower bound Up: Lecture 7 Previous: Properties of failure detectors
Viggo Kann
Sat Dec 20 23:41:16 MET 1997