Abstract
Failure detectors are oracles introduced to provide processes in asynchronous systems with information about faults, enabling the solution of problems otherwise deemed impossible by the FLP (Fischer, Lynch, and Paterson) result. Traditionally, the "strength" of a failure detector is measured by implementability: detector $D$ is stronger than $D'$ if $D$ can implement $D'$. However, this relation has significant drawbacks. This paper explores an alternative: the solvability relation ($\succeq^s$), where $D$ is stronger than $D'$ if $D$ can solve any problem solvable by $D'$. By introducing a novel proof technique based on algorithmic transformations, we demonstrate that the solvability-based hierarchy differs substantially from the classic implementability-based one, resolving previous incomparabilities and collapsing existing hierarchies.
Introduction
In the study of distributed systems, the "FLP impossibility" theorem establishes that consensus cannot be reached in a purely asynchronous environment if even one process fails. To circumvent this, researchers utilize failure detectors—external oracles that provide hints regarding process failures. A central question in this field is how to rank these detectors by their "power" or the amount of information they provide.
Historically, the Chandra-Toueg relation ($\succeq^{CT}$) has been the standard metric. Under this framework, detector $D$ is considered stronger than $D'$ if there exists an algorithm that uses $D$ to implement $D'$. While foundational, this relation focuses on the internal mechanics of the detectors rather than the computational goals they enable. Furthermore, $\succeq^{CT}$ lacks certain desirable mathematical properties, such as reflexivity in all contexts, making it an imperfect tool for measuring computational power.
The Solvability Relation
To address these limitations, researchers have proposed the solvability relation ($\succeq^s$). Under this definition, $D \succeq^s D'$ if any problem solvable with $D'$ is also solvable with $D$. This approach is more robust as it directly measures the "problem-solving power" of an oracle. However, proving $\succeq^s$ has historically been difficult, often requiring researchers to fall back on implementability proofs (since $D \succeq^{CT} D' \implies D \succeq^s D'$). This paper introduces a direct method for establishing solvability without relying on implementability logic.
Methodology: Algorithmic Transformations
The core contribution of this work is a new proof technique based on algorithmic transformations. Instead of attempting to implement one detector from another, we show how to transform any arbitrary algorithm $A$ (designed for $D'$) into a new algorithm $\tilde{A}$ that functions correctly using $D$.
The paper introduces two primary transformations:
- Stall-on-Suspect (SoS): This transformation is applied when comparing the Marabout detector ($\mathcal{M}$) and the Perfect detector ($\mathcal{P}$). It forces a process to "stall" its execution if the detector suspects it has failed. This mechanism effectively filters out inconsistent behaviors that might arise when switching between detector models.
- Delay-a-Step (DaS): This is utilized for the $\mathcal{P}_k$ sequence of detectors. By inserting a "no-op" step at the beginning of an execution, the transformation synchronizes the perceived timing of failures, allowing an algorithm designed for one level of the hierarchy to function at another.
Key Findings
Applying these transformations to well-known failure detectors reveals significant shifts in the established hierarchy:
The Marabout vs. Perfect Detector
In the classic implementability framework, the Marabout detector ($\mathcal{M}$) and the Perfect detector ($\mathcal{P}$) were considered incomparable. $\mathcal{M}$ provides information about future crashes, while $\mathcal{P}$ provides perfect information about current crashes. Our analysis shows that $\mathcal{M} \succ^s \mathcal{P}$. Specifically, $\mathcal{M}$ can solve "strong consensus," a problem that $\mathcal{P}$ cannot solve. This demonstrates that $\mathcal{M}$ is strictly more powerful in terms of solvability.
The Collapse of the $\mathcal{P}_k$ Hierarchy
The $\mathcal{P}_k$ sequence represents a family of detectors where $\mathcal{P}_k$ provides information about processes crashing before or after a specific time $k$. Previous literature suggested these formed a strict hierarchy ($\mathcal{P}_k \succ \mathcal{P}_{k+1}$). However, using the Delay-a-Step transformation, we prove that for all "time-free" problems, these detectors are actually equivalent ($\mathcal{P}_k \equiv^s \mathcal{P}_{k+1}$). The perceived differences in power were an artifact of the implementability relation, not a reflection of the problems they can solve.
Conclusion and Future Work
The shift from implementability to solvability provides a more stable benchmark for distributed computing. Our results suggest that the "weakest failure detector" for a given problem is not an absolute property but is relative to the chosen comparison relation.
While the algorithmic transformation technique is a powerful tool, it may not be exhaustive. Future research is needed to determine if all instances of the solvability relation can be proven via transformations or if more complex techniques are required. Ultimately, this work challenges the community to reconsider how we define and measure the power of distributed oracles.
Summary updated