On Quiescent Reliable Communication

We study the problem ofachieving reliable communication with quiescent algorithms (i.e., algorithms that eventually stop sending messages) in asynchronous systems with process crashes and lossy links. We first show that it is impossible to solve this problem in asynchronous systems (with no failure detectors). We then show that, among failure detectors that output lists of suspects, the weakest one that can be used to solve this problem is ⋄P, a failure detector that cannot be implemented. To overcome this difficulty, we introduce an implementable failure detector called Heartbeat and show that it can be used to achieve quiescent reliable communication. Heartbeat is novel: in contrast to typical failure detectors, it does not output lists of suspects and it is implementable without timeouts. With Heartbeat, many existing algorithms that tolerate only process crashes can be transformed into quiescent algorithms that tolerate both process crashes and message losses. This can be applied to consensus, atomic broadcast, k-set agreement, atomic commitment, etc. Key words. Algorithms, reliability, reliable communication, quiescence, asynchronous systems, heartbeat, crash failures, link failures, failure detection, fault-tolerance, message passing, processor failures AMS subject classifications. 68M15 Reliability and testing; 68Q22 Parallel and distributed algorithm