Adaptive Failure Detection in Logical Time: The Eventual Relative-Speed Model over Causal Blocks - Macêdo, Raimundo José de Araújo (Anais do Workshop de Testes e Tolerância a Falhas (WTF); 2026: Anais do XXVII Workshop de Testes e Tolerância a FalhasDO - 10.5753/wtf.2026.23211, 2026)
In this paper, we introduce the Eventual Relative-Speed (ERS) system model, a logical-time abstraction for distributed systems that lack an absolute physical time reference. In the ERS model, the relative progress of processes is governed by a finite parameter Γ, which characterizes the logical-time divergence among correct processes and holds only after an unknown Global Stabilization Time (GST). We propose a unified Causal Progress and Failure Detection algorithm built atop the Causal Blocks framework. By employing an adaptive suspicion threshold η i , our algorithm ensures causal consistency and satisfies the properties of an Eventually Perfect (⋄P) failure detector. Because it operates entirely in logical time, the system is intrinsically adaptive to fluctuations in relative speed— such as slowing or accelerating—without requiring the dynamic calibration of physical timeouts. We formally prove that the detector converges to Eventual Strong Accuracy as it adapts to transient delays, eventually stabilizing within the Γ bound. This provides a robust foundation for distributed computing in environments subject to arbitrary global load fluctuations.