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 ⋄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 ⋄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 ⋄P. We also show that, assuming that there is at least one incorrect process, C is optimal not only for ⋄P but also for ⋄S and Ω. We revisit our Reliable Broadcast based communication-optimal ⋄P algorithm, and we show that, regarding QoS measures, it performs better than the communication-efficient algorithms.