There is a set of n processes. Process 0 has an initial value x which can be 0 or 1, and each process i has a final decision value v_i. The possible decision values are 0, 1, and ø. The protocol is to satisfy the following two conditions:

CA1: If process 0 is nonfaulty, then each nonfaulty process terminates with v_i = x.

CA2: If process 0 is faulty, then there is a constant c in {0, 1} such that for each nonfaulty process i, v_i = c or v_i = ø.

1. Argue that this problem is weaker than reliable broadcast.

 
2. Give a protocol that implements this specification given that no more than f processes can be arbitrarily faulty. Do not use digital signatures. How is f bounded with respect to n?

 
3. Prove your protocol correct. Your proof need not be formal, but it should be a valid argument.

Consider a set of n processes in a fail-stop system, where each process knows the names of the other processes. Each process also has a portion of stable storage that implements an atomic write operation and whose contents is preserved across crashes. For example, suppose process p writes the value v to stable storage and at a later point writes the value v'. If p crashes after the write operation of v' completes, then after p recovers it will find the value v' in stable storage. But, if p crashes during the write operation of v', then upon recovery p will find either v or v' in stable storage. That is, a crash an an inopportune time won't cause the value on stable storage to become some value other than v or v'.

The processes are involved in some computation during which all of the processes eventually crash. We will say that process i failed before process j if process j detects process i's failure. Thus, the condition failed before defines an irreflexive partial order. A process i is one of the last processes to fail if it maximal in this order; that is, no process detects i's failure.

Assume that the processes start recovering after all of them have failed. The order in which they recover is not constrained.
 

1. Give a protocol that the processes can use such that they can determine when all of the last processes to fail have recovered. Your protocol should terminate as soon as possible; for example, waiting for all of the processes to recover is sufficient, but not necessary.

 
2. Suppose that the failed-before condition implemented an order that was transitive as well. What difference does this make in terms of your protocol and when it terminates?

 
3. Consider again the original system in which the failed-before relationship is not transitive. Can you implement a system in which the failed-before relationship is transitive? If so, then give a protocol; if not, then argue why not.