Communication-efficient failure detection and consensus in omission environments

Failure detectors have been shown to be a very useful mechanism to solve the consensus problem in the crash failure model, for which a number of communication-efficient algorithms have been proposed. In this paper we deal with the definition, implementation and use of communication-efficient failure detectors in the general omission failure model, where processes can fail by crashing and by omitting messages when sending and/or receiving. We first define a new failure detector class for this model in terms of completeness and accuracy properties. Then we propose an algorithm that implements a failure detector of the proposed class in a communication-efficient way, in the sense that only a linear number of links are used to send messages forever. We also explain how the well-known consensus algorithm of Chandra and Toueg can be adapted in order to use the proposed failure detector.

Research highlights► We define a new failure detector class for the general omission model. ► We propose a distributed algorithm implementing the new failure detector class. ► The algorithm is communication-efficient, i.e., a linear number of links is used to send messages forever. ► We explain how to adapt Chandra–Toueg's consensus algorithm to work with the proposed failure detector.