Systematic translation of failure-detector-based protocols into the random asynchronous model

The random asynchronous model (Danezis, Komatovic, Kokoris-Kogias, Sonnino, Zablotchi; DISC 2025) replaces the adversarial message scheduler of asynchronous Byzantine systems with a random scheduler: at each step any pending sender-receiver pair is drawn next with probability at least a constant $\mathcal{C}(n,f)>0$. In this model Byzantine consensus is solvable with probabilistic guarantees at resilience thresholds ($n=2f+1$ and $n=f+2$) where it is impossible under partial synchrony, and correct processes can implement $\sim\mathcal{P}$, a heartbeat crash detector that behaves like the classic perfect failure detector with high probability. The paper explicitly leaves open whether protocols designed for synchrony or partial synchrony that rely on the perfect ($\mathcal{P}$) or eventually perfect ($\Diamond\mathcal{P}$) failure detectors can be systematically translated into the random asynchronous model using $\sim\mathcal{P}$, preserving their guarantees w.h.p. without per-protocol, hand-crafted fallback logic. The question is therefore open, with no theorem known in either direction.

Background

In a message-passing system of $n$ processes of which up to $f$ may be Byzantine (arbitrarily faulty, free to send conflicting or fabricated messages), consensus requires every correct process to eventually decide subject to agreement (no two correct processes decide differently), validity (the decision relates to the inputs as specified), and termination. In the fully asynchronous model, delays are unbounded and an adversary controls delivery order; the Fischer–Lynch–Paterson (FLP) impossibility result shows deterministic consensus is then impossible with even one crash fault. Two classical escapes change the environment. Partial synchrony (Dwork, Lynch, Stockmeyer) assumes message delays become bounded after an unknown stabilization time. Failure detectors (Chandra, Toueg) instead augment asynchrony with an oracle outputting lists of suspected processes: the perfect detector $\mathcal{P}$ combines strong completeness (every crashed process is eventually permanently suspected by every correct process) with strong accuracy (no correct process is ever suspected) and is implementable in a synchronous system; the eventually perfect detector $\Diamond\mathcal{P}$ satisfies accuracy only after some finite time and is implementable under partial synchrony. With a sufficiently strong such detector, consensus becomes solvable in asynchrony (crash faults, $n\geq 2f+1$). Danezis, Komatovic, Kokoris-Kogias, Sonnino, and Zablotchi proposed a third escape: the random asynchronous model. Message delays remain unbounded and Byzantine faults are allowed, but delivery follows a random scheduler: at each step a pair $(p,q)$ of processes with a pending message from $p$ to $q$ is drawn and the earliest pending message on that link is delivered, with every pending pair drawn with probability at least a constant $\mathcal{C}(n,f)>0$, so no message can be adversarially starved. Precursors include the round-based fair scheduler of Bracha and Toueg, Aspnes's noisy scheduling in shared memory (an adversary's schedule perturbed randomly, which also makes deterministic consensus achievable), and the random scheduling exploited by the DAG-based Byzantine systems Tusk and Mahi-Mahi — there only in the $n=3f+1$ setting, to improve commit latency. The paper proves that Byzantine consensus is solvable in the random asynchronous model with probabilistic guarantees: with $n=3f+1$ (a regime partial synchrony also attains), deterministic safety and probabilistic termination; at the thresholds impossible under partial synchrony, with $n=2f+1$, deterministic termination with safety holding with high probability (w.h.p., i.e., the probability of violating it is negligible: it approaches $0$ exponentially in some parameter of the algorithm, for fixed $n$ and $f$); with $n=f+2$, weak validity with w.h.p. agreement — complemented by impossibility results (e.g., no protocol achieves deterministic validity, agreement, and termination if even one process may crash). The engine of these results is an exchange lemma: after $R$ rounds of all-to-all communication, every pair of correct processes has exchanged at least one message with probability $1-\exp(-\Omega(R))$, so $R$ random-asynchronous rounds simulate one synchronous round w.h.p. This lets correct processes implement the crash-fault detector $\sim\mathcal{P}$ by heartbeats (suspect $q$ iff no heartbeat from $q$ in the last $R$ rounds): strong completeness always holds, while strong accuracy holds only w.h.p., with false-suspension probability decaying exponentially in $R$. The detector resembles $\mathcal{P}$ in synchrony and $\Diamond\mathcal{P}$ in partial synchrony — which raises the open question: can the extensive literature of protocols proven correct in synchrony or partial synchrony using $\mathcal{P}$ or $\Diamond\mathcal{P}$ be carried over to the random asynchronous model automatically, or is the deterministic-to-probabilistic downgrade a fundamental obstruction?

Problem Statement

Determine whether protocols designed for synchrony or partial synchrony that rely on the perfect failure detector $\mathcal{P}$ or the eventually perfect failure detector $\Diamond\mathcal{P}$ can be systematically translated into the random asynchronous model using the heartbeat-implemented detector $\sim\mathcal{P}$, preserving their guarantees with high probability. As in the source, $\sim\mathcal{P}$ is a crash-fault detector implemented in the random asynchronous model, in which up to $f$ processes may be Byzantine: strong completeness holds deterministically and strong accuracy holds only w.h.p. The protocols the question targets are those whose guarantees — classically, crash-fault-tolerant consensus in asynchrony with $n\geq 2f+1$ — are proven in their native synchronous or partially synchronous setting, and the translation is required to preserve those guarantees w.h.p. A translation is systematic in the sense at issue in the source if it avoids the manual, algorithm-specific fallback logic that the direct translation (replacing each synchronous round with $R$ random-asynchronous rounds) would otherwise need for the low-probability outlier executions in which the deterministic guarantee of hearing from a common subset of at least $n-f$ processes fails and the translated algorithm's invariants would be violated. This question is posed explicitly by Danezis et al. (DISC 2025), who conjecture informally that a systematic translation is unlikely, since downgrading deterministic communication guarantees to hold only w.h.p. could break arbitrary internal algorithm invariants; no theorem is known in either direction.

References

1. George Danezis, Jovan Komatovic, Lefteris Kokoris-Kogias, Alberto Sonnino, Igor Zablotchi. Byzantine Consensus in the Random Asynchronous Model. In Proceedings of the 39th International Symposium on Distributed Computing (DISC 2025), LIPIcs, pages 28:1–28:22, 2025. DOI: 10.4230/LIPIcs.DISC.2025.28, https://doi.org/10.4230/LIPIcs.DISC.2025.28; also arXiv:2502.09116 (v1 Feb 2025, v2 May 2025). DOI: 10.48550/arXiv.2502.09116, https://arxiv.org/abs/2502.09116
2. Tushar Deepak Chandra, Sam Toueg. Unreliable failure detectors for reliable distributed systems. Journal of the ACM 43(2):225–267, 1996. DOI: 10.1145/226643.226647, https://doi.org/10.1145/226643.226647
3. Michael J. Fischer, Nancy A. Lynch, Michael S. Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM 32(2):374–382, 1985. DOI: 10.1145/3149.214121, https://doi.org/10.1145/3149.214121
4. Cynthia Dwork, Nancy Lynch, Larry Stockmeyer. Consensus in the presence of partial synchrony. Journal of the ACM 35(2):288–323, 1988. DOI: 10.1145/42282.42283, https://doi.org/10.1145/42282.42283
5. Gabriel Bracha, Sam Toueg. Asynchronous consensus and broadcast protocols. Journal of the ACM 32(4):824–840, 1985. DOI: 10.1145/4221.214134, https://doi.org/10.1145/4221.214134
6. James Aspnes. Fast deterministic consensus in a noisy environment. Journal of Algorithms 45(1):16–39, 2002. DOI: 10.1016/S0196-6774(02)00220-1, https://doi.org/10.1016/S0196-6774(02)00220-1
7. Philipp Jovanovic, Lefteris Kokoris-Kogias, Bryan Kumara, Alberto Sonnino, Pasindu Tennage, Igor Zablotchi. Mahi-Mahi: Low-Latency Asynchronous BFT DAG-Based Consensus. In Proceedings of the 2025 IEEE International Conference on Distributed Computing Systems (ICDCS 2025), pages 549–559, 2025. DOI: 10.1109/ICDCS63083.2025.00060, https://doi.org/10.1109/ICDCS63083.2025.00060; also arXiv:2410.08670, 2024. DOI: 10.48550/arXiv.2410.08670, https://arxiv.org/abs/2410.08670
8. Michael Yiqing Hu, Alvin Hong Yao Yan, Jialin Li. Amortized Asynchronous Byzantine Reliable Broadcast with Optimal Resilience. arXiv:2605.10372, 2026. DOI: 10.48550/arXiv.2605.10372, https://arxiv.org/abs/2605.10372
9. Zeta Avarikioti, Eleftherios Kokoris-Kogias, Ray Neiheiser, Christos Stefo. CoBRA: A Universal Strategyproof Confirmation Protocol for Quorum-based Proof-of-Stake Blockchains. arXiv:2503.16783, 2025. DOI: 10.48550/arXiv.2503.16783, https://arxiv.org/abs/2503.16783
10. Rithwik Kerur, Pasindu Tennage, Philipp Jovanovic, Dahlia Malkhi, Alberto Sonnino, Igor Zablotchi. Finding Nemo-Nemo: CFT DAG-based Consensus in the WAN. arXiv:2604.08914, 2026. DOI: 10.48550/arXiv.2604.08914, https://arxiv.org/abs/2604.08914
11. Giulio Segalini, Yigit Çolakoğlu, Marko Putnik, Jérémie Decouchant. Tilikum: Transaction Fair Ordering on a DAG without Weak Edges. arXiv:2606.27250, 2026. DOI: 10.48550/arXiv.2606.27250, https://arxiv.org/abs/2606.27250