IR is called the independent recovery property.It is a handy property to have, because it allows for quick garbage collection. Once the decision is reached, only the stable storage of the crashed process needs to be retained for recovery purposes.
 

1. Show that there is no atomic commit protocol that satisfies IR can tolerate two crashes.
   
   
2. Is there an atomic commit protocol that satisfies IR for n = 2 and for one crash failure?

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.