An Evaluation of Communication-Optimal P Algorithms

This paper presents an evaluation of several communication-optimal algorithms implementing the diamP class of failure detectors. The first algorithm is based on a reliable broadcast primitive, involving a quadratic number of messages to manage a suspicion. The second algorithm uses exclusively one-to-one communication, involving a linear number of messages to manage a suspicion, but with a higher latency to propagate the suspicion to the rest of processes. A third algorithm reduces this latency using an additional one-to-all communication mechanism. We evaluate the quality of service provided by these algorithms, in terms of the capability of the failure detector to provide right answers and the reaction time after a failure.