Abstract. We study the problem of achieving 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 without failure detectors. We then show how to solve it using a new failure detector, called heartbeat. In contrast to previous failure detectors that have been used to circumvent impossibility results, the heartbeat failure detector is implementable, and its implementation does not use timeouts. These results have wide applicability: they can be used to transform many existing algorithms that tolerate only process crashes 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.  This paper introduces heartbeat, a failure detector that can be implemented without timeouts, and shows how it can be used to solve the problem of quiescent reliable communication in asynchronous message-passing systems with process crashes and lossy links. To illustrate this problem consider a system of two processes, a sender s and a receiver r, connected by an asynchronous bidirectional link. Process s wishes to send some message m to r. Suppose first that no process may crash, but the link between s and r may lose messages (in both directions). If we put no restrictions on message losses it is obviously impossible to ensure that r receives m. An assumption commonly made to circumvent this problem is that the link is fair: if a message is sent infinitely often then it is received infinitely often. With such a link, s could repeatedly send copies of m forever, and r is guaranteed to eventually receive m. This is impractical, since s never stops sending messages. The obvious fix is the following protocol: (a) s sends a copy of m repeatedly until it receives ack(m) from r, and (b) upon each receipt of m, r sends ack(m) back to s. Note that this protocol is quiescent: eventually no process sends or receives messages.
For example Aguilera et al. implemented a failure detector allowing a quiescent reliable communication when processes can fail REF .
Heartbeat : A Timeout-Free Failure Detector for Quiescent Reliable Communication
ICDE
Computer Science