Communication-optimal eventually perfect failure detection in partially synchronous systems

摘要

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 optimally, 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 and that c is also optimal for ◇S and Ω when c ＜ n. Finally, we propose two communication-optimal ◇P algorithms following respectively one-to-all and one-to-one communication patterns to manage suspicions, showing that there is a trade-off between detection latency and sporadic communication overhead.