Failure Detection Lower Bounds on Registers and Consensus

This paper addresses the problem of determining the weakest failure detector to implement consensus in a message passing system when t out of n processes can crash (including when n/2 1), by addressing the problem of determining the weakest failure detector to implement a register. We complement and, in a precise sense, generalise previous results on the implementability of consensus and registers in a message passing model (augmented with the failure detector abstraction)