Communication-optimal eventually perfect failure detection in partially synchronous systems

• We present the notion of communication optimality for implementing failure detectors.
• Communication optimality consists in using c links (c: number of correct processes).
• We show that c is the minimum number of links needed for implementing ◇P.
• We show that, if c• We propose two ring-based communication-optimal ◇P algorithms.

Since Chandra and Toueg introduced the failure detector abstraction for crash-prone systems, several algorithms implementing failure detectors in partially synchronous systems have been proposed. Their performance can be measured by their Communication efficiency, defined as the number of links used forever. In this regard, in a communication-efficient algorithm only n links are used forever, n being the number of processes in the system. In this paper, we present communication optimality, a communication efficiency degree reached when only c links are used forever, c being the number of correct processes. We show that c   is the minimum number of links used forever required to implement ◇P◇P and that c   is also optimal for ◇S◇S and Ω   when c