Probabilistic and temporal failure detectors for solving distributed problems

Failure detectors (FD)s are celebrated for their modularity in solving distributed problems. Algorithms are constructed using FD building blocks. Synchrony assumptions to implement FDs are studied separately and are typically expressed as eventual guarantees that need to hold, after some point in time, foreverand deterministically. But in practice, they may hold only probabilistically and temporarily. This paper studies FDs in a realistic system N, where asynchrony is inflicted by probabilistic synchronous communication. We first address a problem with lozenge S, the weakest FD to solve consensus: an implementation of "consensus with probability 1" is possible in Nwithout randomness in the algorithm, while an implementation of "lozenge Swith probability 1" is impossible in N. We introduce lozenge S*, a new FD with probabilistic and temporal accuracy. We prove that lozenge S*(i) is implementable in Nand (ii) can replace lozenge S, in several existing deterministic consensus algorithms that use lozenge S, to yield an algorithm that solves "consensus with probability 1". We extend our results to other FD classes, e.g., lozenge P, and to a larger set of problems (beyond consensus), which we call decisive problems. (C) 2021 Elsevier Inc. All rights reserved.