Diamond-P-vCube: An Eventually Perfect Hierarchical Failure Detector for Asynchronous Distributed Systems

  • Gabriela Stein UNIOESTE
  • Luiz Antonio Rodrigues UNIOESTE
  • Elias Procópio Duarte Jr. UFPR
  • Luciana Arantes Sorbonne Université / LIP6 / CNRS

Resumo


In this work, we introduce ◊P-vCube, a push-based failure detector for asynchronous distributed systems. Processes running ◊P-vCube are hierarchically organized on the vCube virtual topology, which presents several logarithmic properties. As there are no bounds on communication delays and process execution times, false suspicions may occur. To ensure eventual accuracy, a process exits the system when it learns that it has been suspected by another process or suspects every other process. We show that ◊P-vCube guarantees completeness in any situation, and eventual accuracy if all correct processes remain strongly connected among themselves. We implemented the proposed algorithm using simulation and presented comparison results with the traditional all-test-all solution and a ring approach. The results demonstrate the trade-off between the speed of detecting actual failures and the number of messages used, as well as the scalability of ◊P-vCube.

Palavras-chave: Dependability, Unreliable Failure Detectors, Distributed Algorithms, Autonomic Systems, Fault-Tolerance
Publicado
16/10/2023
STEIN, Gabriela; RODRIGUES, Luiz Antonio; DUARTE JR., Elias Procópio; ARANTES, Luciana. Diamond-P-vCube: An Eventually Perfect Hierarchical Failure Detector for Asynchronous Distributed Systems. In: LATIN-AMERICAN SYMPOSIUM ON DEPENDABLE COMPUTING (LADC), 12. , 2023, La Paz/Bolívia. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2023 . p. 40–49.