On the Complexity of Fault-Tolerant Consensus

Dariusz R. Kowalski, Jaroslaw MirekNETYS 2019 · DOI

Introduction

In distributed computing, reaching consensus—where $n$ processes agree on a single value despite up to $f$ failures—is a fundamental challenge. The complexity of this task is largely determined by the power of the "adversary," the entity that decides which processes fail and when. Traditionally, research has focused on two extremes: the Strongly-Adaptive adversary, which can crash any process at any time based on full system knowledge, and the Non-Adaptive adversary, which must pre-select victims before the protocol begins.

In "On the complexity of fault-tolerant consensus," Dariusz R. Kowalski and Jarosław Mirek bridge this gap by introducing "Constrained Adversaries." These models, such as the Weakly-Adaptive and $k$-Chain-Ordered adversaries, more accurately reflect real-world system dependencies where failures often follow hierarchical or pre-determined patterns.

Adversary Models and Problem Scope

The difficulty of consensus varies significantly across different failure models:

  1. Strongly-Adaptive: Highly pessimistic, modeling worst-case security threats.
  2. Non-Adaptive: Often too optimistic, failing to account for reactive or targeted attacks.
  3. Weakly-Adaptive (New): The adversary must pre-select the set of victims but can choose the timing of their crashes adaptively during execution.
  4. $k$-Chain-Ordered (New): Failures must follow specific hierarchical paths (e.g., rack-level or switch-level dependencies), where $k$ represents the number of independent failure chains.

Methodology

The authors propose three primary algorithms to address these constrained scenarios:

  • Algorithm A (Iterative Leader Election): This core strategy repeatedly elects a small set of leaders to reach a "small consensus" using randomized protocols. If a process not pre-selected by the adversary becomes a leader, the consensus result is successfully propagated.
  • Algorithm B (Gossip Integration): To optimize message complexity, standard communication is replaced with a deterministic gossip protocol, ensuring efficient information exchange even amidst high failure rates.
  • Algorithm C (Chain-Awareness): Specifically for the $k$-Chain model, this algorithm dynamically adjusts leader election probabilities based on the estimated number of operational processes, preventing the adversary from stalling the protocol.

Key Results

The primary contribution of this work is the derivation of tight upper and lower bounds for these new adversary models. The results demonstrate that constraining the adversary's selection of victims—even if they remain adaptive in timing—allows for significantly faster consensus.

Summary of time complexity bounds for various adversary models.

As shown in the table above, the expected time complexity for the Weakly-Adaptive model is sub-linear, scaling with the ratio of total processes to survivors. In the $k$-Chain-Ordered model, complexity scales with the number of failure paths $k$ rather than the total process count $n$. These results prove that randomization is a powerful tool for overcoming the $f+1$ round barrier inherent in deterministic consensus.

Conclusion

By formalizing intermediate adversary models, Kowalski and Mirek provide a more nuanced understanding of fault tolerance. Their work shows that when failures are constrained by system architecture or pre-selection, consensus can be achieved much more efficiently than worst-case models suggest. Future research may extend these findings to dynamic systems or explore "delayed" adversaries who operate with partial information.

Summary updated

BibTeX
@inproceedings{kowalski2019complexity,
  author = {Dariusz R. Kowalski and Jaroslaw Mirek},
  title = {{On the Complexity of Fault-Tolerant Consensus}},
  booktitle = {NETYS},
  year = {2019},
  doi = {10.1007/978-3-030-31277-0\_2},
}
Figure