Brief Announcement: Reaching Approximate Consensus When Everyone May Crash

Lewis Tseng, Qinzi Zhang, Yifan ZhangDISC 2020 · OpenReview

TL;DR

This paper tackles the challenge of achieving approximate consensus in distributed systems where nodes can crash and recover, and network links are unreliable. They introduce a novel algorithm that requires nodes to store minimal information (just three values: state, phase index, and an n-bit counter) in persistent storage, making it suitable for resource-constrained environments like sensor networks.

What Problem Does This Paper Address?

In distributed systems, achieving consensus – where all non-faulty nodes agree on a value – is fundamental. However, real-world systems are prone to failures. This paper focuses on approximate consensus, where nodes don't need to agree on an exact value, but rather on values within a small tolerance ($\epsilon$). The challenge is amplified by a "weak" system model:

  • Crash-Recovery Model: Nodes can crash permanently (up to $f$ of them) or crash and recover intermittently.
  • Fair-Lossy Links: Network connections can drop messages infinitely often, but eventually, communication between non-faulty nodes will succeed.
  • Limited Persistent Storage: Nodes have a small, fixed amount of storage that survives crashes. This is a crucial constraint, as traditional solutions often rely on unbounded storage to emulate reliable channels.

The authors aim to design an algorithm that achieves approximate consensus under these challenging conditions, specifically for systems with limited resources.

Methods

The core of the paper is a novel algorithm designed for $n \ge 2f + 1$ nodes. Key aspects include:

  • Minimal Persistent Storage: Each node only stores three values:
  • vi: The current value held by the node.
  • pi: The current "phase" the node is in.
  • Ri: An n-bit counter, where Ri[j] = 1 indicates node i has received a message from node j in the current phase.
  • "Jumping" to Future Phases: A significant innovation is that nodes can "jump" to a future phase (line 6 of Algorithm 1) upon receiving a message from a higher phase. This bypasses the need to process messages strictly in order, which is typical in many consensus algorithms and helps overcome the fair-lossy channel.
  • Direct Value Aggregation: Nodes directly add received values to their local state (line 8). This is a space-saving technique compared to methods that might store more complex message histories.
  • Phase-Based Progress: The algorithm progresses through phases. Nodes update their values and advance to the next phase when they have received sufficient information (specifically, when their counter Ri indicates messages from at least $n-f$ nodes).
  • Proof Sketch for $\epsilon$-Agreement: The paper provides a proof sketch for the crucial $\epsilon$-agreement property. It defines sets of states V(p) for each phase p and uses an induction to show that the range of values decreases with each phase, eventually converging to within $\epsilon$. The proof technique is adapted to handle the uncertainty of message delivery.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • The Power of Minimal State: The most striking insight is that approximate consensus can be achieved with an astonishingly small amount of persistent storage. This opens doors for consensus in highly constrained environments.
  • "Jumping" as a Key Enabler: The ability for nodes to "jump" to higher phases is a critical mechanism that allows the algorithm to cope with unreliable channels and asynchronous message arrivals without needing strict ordering.
  • Trade-off Between Space and Complexity: The algorithm achieves its space efficiency by accepting a slightly more complex proof for $\epsilon$-agreement, which needs to account for nodes potentially missing messages.
  • Generalizability: While the paper focuses on crash-recovery, the abstract mentions an extension to Byzantine faults, suggesting the core ideas might be adaptable to even more challenging scenarios.

Key Results

The paper presents an algorithm that achieves approximate consensus under the specified weak model. The key result is the algorithm's ability to satisfy the three conditions of approximate consensus:

  • $\epsilon$-agreement: All non-faulty nodes decide on values within a tolerance $\epsilon$. The paper provides a formula for Pend (the termination phase) that ensures this.
  • Validity: The decided values are within the range of the initial inputs.
  • Termination: All non-faulty nodes eventually decide on a value.

The algorithm's space complexity is highlighted as being very low, requiring only three values (state, phase index, and an n-bit counter) per node in persistent storage.

Limitations and Future Work

  • Proof Complexity: While a proof sketch is provided, the full proof for $\epsilon$-agreement is detailed in a separate technical report. The authors acknowledge that the proof is more complex than in traditional models due to the fair-lossy channels.
  • Byzantine Faults: The paper mentions an extension to Byzantine faults in their technical report, implying that the current algorithm is specifically for crash faults, and further work is needed to fully explore Byzantine scenarios.
  • Specific $\epsilon$ Bound: The paper derives a bound for Pend that ensures $\epsilon$-agreement, but the exact value of $\epsilon$ achieved depends on the initial range of values and the derived decrease rate r. Further analysis might be needed to optimize $\epsilon$ for specific applications.
  • Performance Analysis: While the algorithm is space-efficient, a detailed analysis of its time complexity or message complexity is not the primary focus of this brief announcement.

Summary updated

Abstract

Fault-tolerant consensus is of great importance in distributed systems. This paper studies the asynchronous approximate consensus problem in the crash-recovery model with fair-loss links. In our model, up to f nodes may crash forever, while the rest may crash intermittently. Each node is equipped with a limited-size persistent storage that does not lose data when crashed. We present an algorithm that only stores three values in persistent storage - state, phase index, and a counter.
BibTeX
@inproceedings{tseng2020brief,
  author = {Lewis Tseng and Qinzi Zhang and Yifan Zhang},
  title = {{Brief Announcement: Reaching Approximate Consensus When Everyone May Crash}},
  booktitle = {DISC},
  year = {2020},
  url = {https://openreview.net/forum?id=KwvD0aQ2jH},
}
Figure