Finding Nemo-Nemo : CFT DAG-based Consensus in the WAN
Rithwik Kerur, Pasindu Tennage, Philipp Jovanovic, Dahlia Malkhi, Alberto Sonnino, Igor Zablotchi · 2026
Read Finding Nemo-Nemo : CFT DAG-based Consensus in the WAN by Rithwik Kerur, Pasindu Tennage, Philipp Jovanovic, Dahlia Malkhi, Alberto Sonnino, Igor Zablotchi (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-08914.txt.
Introduction
Kerur and five colleagues present Nemo-Nemo, a working crash fault proof agreement system for wide area networks that bridges crash fault and hostile fault proof design. Command spread through a cause linked DAG lets all copies propose commands with self taming traffic. Multi leader design removes the single leader choke point, and splitting spread from agreement logic rides out stalled commits. Missed deadline bids are by rule delayed, never dropped, and DAG commits in just two network hops match older crash fault latency with far higher throughput.
Catalog record
| CREATOR | Rithwik Kerur, Pasindu Tennage, Philipp Jovanovic, Dahlia Malkhi, Alberto Sonnino, Igor Zablotchi |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 63272 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.08914
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Finding Nemo-Nemo : CFT DAG-based Consensus in the WAN Rithwik Kerur, Pasindu Tennage, Philipp Jovanovic, Dahlia Malkhi, Alberto Sonnino, Igor Zablotchi Abstract This paper introduces Nemo-Nemo, a practical crash-fault tolerant (CFT) consensus protocol designed to outperform existing protocols in wide-area networks by bridging design principles from the CFT and Byzantine-fault tolerant (BFT) worlds. By structuring command propagation through a causally ordered DAG, Nemo-Nemo allows all consensus replicas to propose commands with a naturally self-regulating communication regime. By exploiting multi-leader architecture, Nemo-Nemo avoids the performance bottleneck inherent to single-leader protocols. By separating command dissemination from consensus logic, Nemo-Nemo handles challenging network conditions even when consensus commits are stalled. Moreover, leader proposals that miss a deadline are never dropped, but deterministically deferred and executed later, preserving throughput under transient network delays. And by enabling Nemo-Nemo to commit on a DAG in just two network hops, it matches the latency of existing CFT systems, while achieving significantly higher throughput. The result is a robust, deployable system: the first DAG-based CFT consensus protocol proven to exceed state-of-the-art wide-area network performance in both speed and resilience. 1 Introduction Byzantine fault-tolerant (BFT) consensus systems have seen significant advances, driven by a multi-trillion dollar blockchain industry. These advances have yielded powerful techniques, notably DAG-based consensus architectures, that enable high throughput, low latency, and graceful handling of both failures and network instabilities (e.g., [ 14 , 46 , 25 , 5 ] and others). Meanwhile, crash fault-tolerant (CFT) consensus remains the workhorse for traditional distributed systems, yet has not benefited equally from these innovations. This paper bridges that gap. We argue that CFT systems designed to operate in the WAN can and should adopt lessons from modern BFT consensus, while adapting them to exploit the simpler model of crash-only failures. Specifically: 1. DAG-based architecture: We can boost performance and alleviate network and failure-induced hiccups by adopting the DAG-based approach, which provides a self-regulating mempool and seamless failure recovery. 2. Battle-tested implementations: Rather than building from scratch, we can adapt production-grade BFT codebases to CFT settings. 3. Unstable network testing: Even without Byzantine replicas, we must test CFT systems under unstable network conditions, such as shifting connected majorities and leaders, which partial synchrony alone does not capture. This paper presents Nemo-Nemo , the first DAG-based CFT protocol. Nemo-Nemo applies these principles to achieve the best performance among known CFT protocols in wide-area network settings under both partial synchrony [ 17 ] and random asynchronous network [ 15 ] models. Vision and motivation. Modern DAG-based BFT consensus systems offer two central lessons that form the foundation of Nemo-Nemo . The first is the value of a causally ordered, and self-regulating mempool A mempool functions as a transport layer for disseminating transaction requests, allowing replicas to inject transactions in parallel. In a DAG-based mempool, transactions are bundled into blocks that maintain causal order. This design achieves three goals: (1) it induces a self-regulating, round-based communication pattern where replicas wait for a threshold of blocks before advancing rounds; (2) each block automatically carries its causal history, ensuring consistent DAG views across correct replicas; and (3) progress continues seamlessly despite leader failures, enabling rapid recovery when new leaders are promoted. In principle, any consensus protocol can sit atop such a DAG mempool, and many BFT protocols leverage this idea: Narwhal-HS [ 14 ] integrates HotStuff [ 62 ] with a DAG and achieves roughly a 50\times performance gain over bare HotStuff, while Autobahn [ 20 ] integrates PBFT [ 12 ] with a DAG and similarly attains significant throughput improvements. Beyond a DAG-based mempool alone, the second lesson is that consensus protocols can be embedded directly into the DAG structure by pre-designating a skeleton of leader proposals and treating blocks that reference those proposals as protocol votes [ 6 ] . In this view, much of the logic of traditional consensus protocols collapses into simple structural rules on the DAG. For example, simple and direct commit logic can be realized by f+1 blocks referencing a leader proposal [ 31 , 47 ] . Overview of Nemo-Nemo . For the DAG-mempool, a key design choice concerns whether DAG blocks must be explicitly certified for availability by a quorum before insertion [ 1 ] . Several BFT DAGs, such as Tusk [ 14 ] and Bullshark [ 46 ] , use certified blocks, motivated by the need for non-equivocation and data availability in adversarial environments. However, pre-certifying each block adds communication rounds on top of those required for consensus, increasing latency. Alternative BFT DAGs, including Cordial Miners [ 25 ] and Mysticeti [ 5 ] , avoid pre-certification to reduce latency. Prioritizing low latency, Nemo-Nemo uses non-certified blocks. Note that in CFT settings, equivocation is not a concern, hence the benefit of pre-certification is diminished whereas admitting non-certified blocks enables extremely low-latency. The DAG direct commit rule of Nemo-Nemo is straightforward: a skeleton block becomes directly committed if referenced by f+1 blocks in the next round (see Figure 1 ). The crux is maintaining safety against failures across replicas, each distinctly evolving the DAG due to network scheduling and omissions. When a skeleton slot is not directly committed, it can become indirectly committed by a future skeleton slot using the (causally ordered) DAG structure itself (see Figure 2 ). Notably, there is no explicit view-change by which a future leader may reinstate the proposed block. Rather, a DAG rule, which is somewhat subtle, is employed to indirectly commit or skip the undecided slot; it is detailed in the body of the paper. This design enhances state-of-the-art CFT consensus in several non-obvious respects. First, each round can inject new proposals in the same round as voting, without waiting for confirmation that earlier proposals have committed. Second, each round can rotate leaders while preserving the same structure and latency as a stable-leader regime, without requiring an explicit leader-replacement ( view-change ) protocol. Third, each round may include multiple skeleton slots for proposals, enabling greater flexibility and throughput (see Figure 2 ). An additional advantage becomes apparent under unstable conditions, such as transient network delays. Consensus protocols face a well-known tradeoff when configuring leader timeouts: timeouts that are too short risk discarding correct leader proposals, while timeouts that are too long can stall the system upon leader failure or hang-up. Nemo-Nemo mitigates this tradeoff by enabling shorter leader timeouts without compromising fairness or throughput. Leader proposals are never dropped; instead, they are deferred, typically to the immediately succeeding round, allowing the system to progress smoothly despite temporary leader disruptions. Implementing Nemo-Nemo . To validate our vision, we wanted to employ mature code and optimize it for low latency. We started with Mysticeti, a BFT protocol deployed in production by multiple blockchains [ 48 , 22 , 13 ] . Applying Mysticeti to CFT involved both obvious modifications and structural opportunities that fundamentally improve performance, including the following: (i) changing quorum thresholds from 2f+1 to f+1 , (ii) eliminating an entire communication round and simplifying commit rules to enable Nemo-Nemo to commit on a DAG in just two network hops, like existing CFT systems, (iii) simplifying authentication by removing signatures and integrity checks, thus streamlining command ingestion without Byzantine peer concerns. Unstable Network Testing. Finally, in addition to evaluating