On the implementation of communication-optimal failure detectors

Several algorithms implementing failure detectors have been proposed in the literature. In particular, we have proposed a family of communication-efficient lozenge P algorithms, i.e., algorithms using n links to carry messages forever, being n the number of processes in the system. Moreover, we have recently proposed a lozenge P algorithm that uses only C links, being C the number of correct processes. In this paper, we show that C is the minimum number of links required to implement lozenge P. We also show that, assuming that there is at least one incorrect process, C is optimal not only for lozenge P but also for lozenge S and Q. We revisit our Reliable Broadcast based communication-optimal lozenge P algorithm, and we show that, regarding QoS measures, it performs better than the communication-efficient algorithms.