Portal de Periódicos da CAPES

Communication-optimal eventually perfect failure detection in partially synchronous systems

2014; Elsevier BV; Volume: 81; Issue: 2 Linguagem: Inglês

10.1016/j.jcss.2014.06.010

1090-2724

Alberto Lafuente, Mikel Larrea, Iratxe Soraluze, Roberto Rodríguez,

Parallel Computing and Optimization Techniques

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 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.