Solvability-Based Comparison of Failure Detectors

Srikanth Sastry, Josef Widder

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:

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

Abstract

Failure detectors are oracles that have been introduced to provide processes in asynchronous systems with information about faults. This information can then be used to solve problems otherwise unsolvable in asynchronous systems. A natural question is on the "minimum amount of information" a failure detector has to provide for a given problem. This question is classically addressed using a relation that states that a failure detector D is stronger (that is, provides "more, or better, information") than a failure detector D' if D can be used to implement D'. It has recently been shown that this classic implementability relation has some drawbacks. To overcome this, different relations have been defined, one of which states that a failure detector D is stronger than D' if D can solve all the time-free problems solvable by D'. In this paper we compare the implementability-based hierarchy of failure detectors to the hierarchy based on solvability. This is done by introducing a new proof technique for establishing the solvability relation. We apply this technique to known failure detectors from the literature and demonstrate significant differences between the hierarchies.
BibTeX
@misc{sastry2014solvability,
  author = {Srikanth Sastry and Josef Widder},
  title = {{Solvability-Based Comparison of Failure Detectors}},
  year = {2014},
  eprint = {1407.3286},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1407.3286},
}

Loading related content...

Figure