5.18 This exercise guides you through a direct proof of the impossibility of I- resilient consensus for shared memory. Assume A is a 1-resilient consensus algorithm for n processors in shared memory.

(a) Prove that there is a bivalent initial configuration of A.

(b) Let D be a bivalent configuration of A and p; be any processor. Using the outline given below, prove that there exists a schedule or ending with the event i such that (D) is bivalent. Outline: Suppose, in contradiction, that there is no such schedule. Then every schedule that ends in i, when started at D, leads to a univalent configuration. Without loss of generality, assume that i(D) is 0-valent. (b.1) Show that there exists a finite schedule

a, in which p; does not take a step, and a processor p, other than pi, such that i(a(D)) is 0-valent and i(j(a(D))) is 1-valent. (b.2) Let Do = a(D) and D = j(a(D)). Consider the possible actions being performed by p; and p; in taking a step from Do (e.g., reading or writing) and show that a contradiction is obtained in each case.

(c) Combine

(a) and

(b) above to show there exists an admissible execution of A that does not satisfy the termination condition.