New failure detector mechanisms particularly suitable for use in asynchronous distributed computing systems in which processes may crash and recover, and two crash-recovery consensus mechanisms, one requiring stable storage and the other not requiring it. Both consensus mechanisms tolerate link failures and are particularly efficient in the common runs with no failures or failure detector mistakes. Consensus is achieved in such runs within 3.quadrature. time and with 4n messages, where .quadratu...