Finding Nemo-Nemo: CFT DAG-based Consensus in the WAN
arXiv:2604.08914v1 [cs.DC] 10 Apr 2026
Rithwik Kerur∗ UCSB [email protected] Dahlia Malkhi UCSB [email protected]
Pasindu Tennage∗ Digital Asset and EPFL [email protected] Alberto Sonnino Mysten Labs and UCL [email protected]
Igor Zablotchi Mysten Labs [email protected]
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.
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
Philipp Jovanovic Mysten Labs and UCL [email protected]
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× performance gain over bare HotStuff, while Autobahn [20] integrates PBFT [12] with a DAG and similarly attains significant throughput improvements.
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., [5, 14, 25, 46] 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: ∗ Equal contribution.
1
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 𝑓 + 1 blocks referencing a leader proposal [31, 47].
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 [13, 22, 48]. Applying Mysticeti to CFT involved both obvious modifications and structural opportunities that fundamentally improve performance, including the following: (i) changing quorum thresholds from 2 𝑓 + 1 to 𝑓 + 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.
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 𝑓 + 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
Unstable Network Testing. Finally, in addition to evaluating performance under standard, partial synchrony conditions, we address an existing gap in the evaluation methodology for CFT consensus systems. Existing CFT systems are designed to cope with a minority of stragglers, progressing rather well with a stable, well-connected majority. However, they suffer a performance degradation when network conditions are unstable and the fast majority is constantly “shifting”. To address this, in addition to traditional evaluations, we developed a framework to evaluate protocols under a recently proposed random asynchronous model, which assumes message delivery delays are random but not adversarially controlled. This model captures realistic network variability—where packets may be delayed or reordered—without assuming malicious nodes. Importantly, this model reveals performance characteristics invisible under standard partial synchrony assumptions, where protocols are typically evaluated with stable, low-latency networks. We detail how we simulate this network model in Section 6 Our evaluations demonstrate that existing CFT protocols behave quite differently under randomized network delays compared to stable networks. Nemo-Nemo, by contrast, maintains robust performance across both settings.This validates our motivating insight: by decoupling block propagation from consensus, Nemo-Nemo remains robust under the random asynchronous model as the DAG continues to grow even in the absence of commits. It contrasts with traditional CFT protocols, which couple these processes, forcing block production to halt until consensus is achieved. Contributions. We summarize our contributions as follows: • We present Nemo-Nemo, the first DAG-based CFT consensus protocol. Nemo-Nemo achieves the best performance among known CFT protocols in WAN settings under both partial synchrony and random asynchronous network models. • We show how, unlike traditional CFT protocols that require explicit view-change mechanisms, Nemo-Nemo integrates leader rotation and multi-proposer rounds di2
rectly into the DAG structure, eliminating protocol complexity and latency overhead.
to commit, but relaxes the worst-case adversarial scheduling of the classic asynchronous model [7, 34], where an adversary can control the message schedule indefinitely.
• We exploit CFT’s lack of equivocation to admit noncertified blocks into the DAG, achieving commit latencies unattainable in BFT settings. This design choice, along with optimized commit rules and block ingestion, enables Nemo-Nemo to commit in just two network hops, like existing CFT systems, while achieving a significantly higher saturation throughput of at least 2x.
3
Nemo-Nemo operates in two logical layers: (i) a data dissemination layer that propagates client transactions through a structured DAG (this section); and (ii) an ordering layer interpreting the DAG to derive a total order of transactions (see Section 4).
• In addition to the standard partially synchronous model, we also evaluate Nemo-Nemo under the random asynchronous model, which models unstable network conditions. Our results show that existing CFT protocols degrade significantly under this model, while NemoNemo maintains robust performance.
2
The Nemo-Nemo DAG: Data Dissemination
3.1
Block creation
Replicas operate in a sequence of logical rounds, and in each round, every replica proposes a unique block. During a round, replicas receive transactions from clients and blocks from other replicas. Clients submit transactions to a replica, which includes them in its (next) block. If a transaction does not finalize quickly enough, the client simply resubmits it to a different replica. Each block references blocks from prior rounds, starting with the author’s most recent block, and includes fresh transactions not yet included in preceding blocks. Specifically, a block contains at least the following elements: (1) the author 𝐴 of the block; (2) a round number 𝑅; (3) a list of transactions; and (4) at least 𝑓 + 1 distinct references to blocks from the previous round 𝑅 − 1, as well as any additional references from earlier rounds, for which the replica has already downloaded the complete causal history. At the core of Nemo-Nemo is a round-based DAG structure where each vertex is a block. Each replica maintains a local view of the DAG, adding a block once it has downloaded its entire causal history. Consequently, all correct replicas eventually converge on the same DAG view.
System Model and Assumptions
Nemo-Nemo is a peer-to-peer message-passing system which implements atomic broadcast [10], with the following properties: (1) Validity: If a correct replica 𝑝 proposes a value 𝑣, then 𝑝 eventually commits 𝑣; (2) No duplication: No value is committed more than once; (3) No creation: If a replica commits a value 𝑣 with proposer 𝑠, then 𝑣 was previously proposed by replica 𝑠; (4) Agreement: If a value 𝑣 is committed by some correct replica, then 𝑣 is eventually committed by every correct replica; (5) Total order: Let 𝑣 1 and 𝑣 2 be any two values and suppose 𝑝 and 𝑞 are any two correct replicas that commit 𝑣 1 and 𝑣 2 . If 𝑝 commits 𝑣 1 before 𝑣 2 , then 𝑞 commits 𝑣 1 before 𝑣 2 . In the random asynchronous model, validity and agreement are satisfied with probability 1 (almost surely). Fault model. Nemo-Nemo follows the standard CFT assumptions used in prior work [27, 40]. The system consists of 𝑛 = 2 𝑓 + 1 replicas, of which at most 𝑓 may crash. A replica is correct if it follows the protocol and crashed otherwise.
3.2
Inclusive block proposing
Unlike traditional leader-based consensus protocols, where only leaders propose values, in Nemo-Nemo all replicas, leaders or not, propose values in each round. In each round, a subset of replicas known to everyone is pre-designated as skeleton nodes. Skeleton nodes are akin to leaders (possibly multiple ones per view, as in multi-leader protocols). That is, blocks by skeleton nodes drive progress in the protocol: they can become directly committed, and they determine the commit decisions for blocks they causally reference, as described in the ordering layer (see Section 4). A replica disseminates its block only after receiving (in addition to 𝑓 + 1 blocks from the previous round, also) all skeleton blocks from the previous round, or after a timeout expires. This ensures liveness once the system becomes synchronous (see Supplementary Material).
Network model. We analyze and evaluate Nemo-Nemo under two network models: the standard partial synchrony model and the more recent random asynchronous model. Links between correct parties behave reliably, and messages among them eventually arrive. In the partially synchronous model, we assume the standard Global Stabilization Time (GST) used throughout related work. After GST, every message sent among correct parties arrives within Δ time. Before GST, the protocol operates in a fully asynchronous network where messages eventually arrive but no bound limits their delay. Although Nemo-Nemo operates in the CFT setting, it is designed to operate in a more unstable environment prone to network instabilities. To model this, we employ the random asynchronous model [15] which assumes that message delivery follows a random schedule. The random asynchronous model strikes a midpoint between the partially synchronous and fully asynchronous settings: it does not rely on synchronous periods
Random Asynchronous Model. This model assumes that the first 𝑓 + 1 blocks received by a replica in a round 𝑅 constitute a random sample. We discuss the implementation of this mechanism in Section 6 and prove that Nemo-Nemo is live with probability 1 under this model (see Section 5.2). 3
R
R+1
N0
P0
D0
N0
P0
P0
P0
N1
P1
D1
N1
P1
P1
P1
R
R
R+2
N0
S0a
N1 N2
P2
D2
propose
decide
N2
P2
wave 1
P2
R+1
R+2
R+3
R+4
S2a
S1b
S3a
P2
N2
wave 2
S0b
S1a
S2b
Figure 1: The structure of the Nemo-Nemo DAG. Left: The structure of a wave, consisting of two rounds (Propose and Decide). Right: Waves patterns in the Nemo-Nemo protocol (each round starts a new overlapping wave).
Figure 2: Example execution with three replicas and two skeleton slots per round. Skeleton blocks are classified as commit (green), skip (red), or undecided (grey). Thick arrows signify commits via the indirect decision rule.
4
trates an example of a Nemo-Nemo DAG with three replicas, (𝑁0 , 𝑁1 , 𝑁2 ), two skeleton slots per round, and a potential skeleton slot ordering represented as (𝑆0𝑎 , 𝑆0𝑏 ) and (𝑆1𝑎 , 𝑆1𝑏 ) for the first and second rounds, respectively.
The Nemo-Nemo Consensus Protocol
By itself, the DAG layer described in Section 3 functions as a scalable data dissemination layer. It grows with the network and ensures that all disseminated transactions are reliably available. However, a consensus layer is required to order transactions. Nemo-Nemo integrates this layer logically into the DAG messages, rather than sending separate consensus messages, and infers decisions directly from the DAG itself.
4.1
4.2
The Nemo-Nemo decision rule
We present the decision rule of Nemo-Nemo leveraging an example protocol run depicted in Figure 2. In this example, we refer to blocks using the notation 𝐵 ( 𝑁𝑖 ,𝑅) , where 𝑁𝑖 is the issuing replica and 𝑅 is the block’s round. All skeleton slots are initially in the undecided state. The replica holds the portion of the DAG depicted in Figure 2 and attempts to classify as many blocks in the skeleton slots as possible as either commit or skip.
Identifying DAG patterns
Nemo-Nemo leverages patterns in the DAG structure to define its decision rules. Rounds and waves. Figure 1 (left) shows an example of a Nemo-Nemo DAG with three replicas, (𝑁0 , 𝑁1 , 𝑁2 ). NemoNemo defines a wave of two rounds for every block. The first round 𝑅 (Propose) includes the blocks that the wave attempts to commit (𝑃0 , 𝑃1 , 𝑃2 ). The second round 𝑅 + 1 (Decide) includes the blocks (𝐷 0 , 𝐷 1 , 𝐷 2 ) implicitly acting as “votes” [27] determining the blocks of the previous round to commit. Figure 1 (right) shows that Nemo-Nemo initiates a new wave every round, with two consecutive waves always overlapping by one round. Put differently, each round starts a new wave. Algorithm 2 (Section 4.2) formally defines a wave.
Step 1: Direct decision rule. To start the classification process, the replica processes each slot individually, starting with the highest (𝑆3𝑎 ), applying the Nemo-Nemo direct decision rule. The replica classifies a block 𝐵 in a slot as commit if it observes 𝑓 + 1 blocks (i.e., two blocks in our example) from the subsequent round referencing it. Otherwise, the replica leaves the slot as undecided (for now). This rule is formally described by the function TryDirectDecide in Algorithm 2. In Figure 2, the replica targets 𝑆3𝑎 first. It observes that 𝐵 ( 𝑁0 ,𝑅+4) and 𝐵 ( 𝑁1 ,𝑅+4) reference it. Therefore, it classifies 𝑆3𝑎 as commit. Section 7 shows that this scenario is the most common (in the absence of an asynchronous adversary) and results in the lowest latency. Blocks 𝑆2𝑎 , 𝑆1𝑏 , and 𝑆0𝑎 are also classified as commit as they each have 𝑓 + 1 references from the subsequent round.
Skeleton slots. A skeleton slot (or simply “a slot”) is a tuple (replica, round) and can be either empty or contain the replica’s proposal for the respective round. The slot can assume one of three states: commit, skip, or undecided. All slots are initially set to undecided and the goal of the protocol is to classify them as commit or skip. The number of skeleton slots instantiated per round can be configured, and for systems with few faults, it can be as high as 𝑛 so that every block has a chance to commit in two steps. It can also be dynamically adjusted based on the network conditions, following a similar deterministic approach to HammerHead [55]. The protocol is initialized with a deterministic total order among skeleton slots, known to all replicas. Within a single round, this ordering may reflect a fixed (e.g., round robin) or a variable regime per round. Figure 2 illus-
Step 2: Indirect decision rule. In the case where the direct decision rule cannot classify a skeleton slot 𝐵 ( 𝑁𝑖 ,𝑅) , the replica uses the Nemo-Nemo indirect decision rule. This rule looks at future slots to decide about the current one. First, it finds an anchor. This is the earliest non-skipped skeleton slot with a round number 𝑅 ′ > 𝑅 + 1 that is either still classified as undecided or already classified as commit. Recall that slots are totally-ordered, so the anchor is uniquely defined regardless of how the DAG evolves at different replicas. If the anchor is 4
Algorithm 1 Nemo-Nemo
undecided, the replica marks the current slot as undecided. If the anchor is commit, the replica checks if it indirectly references the target slot, that is, it checks whether there is a path between the anchor and the target skeleton slot. If it does, the replica marks the target slot as commit. If it does not, the replica marks it as skip. This rule is formally described by the function TryIndirectDecide in Algorithm 2. Section 5 shows that the direct and indirect decision rules are consistent: if one replica directly commits a block, no honest replicas will indirectly skip it (and vice versa).
1: leadersPerRound 2: waveLength = 2
⊲ A number between 1 and 2 𝑓 + 1
3: procedure TryDecide(𝑟𝑐𝑜𝑚𝑚𝑖𝑡𝑡𝑒𝑑 , 𝑟ℎ𝑖𝑔ℎ𝑒𝑠𝑡 ) 4: 𝑆←[] ⊲ Holds decisions 5: for 𝑟 ← 𝑟ℎ𝑖𝑔ℎ𝑒𝑠𝑡 down to 𝑟𝑐𝑜𝑚𝑚𝑖𝑡𝑡𝑒𝑑 + 1 do 6: for 𝑙 ← leadersPerRound − 1 down to 0 do 7: 𝑖 ← 𝑟 mod waveLength 8: 𝐷 ← Decider(𝑖, 𝑙 ) 9: 𝑤 ← 𝐷.WaveNumber(𝑟 ) 10: 𝑠 ← 𝐷.TryDirectDecide(𝑤 ) 11: if 𝑠 = ⊥ then 𝑠 ← 𝐷.TryIndirectDecide(𝑤, 𝑆 ) 12: 𝑆←𝑠 ∥ 𝑆 13: return 𝑆
In this example, the replica fails to classify 𝑆2𝑏 , 𝑆1𝑎 , and 𝑆0𝑏 using the direct decision rule and thus searches for their respective anchors. The status of the anchor of 𝑆2𝑏 is still undecided; the replica thus marks 𝑆2𝑏 as undecided. Eventually, the DAG will grow and a block with round 𝑅 ′ > 𝑅 + 3 will become the anchor for 𝑆2𝑏 . For the moment however, 𝑆2𝑏 remains undecided. 𝑆3𝑎 is the anchor for 𝑆1𝑎 ; since 𝑆3𝑎 has a path to 𝑆1𝑎 (marked with thick arrows), the replica classifies 𝑆1𝑎 as commit. The anchor of 𝑆0𝑏 is 𝑆2𝑎 which does not have a path to 𝑆0𝑏 . Thus, the replica classifies 𝑆0𝑏 as skip.
14: procedure ExtendCommitSequence(𝑟𝑐𝑜𝑚𝑚𝑖𝑡𝑡𝑒𝑑 , 𝑟ℎ𝑖𝑔ℎ𝑒𝑠𝑡 ) 15: 𝑆 ← TryDecide(𝑟𝑐𝑜𝑚𝑚𝑖𝑡𝑡𝑒𝑑 , 𝑟ℎ𝑖𝑔ℎ𝑒𝑠𝑡 ) 16: 𝑆𝑐𝑜𝑚𝑚𝑖𝑡 ← [ ] ⊲ Holds committed blocks 17: for 𝑠 ∈ 𝑆 do 18: if 𝑠 = ⊥ then break 19: if 𝑠 = Commit (𝑏𝑙𝑒𝑎𝑑𝑒𝑟 ) then 𝑆𝑐𝑜𝑚𝑚𝑖𝑡 ← 𝑆𝑐𝑜𝑚𝑚𝑖𝑡 ∥ 𝑏𝑙𝑒𝑎𝑑𝑒𝑟 20: return LinearizeSubDags(𝑆𝑐𝑜𝑚𝑚𝑖𝑡 ) ⊲ Commit returned blocks
5
Correctness
In this section, we prove that Nemo-Nemo guarantees the properties of atomic broadcast.
5.1
Step 3: Skeleton slots sequence. After processing all slots, the replica derives an ordered sequence of the blocks contained in the skeleton slots. It then iterates over this sequence, committing all slots marked as commit and skipping all slots marked as skip. This process continues until the replica encounters the first undecided slot. As shown in Section 5 this commit sequence is safe, and eventually, all slots will be classified as either commit or skip. In the example shown in Figure 2, the skeleton block output by the replica is [𝑆0𝑎 , 𝑆1𝑎 , 𝑆1𝑏 , 𝑆2𝑎 ]. Since 𝑆2𝑏 remains undecided, it is not included in the sequence and 𝑆3𝑎 is also excluded.
Safety proofs
Lemma 1. If in round 𝑅, 𝑓 + 1 blocks from distinct replicas vote for a block 𝐵, then all blocks at future rounds 𝑅 ′ > 𝑅 will have a path to 𝐵. Proof. We prove the lemma by induction on 𝑅 ′ . The base case is 𝑅 ′ = 𝑅 + 1. Let 𝐵′ be a block at round 𝑅 ′ . Since 𝐵′ points to 𝑓 + 1 blocks at round 𝑅, by quorum intersection, 𝐵′ must point to at least one of the blocks that vote for 𝐵, and thus have a path to 𝐵. For the induction case, assume the lemma holds up to round 𝑅 ′ and consider the case of round 𝑅 ′ + 1. Let 𝐵′ be a block at round 𝑅 ′ + 1. By the induction hypothesis, 𝑓 + 1 blocks at round 𝑅 ′ have paths to 𝐵. Since 𝐵′ points to 𝑓 + 1 blocks from round 𝑅 ′ , by quorum intersection, 𝐵′ must point to at least one block that has a path to 𝐵. □
Step 4: Commit sequence. Following the approach introduced by DagRider [24], the replica determines a linear ordering of all the blocks within the sub-DAG defined by each skeleton block, including previously skipped skeleton blocks (if they are reachable), by performing a depth-first search. If a previous skeleton slot has already linearized a block, it is not re-linearized. The replica processes skeleton slots sequentially, ensuring that all blocks are included in the final commit sequence in the correct order, according to their causal dependencies. The procedure LinearizeSubDags of Algorithm 3 formally describes this linearization process.
Lemma 2. If a replica directly commits some block in a slot 𝑆, then no other replica skips slot 𝑆. Proof. Assume by contradiction that a replica 𝑁 directly commits block 𝐵 in slot 𝑆 while another replica 𝑁 ′ decides to skip 𝑆. Let 𝑅 be the round of 𝑆. Since 𝑁 directly commits 𝐵, there exist 𝑓 + 1 votes for 𝐵 at 𝑆. Therefore, by Lemma 1, all blocks at rounds 𝑅 ′ > 𝑅, including the anchor of 𝑆, have a path to 𝐵 at 𝑆. Thus, 𝑁 ′ cannot decide to skip 𝑆 using the indirect decision rule. We have reached a contradiction. □
In this example, 𝑆0𝑎 and 𝑆0𝑏 do not define any sub-DAG (because the example begins at round 𝑅) and are thus directly added to the commit sequence. Next, 𝑆1𝑎 defines the subDAG {𝐿 1𝑎 , 𝐵 ( 𝑁1 ,𝑅) , 𝐿 0𝑏 }, which is linearized as [𝐵 ( 𝑁1 ,𝑅) , 𝑆0𝑏 , 𝑆1𝑎 ]. The replica continues this process for each skeleton, linearizing the sub-DAGs defined by 𝑆1𝑏 as [𝑆1𝑏 ], since both 𝑆0𝑎 and 𝐵 ( 𝑁1 ,𝑅) are already part of the commit sequence, and so forth. The final commit sequence is [ 𝑆0𝑎 , 𝐵 ( 𝑁1 ,𝑅) , 𝑆1𝑎 , 𝑆1𝑏 , 𝐵 ( 𝑁0 ,𝑅+1) , 𝑆2𝑎 ].
Observation 1. If a slot 𝑆 is committed at two replicas, then 𝑆 contains the same block at both replicas. Proof. This follows, by construction, from two facts: (1) the sequence of skeleton slots is predetermined and known to all replicas, (2) replicas propose at most one block per slot. □ 5
Algorithm 2 Decider Instance 1: waveOffset = 𝑖 2: leaderOffset = 𝑙 3: waveLength = 2
Algorithm 3 Helper Functions 1: nodes
⊲ The first parameter of the Decider (i) ⊲ The second parameter of the Decider (l)
⊲ The set of nodes
2: procedure GetDecisionBlocks(𝑤 ) 3: 𝑟𝑑𝑒𝑐𝑖𝑠𝑖𝑜𝑛 ←DecisionRound(𝑤 ) 4: return 𝐷 𝐴𝐺 [𝑟𝑑𝑒𝑐𝑖𝑠𝑖𝑜𝑛 ]
4: procedure WaveNumber(𝑟 ) 5: return (𝑟 − waveOffset )/waveLength
5: procedure GetLeaderBlock(𝑤, 𝑟 𝑎𝑛𝑘 ) 6: 𝑟 𝑝𝑟𝑜 𝑝𝑜𝑠𝑒 ←ProposeRound(𝑤 ) 7: 𝑙𝑒𝑎𝑑𝑒𝑟 ← nodes [ (𝑟 𝑝𝑟𝑜 𝑝𝑜𝑠𝑒 + 𝑟 𝑎𝑛𝑘 ) mod | nodes | ] 8: if ∃𝑏 ∈ 𝐷 𝐴𝐺 [𝑟 𝑝𝑟𝑜 𝑝𝑜𝑠𝑒 ] s.t. 𝑏.𝑎𝑢𝑡 ℎ𝑜𝑟 = 𝑙𝑒𝑎𝑑𝑒𝑟 then return 𝑏 9: else return ⊥
6: procedure ProposeRound(𝑤 ) 7: return (𝑤 · waveLength ) + waveOffset 8: procedure DecisionRound(𝑤 ) 9: return ProposeRound(𝑤 )+( waveLength − 1)
10: procedure IsLink(𝑏𝑛𝑒𝑤 , 𝑏𝑜𝑙𝑑 ) 11: return ∃ a sequence of 𝑘 ∈ N blocks 𝑏1 , . . . , 𝑏 𝑘 s.t. Ð
10: procedure SupportedLeader(𝑤, 𝑏𝑙𝑒𝑎𝑑𝑒𝑟 ) 11: 𝐵𝑑𝑒𝑐𝑖𝑠𝑖𝑜𝑛 ← GetDecisionBlocks(𝑤 ) 12: return | {𝑏′ ∈ 𝐵𝑑𝑒𝑐𝑖𝑠𝑖𝑜𝑛 : IsLink(𝑏′ , 𝑏𝑙𝑒𝑎𝑑𝑒𝑟 ) } | ≥ 𝑓 + 1
𝑏1 = 𝑏𝑜𝑙𝑑 ∧ 𝑏 𝑘 = 𝑏𝑛𝑒𝑤 ∧ ∀ 𝑗 ∈ [2, 𝑘 ] : 𝑏 𝑗 ∈ 𝑏 𝑗 . 𝑝𝑎𝑟 𝑒𝑛𝑡 𝑠
𝑟 ≥1 𝐷 𝐴𝐺 [𝑟 ] ∧ 𝑏 𝑗 −1 ∈
13: procedure TryDirectDecide(𝑤 ) 14: 𝑏𝑙𝑒𝑎𝑑𝑒𝑟 ← GetLeaderBlock(𝑤 , leaderOffset) 15: if SupportedLeader(𝑤, 𝑏𝑙𝑒𝑎𝑑𝑒𝑟 ) then return Commit (𝑏𝑙𝑒𝑎𝑑𝑒𝑟 ) 16: else return ⊥
12: procedure LinearizeSubDags( 𝐿 ) 13: 𝑂←[ ] ⊲ Hold output sequence 14: for 𝑏𝑙𝑒𝑎𝑑𝑒𝑟 ∈ 𝐿 do Ð 15: 𝐵 ← {𝑏 ∈ 𝑟 ≥1 𝐷 𝐴𝐺 [𝑟 , ∗] s.t. IsLink (𝑏, 𝑏𝑙𝑒𝑎𝑑𝑒𝑟 ) ∧ 𝑏 ∉ 𝑂 ∧
17: procedure TryIndirectDecide(𝑤, 𝑆 ) 18: 𝑟𝑑𝑒𝑐𝑖𝑠𝑖𝑜𝑛 ←DecisionRound(𝑤 ) 19: 𝑠𝑎𝑛𝑐ℎ𝑜𝑟 ← first 𝑠 ∈ 𝑆 s.t. 𝑟𝑑𝑒𝑐𝑖𝑠𝑖𝑜𝑛 < 𝑠.𝑟 𝑜𝑢𝑛𝑑 ∧ 𝑠 ≠ Skip 20: if 𝑠𝑎𝑛𝑐ℎ𝑜𝑟 = Commit (𝑏𝑎𝑛𝑐ℎ𝑜𝑟 ) then 21: 𝑏𝑙𝑒𝑎𝑑𝑒𝑟 ← GetLeaderBlock(𝑤 , leaderOffset) 22: if Link (𝑏𝑎𝑛𝑐ℎ𝑜𝑟 , 𝑏𝑙𝑒𝑎𝑑𝑒𝑟 ) then return Commit (𝑏𝑙𝑒𝑎𝑑𝑒𝑟 ) 23: else return Skip 24: return ⊥
16: 17: 18:
𝑏 not already output } for 𝑏 ∈ 𝐵 in any deterministic order do 𝑂 ← 𝑂 || 𝑏 return 𝑂
committed as part of a lower slot’s causal history. In this case, we say 𝐵 is committed at slot 𝑆, or committed with block 𝐿. Lemma 4. If a block 𝐵 is committed by two replicas 𝑁 and 𝑁 ′ , then 𝐵 is committed at the same slot 𝑆, and 𝐵 is committed with the same skeleton block 𝐿, at both 𝑁 and 𝑁 ′ .
We say that a slot 𝑆 is decided at a replica 𝑁 if 𝑆 is committed or skipped. Otherwise, 𝑆 is undecided. Lemma 3. If a slot 𝑆 is decided at two replicas 𝑁 and 𝑁 ′ , then either both replicas commit 𝑆, or both replicas skip 𝑆.
Proof. Let 𝑆 be the slot at which 𝐵 is committed at replica 𝑁, and 𝐿 the corresponding skeleton block in 𝑆, also at replica 𝑁. Consider now the slot 𝑆 ′ at which 𝐵 is committed at replica 𝑁 ′ , and 𝐿 ′ the corresponding skeleton block. Assume by contradiction that 𝑆 ′ ≠ 𝑆. If 𝑆 ′ < 𝑆, then 𝑁 would have also committed 𝐵 at slot 𝑆 ′ , since by Observation 1, they must commit the same skeleton blocks in the same slots, so 𝑁 could not have committed 𝐵 again at slot 𝑆; a contradiction. Similarly, if 𝑆 < 𝑆 ′ , then 𝑁 ′ would have already committed 𝐵 at slot 𝑆, since by Observation 1 𝑁 and 𝑁 ′ must have committed the same block in slot 𝑆; contradiction. Thus, it must be that 𝑆 = 𝑆 ′ , and by Observation 1, 𝐿 = 𝐿 ′ . □
Proof. Assume by contradiction that there exists a slot 𝑆 such that 𝑁 and 𝑁 ′ decide differently at 𝑆. We consider a finite execution prefix and assume wlog that 𝑆 is the highest slot at which 𝑁 and 𝑁 ′ decide differently (★). Further assume wlog that 𝑁 commits 𝑆 and 𝑁 ′ skips 𝑆. By Lemma 2, neither 𝑁 nor 𝑁 ′ could have used the direct decision rule for 𝑆; they must both have used the indirect rule. Consider now the anchor of 𝑆: 𝑁 and 𝑁 ′ must agree on which slot is the anchor of 𝑆, since by our assumption (★) above, they make the same decisions for all slots higher than 𝑆, including the anchor of 𝑆. Let 𝑆 ′ be the anchor of 𝑆; 𝑆 ′ must be committed at both 𝑁 and 𝑁 ′ . Thus, by Observation 1, 𝑁 and 𝑁 ′ commit the same block 𝐵′ at 𝑆 ′ . But then 𝑁 and 𝑁 ′ cannot reach different decisions about slot 𝑆 using the indirect decision rule, a contradiction. □
We can now prove the main safety properties of NemoNemo: total order, no duplication, and no creation. Theorem 1 (Total Order). Nemo-Nemo satisfies the total order property of Atomic Broadcast.
We have proven the consistency of replicas’ commit sequences: replicas commit (or skip) the same skeleton blocks, in the same order. However, we are not done: we also need to prove that non-skeleton blocks are committed in the same order by replicas. We show this next.
Proof. This property follows immediately from Lemma 4 and the fact that replicas order the causal histories of committed blocks using the same deterministic function, and commit blocks in this order. □ Theorem 2 (No duplication). Nemo-Nemo satisfies the no duplication property of Atomic Broadcast.
Causal history and commit conditions. Consider a replica 𝑁. We call the causal history of a block 𝐵 in 𝑁’s DAG, the transitive closure of all blocks referenced by 𝐵 in 𝑁’s DAG, including 𝐵 itself. In Nemo-Nemo, a block 𝐵 is committed by a replica 𝑁 if (1) there exists a committed skeleton block 𝐿 in 𝑁’s DAG such that 𝐵 is in 𝐿’s causal history (2) all skeleton slots up to 𝐿 are decided in 𝑁’s DAG and (3) 𝐵 has not been
Proof. This is by construction: a block 𝐵 is committed as part of the causal history of a committed skeleton block only if 𝐵 has not been committed along with an earlier leader block (see "Causal history & commit conditions" above). So a replica cannot commit the same block twice. □ 6
rounds without any directly committed slot is less than 2−𝑡 . This implies that w.h.p., every slot that is not directly decided will eventually have a committed anchor and therefore become decided (i.e., it will be committed or skipped). □
Theorem 3 (No creation). Nemo-Nemo satisfies the no creation property of Atomic Broadcast. Proof. This follows from two facts: (1) replicas only include in their local DAGs, blocks that have been previously proposed by some replica, and (2) replicas only commit blocks that they have previously included in their DAGs. □
5.2
Theorem 4 (Validity). Nemo-Nemo satisfies the validity property of Atomic Broadcast, with probability 1. Proof. Let 𝑁 be a correct replica and 𝐵 a block proposed by 𝑁. We show that, with probability 1, 𝐵 is eventually committed by every correct replica. By Lemma 6, 𝐵 is eventually included in the local DAG of every correct replica. So every correct replica will eventually include a reference to 𝐵 in at least one of its blocks. Let 𝑅 be the highest round at which some correct replica includes a reference to 𝐵 in one of its blocks. By Lemma 7, with probability 1, each skeleton block has a nonzero probability of being directly committed, so eventually some block 𝐵′ at a round 𝑅 ′ > 𝑅 will be directly committed. Since all replicas have 𝐵 in their causal histories by round 𝑅, 𝐵′ must therefore have a path to 𝐵. Lemma 8 guarantees that all slots before 𝐵′ are eventually decided, so 𝐵′ is eventually committed. Thus, 𝐵 will be committed at all correct replicas at the latest when 𝐵′ is committed alongside its causal history. □
Liveness proofs
We now turn to liveness. We prove liveness in the random asynchronous model here, and defer the proof of liveness under partial synchrony to the Supplementary Material. Lemma 5. If a block 𝐵 produced by a correct replica 𝑁 references some block 𝐵′ , then 𝐵′ will eventually be included in the local DAG of every correct replica. Proof. If some replica 𝑁 ′ receives 𝐵 from 𝑁, but does not have 𝐵′ yet, 𝑁 ′ will request 𝐵′ from 𝑁; since 𝑁 is correct and the network links are reliable, 𝑁 will eventually receive 𝑁 ′ ’s request, send 𝐵′ to 𝑁 ′ , and 𝑁 ′ will eventually receive 𝐵′ . The same is recursively true for any blocks from the causal history of 𝐵′ , so 𝑁 ′ will eventually receive all blocks from the causal history of 𝐵′ and thus include 𝐵′ in its local DAG. □
Theorem 5 (Agreement). Nemo-Nemo satisfies the agreement property of Atomic Broadcast, with probability 1.
Lemma 6. If a correct replica 𝑁 proposes a block 𝐵, then every correct replica will eventually include 𝐵 in its local DAG.
Proof. Let 𝑁 be a correct replica and 𝐵 a block committed by 𝑁. We show that, with probability 1, 𝐵 is eventually committed by every correct replica. Let 𝐿 be the skeleton block with which 𝐵 is committed and 𝑆 the corresponding slot. By Lemma 8, all blocks up to and including 𝑆 are eventually decided by all correct replicas, with probability 1. By Observation 1, all correct replicas commit 𝐿 in 𝑆. Eventually, all correct replicas commit 𝐵. □
Proof. Since network links are reliable, all correct replicas will eventually receive 𝐵 from 𝑁. By Lemma 5, all correct replicas will eventually receive all of 𝐵’s causal history, and so will include 𝐵 in their local DAG. □ Lemma 7. Fix a skeleton slot 𝑆. A replica directly commits 𝑆 with probability at least 1/2. Proof. A block in round 𝑅 + 1 will reference a random subset of 𝑓 + 1 blocks in round 𝑅. The probability that a given block 𝐵 1 votes for the skeleton slot 𝑆 is 𝑝 = 2𝑓𝑓+1 +1 > 2 . Let 𝑉 (𝑆) denote the random variable representing the number of replicas in round 𝑅 +1 that vote for 𝑆 in round 𝑅. 𝑉 (𝑆) follows a Binomial distribution: 𝑉 (𝑆) ∼ 𝐵(𝑛, 𝑝), where 𝑝 = 2𝑓𝑓+1 +1 The expected value of 𝑉 (𝑆) is: 𝐸 [𝑉 (𝑆)] = 𝑛 · 𝑝 = 𝑓 + 1. Since the mean 𝜇 = 𝑓 + 1 is an integer, the mean and the median of the distribution are equal [30]. By the definition of the median 𝑚, we have Pr(𝑉 (𝑆) ≥ 𝑚) ≥ 21 . Thus, the probability of a skeleton slot in round 𝑅 receiving at least 𝑓 + 1 votes in round 𝑅 + 1, and thus being directly committed, satisfies: Pr(𝑉 (𝑆) ≥ 𝑓 + 1) ≥ 1/2. □
6
Implementation
We implemented Nemo-Nemo in Rust, building on the opensource Mysticeti codebase [26], which contains approximately 14,000 lines of code (LOC). Our implementation uses tokio [49] for asynchronous networking and raw TCP sockets for replica-to-replica communication. To support crash recovery and ensure data persistence, we implemented a Write-Ahead Log (WAL) tailored to NemoNemo. This provides stronger resilience than existing implementations of Multi-Paxos [50] and QuePaxa [51], which lack mechanisms for recovering after crashes, though this absence arises from implementation choices rather than protocol specifications. Following prior implementations of Multi-Paxos, QuePaxa, and Rabia [41], we support batching at the replica level to amortize communication costs by packing multiple commands into a single message. We collocated front- and back-end within the same Nemo-Nemo binary. Each front-end communicates with its assigned back-end, a design choice common in existing consensus protocol implementations [37].
Lemma 8. Fix a skeleton slot 𝑆. Every correct replica eventually either commits or skips 𝑆 with probability 1. Proof. By Lemma 7, the probability of a correct replica directly committing any skeleton block in a given round is a constant (≥ 1/2). Thus, the probability that a sequence of 𝑡 7
We also implement a benchmark framework to simulate performance under a random asynchronous network model. The framework forces each consensus instance to gather a randomly selected quorum to commit rather than rely on whichever majority returns first. This shifts performance away from the quickest or geographically closest replicas and instead drives execution through a random messagedelivery schedule that removes any bias toward low-latency quorums. We use this framework only in Section 7.7 and rely on standard communication patterns for the rest of our evaluation in Section 7. To the best of our knowledge, this is the first work to introduce an evaluation framework for measuring protocol performance under the random asynchronous model, and we present this evaluation setup as a novel contribution of independent interest. We will open-source our Nemo-Nemo implementation upon acceptance to support reproducibility and enable further research in this area.
7
200k
400k
600k
Throughput (cmd/sec)
800k
Figure 3: Performance under normal case WAN execution. two state-of-the-art DAG-based, partially synchronous BFT consensus protocols: Bullshark [46] and Mysticeti [5]. We select these two BFT protocols because they share key architectural features with Nemo-Nemo and because both are widely deployed in production systems [8, 48].
Evaluation
Our evaluation compares performance, scalability, and resource efficiency to existing CFT consensus protocols. We experiment across a range of execution conditions, including favorable (fault-free, timely communication), crash-fault scenarios, and both normal and unstable network conditions.
7.1
Nemo-Nemo QuePaxa Multi-Paxos EPaxos Rabia SADL-RACS
Median latency (ms)
1,600 1,400 1,200 1,000 800 600 400 200 0 0
7.2
Experimental setup
We deploy replicas on Amazon EC2 virtual machines [4] of type c5.4xlarge. Each machine provides 10 Gbps of bandwidth, 16 virtual CPUs on a 2.5 GHz Intel Xeon Platinum 8124M, 32 GB memory, and runs Ubuntu Linux 22.04 LTS [56]. We select these machines because they provide decent performance, are in the price range of “commodity servers”, and are in line with recent related work [5, 23]. We conducted experiments in a wide-area network (WAN) with replicas distributed across multiple AWS regions: Cape Town (af-south-1), Hyderabad (ap-south-2), Jakarta (ap-southeast-3), Osaka (ap-northeast-3), and Milan (eu-south-1). We instantiate several geo-distributed benchmark clients collocated with each replica, submitting transactions in an open loop model [45], at a fixed rate. We experimentally increase the submission rate and record the throughput and latency of commits. As a result, all plots illustrate the steadystate latency of all systems under load, as well as the maximal throughput they can provide, after which latency increases rapidly. We verified that the CPU, memory, bandwidth, and storage resources are sufficient to host both the replica and client for all protocols under test. Following prior studies [42, 52] and production systems [9], we set the command size to 18 bytes. We set the timeouts at 5 sec in each protocol. For each protocol, we measure end-toend commit latency. Throughput is measured in commands per second (cmd/sec), where one command corresponds to a single 18-byte request. All protocols use batching to amortize network latency.
Baselines
We compare the performance of Nemo-Nemo against state-ofthe-art CFT protocols: Multi-Paxos [27, 50], EPaxos [35, 36], QuePaxa [51, 52], Rabia [41, 42], and SADL-RACS [53] We select these baselines for their contrasting designs, ensuring coverage of a broad spectrum of protocol architectures. Multi-Paxos uses a classic leader-based approach that channels all requests through a single leader. EPaxos adopts a multi-leader design in which every replica can propose and commit commands concurrently under dependency constraints. EPaxos produces only a partial order, a weaker abstraction than the total order that Nemo-Nemo enforces. QuePaxa represents the current state of the art in randomized consensus: it matches Multi-Paxos under synchronous conditions and switches to a fallback mode that preserves throughput under asynchrony, which makes it well suited for wide-area deployments. Rabia uses randomized techniques to optimize for low-latency local-area settings; we include it for completeness. SADL-RACS achieves high throughput by separating command dissemination from the consensus critical path. We include QuePaxa, Multi-Paxos, EPaxos, and Nemo-Nemo in all subsequent experiments. Due to page-limit constraints, we report only best-case evaluations for SADL-RACS and Rabia. We observed that the existing EPaxos codebase [35] does not support more than five replicas, an implementation limitation noted by prior work [52, 53]. Therefore, we omit using EPaxos in the scalability experiment in Section 7.4. Nemo-Nemo is designed for crash fault-tolerant systems; however, for completeness, we also compare Nemo-Nemo against
7.3
Normal case WAN performance
We evaluate the normal-case performance of Nemo-Nemo in a WAN under favorable (“synchronous”) network conditions. 8
Throughput (cmd/sec)
Figure 3 shows the throughput and median latency.
900k
Multi-Paxos. We observe in Figure 3 that Nemo-Nemo reaches a saturation throughput of 800k cmd/s at a median latency of 600 ms. In contrast, Multi-Paxos reaches only 400k cmd/s at 750 ms. This corresponds to a 2x throughput improvement and a 20% latency reduction for Nemo-Nemo over Multi-Paxos. Nemo-Nemo’s throughput advantage over Multi-Paxos stems from two key factors. First, Multi-Paxos funnels all client traffic through a single leader, creating a bottleneck, whereas Nemo-Nemo distributes load uniformly across all replicas (see Section 3). Second, Nemo-Nemo amortizes a single message per batch of commands (see Section 4), while Multi-Paxos requires ten messages per batch in a five-replica deployment, consisting of five propose messages followed by five accept messages.
600k
Nemo-Nemo Multi-Paxos QuePaxa
300k 0
3
5
7
Number of Replicas
9
Figure 4: Scalability with replication factor. Saturation throughput under 500 ms median latency. higher throughput and lower latency by load balancing across all participating nodes.
EPaxos. We observe in Figure 3 that EPaxos delivers over 400k cmd/s at a median latency of 440 ms, compared to NemoNemo which reaches 800k cmd/s at 600 ms. Both EPaxos and Nemo-Nemo distribute load among all participating nodes and therefore outperform leader-based Multi-Paxos in latency. For a throughput below 300k cmd/s, EPaxos achieves a 130 ms lower median latency than Nemo-Nemo. This latency advantage arises because EPaxos provides only a partial order of commands, which incurs less coordination overhead than Nemo-Nemo, which enforces a total order. In this experiment, we configured EPaxos with a 2% conflict rate [54], meaning that 98% of commands commit in a single round trip, resulting in lower commit latency than Nemo-Nemo at moderate load. However, beyond 400k cmd/s, Nemo-Nemo achieves roughly 2× the throughput of EPaxos. This gap stems from two factors. (1) The EPaxos implementation suffers from implementation limitations—most notably a single-threaded main execution path—whereas Nemo-Nemo employs a highly parallelized design. (2) Under high arrival rates, EPaxos’s conflict-resolution overhead becomes a dominant bottleneck. By avoiding specialized conflict resolution, Nemo-Nemo sustains substantially higher throughput. EPaxos is well suited for applications requiring only partial order with low conflict rates, such as key-value stores where per-key ordering is sufficient. By contrast, Nemo-Nemo targets applications requiring a total order of all commands, providing higher throughput for workloads that demand strong consistency.
SADL-RACS. SADL-RACS uses a mempool to disseminate client commands off the consensus critical path. In our deployment, it achieves a saturation throughput of 300k cmd/s with a median latency of 1.35 s. In comparison, Nemo-Nemo reaches 800k cmd/s and 600 ms, corresponding to a 166% higher throughput and 125% lower latency. The performance advantage of Nemo-Nemo arises from its avoidance of extra dissemination round trips. SADL-RACS requires two additional hops to propagate commands, which significantly increases latency. By embedding command dissemination into the DAG and balancing load across replicas, Nemo-Nemo sustains higher throughput and lower latency. Rabia. In our WAN deployment, Rabia delivers only 1k cmd/s with latency above 1.25 s, whereas Nemo-Nemo achieves 800k cmd/s at 600 ms. Its lower WAN performance stems from its design assumptions and optimizations for low-latency, highbandwidth LANs. As network diameter and latency variability increase, Rabia’s design assumptions no longer hold, leading to severely reduced throughput and higher latency. Tail latency. None of the evaluated systems is optimized for tail latency, and in practice we observe comparable percentile 99 behavior across all protocols. Under a 1 s percentile 99 bound, Nemo-Nemo sustains 400k cmd/s, while EPaxos reaches 375k cmd/s, and both QuePaxa and Multi-Paxos reach roughly 300k cmd/s. These results are consistent with prior findings reported in related work [52].
QuePaxa. We observe in Figure 3 that QuePaxa achieves only 400k cmd/s at a median latency of 460 ms. Under normal-case executions, QuePaxa1 funnels all commands through a single leader replica. As a result, QuePaxa’s performance is limited by the leader replica’s capacity, whereas Nemo-Nemo achieves
Summary. Across our experiments, Nemo-Nemo consistently outperforms existing CFT protocols in WAN deployments, achieving higher throughput and lower latency. Its advantages arise from uniform load distribution, minimal message delays, and avoidance of specialized assumptions (such as latency bounds) or conflict-resolution bottlenecks. These observations validate our vision: Nemo-Nemo is well suited for applications that require total ordering, high throughput, and low latency, in cloud and wide-area environments.
1 Ideally, both QuePaxa and Multi-Paxos should incur the same overhead and achieve comparable performance in normal-case operation. However, the QuePaxa implementation yields higher throughput than Multi-Paxos because it leverages gRPC-based high-speed messaging and multi-threading, whereas the Multi-Paxos implementation employs single-threaded execution.
9
Throughput (cmd/sec)
must handle all client commands and broadcast them to followers, making the leader’s network bandwidth the bottleneck as command size grows. Nemo-Nemo’s multi-leader DAG-based design distributes bandwidth usage evenly across all replicas, avoiding the leader bottleneck entirely.
Nemo-Nemo Multi-Paxos QuePaxa
600k 400k 200k 0
7.6 18
32
Command size (Bytes)
We evaluate how each system handles crash failures by deploying five replicas in a WAN setup under a constant load of 40k cmd/sec. At 25 seconds, we crash the leader replica in Multi-Paxos and QuePaxa, and a random replica in NemoNemo and EPaxos. Figure 6 shows the throughput over time.
512
Figure 5: Scalability with command size. Saturation throughput under 500 ms median latency and 5 replicas.
7.4
Scalability with number of replicas
Leader-based protocols suffer downtime. Multi-Paxos throughput drops to zero immediately upon leader crash and remains at zero during the leader election (view change). Once a new leader is elected, the backlog of accumulated commands is processed, causing a throughput spike before returning to steady state. QuePaxa exhibits similar behavior despite employing multiple leaders via a hedging schedule: by default, only the first leader proposes in the crash-free case, and the second leader begins proposing only after the configured hedging timeout. This design still creates a period of zero throughput during leader transition, followed by a spike when the new leader processes the backlog.
We evaluate how Nemo-Nemo scales as the number of replicas increases. We deploy ensembles of 3, 5, 7, and 9 replicas across geographically distributed AWS regions and compare against pipelined Multi-Paxos and QuePaxa2 . Figure 4 shows the saturation throughput under 500 ms median latency. Leader-based performance degradation. Multi-Paxos and QuePaxa exhibit throughput degradation of 35% and 33%, respectively, when scaling from 3 to 9 replicas. The performance degradation stems from leader-centric designs: as the replication factor grows, the leader must handle more messages due to larger quorum sizes, creating a resource bottleneck.
Multi-leader protocols avoid downtime. Both EPaxos and Nemo-Nemo exhibit no visible downtime under replica crashes. As multi-leader protocols, the failure of one replica does not affect the ability of the remaining replicas to make progress. Nemo-Nemo avoids explicit view changes and promptly discards blocks from crashed replicas, preventing head-of-line blocking in the commit sequence. This ensures that even if a crashed replica was previously a leader, its uncommitted blocks do not stall the system’s progress.
Multi-leader scalability. In contrast, Nemo-Nemo’s throughput doubles from 500k to 1M cmd/sec over the same range, demonstrating superior scalability. Nemo-Nemo exhibits opposite behavior due to its multi-leader DAG-based architecture. With only 3 replicas, Nemo-Nemo underutilizes available network and CPU resources. Adding more replicas improves resource multiplexing across leaders, increasing throughput. Furthermore, more replicas increase the number of blocks per round and the causal history size of leader blocks without additional network hops, enabling higher parallelism.
7.5
Performance under crash failures
7.7
Performance under random asynchrony
We evaluate Nemo-Nemo’s performance when experiencing random message delays, leveraging the benchmarking framework presented in Section 6. To amplify the effects of network randomization, we deploy 5 replicas in Cape Town (af-south-1), London (eu-west-2), Ireland (eu-west-1), Milan (eu-south-1), and Hyderabad (ap-south-2). This setup includes three replicas in Europe (forming a fast majority) and two geographically distant replicas, creating significant latency variance. Figure 7 compares throughput and median latency for both normal conditions and random asynchrony.
Scalability with command size
We evaluate the impact of command size on Nemo-Nemo’s performance. We experiment with three command sizes: 18 B, 32 B, and 512 B, as used in recent SMR work [3, 53]. We deploy Nemo-Nemo, pipelined Multi-Paxos, and pipelined QuePaxa in a WAN setting with 5 replicas. Figure 5 depicts the saturation throughput under 500 ms median latency.3 As command size increases from 18 B to 512 B, MultiPaxos degrades from 300k to 10k cmd/s, while QuePaxa drops from 400k to 20k cmd/s. In contrast, Nemo-Nemo maintains 50–66% higher throughput at 18 B and 32 B, and still retains a 5% advantage at 512 B, degrading from 600k to 30k cmd/s. This performance gap stems from fundamental architectural differences. In Multi-Paxos and QuePaxa, the single leader
Single leader-based protocols suffer under asynchrony. MultiPaxos degrades from 400k to 300k cmd/sec while QuePaxa drops from 500k to 400k cmd/sec, under 500ms latency bound. This degradation stems from their reliance on single leaderbased dissemination: all commands must flow through a single leader to its quorum. Under random asynchronous network conditions, the leader or its quorum members experience slow message delivery, creating a bottleneck that degrades overall
2 Due to an implementation error, EPaxos only supports up to 5 replicas and is excluded from this experiment. 3 The EPaxos implementation does not allow configurable command sizes and was omitted from this experiment.
10
EPaxos
80k 60k 40k 20k 00
Multi-Paxos
80k 60k 40k 20k 00
Throughput (cmd/sec)
Nemo-Nemo
Throughput (cmd/sec)
80k 60k 40k 20k 00
Throughput (cmd/sec)
Throughput (cmd/sec)
80k 60k 40k 20k 00
QuePaxa
20 40 60 20 40 60 20 40 60 20 40 60 Time (s) Time (s) Time (s) Time (s) Figure 6: Throughput under crash failures with 5 replicas. At 25 seconds, we crash the leader in Multi-Paxos and QuePaxa, and a random replica in Nemo-Nemo and EPaxos. Constant arrival rate of 40k cmd/sec.
Median latency (ms)
1,000 800 600
Nemo-Nemo (random) Nemo-Nemo QuePaxa (random) QuePaxa Multi-Paxos (random) Multi-Paxos
CPU Utilization (%)
1,200
15
200
5 0
10k
100k
Throughput (cmd/sec)
200k
Figure 9: Average CPU utilization across all 5 replicas.
200k
400k
600k
800k
Throughput (cmd/sec)
7.8
Figure 7: Performance under normal conditions and random asynchrony with 5 replicas.
100k
200k
300k
400k
Throughput (cmd/sec)
500k
Comparison against BFT protocols
We compare Nemo-Nemo against state-of-the-art BFT DAGbased consensus protocols to understand how our CFToptimized design compares to systems designed for BFT. We deploy 10 replicas with 32 B commands and compare against two popular BFT DAG protocols: Bullshark and Mysticeti. Bullshark is a partially synchronous protocol using Narwhal as its DAG layer. Mysticeti is an uncertified DAG protocol achieving an optimal three-round commitment. Since both Bullshark and Mysticeti report average latency, we depict the average latency in this evaluation. Figure 8 shows the latency-throughput trade-off.
Nemo-Nemo Mysticeti Bullshark
Average latency (ms)
1,750 1,500 1,250 1,000 750 500 250 00
QuePaxa EPaxos
10
400 0 0
Nemo-Nemo Multi-Paxos
Throughput. Nemo-Nemo and Mysticeti achieve at least 600k cmd/sec throughput, as both employ lightweight DAGbased architectures for parallel block processing. Bullshark attains only 450k cmd/sec (25% lower) due to its heavier Narwhal-based certified DAG design.
600k
Figure 8: Comparison against state-of-the-art BFT DAG-based protocols with 10 replicas and 32 B commands.
Latency advantages. More importantly, Nemo-Nemo achieves substantially lower latency than both BFT protocols: 1200 ms lower than Bullshark and 180 ms lower latency than Mysticeti. This latency advantage stems from two key differences. First, Nemo-Nemo’s typical commit path requires only 2 message delays, fewer than both Mysticeti (3 message delays) and Bullshark (6 message delays). Second, Nemo-Nemo targets crash faults and avoids cryptographic operations entirely, while BFT protocols must authenticate every message with signatures and hashes to defend against Byzantine behavior. The combination of fewer message delays and zero cryptographic overhead enables Nemo-Nemo to achieve significantly lower latency than BFT alternatives.
system performance. DAG-based dissemination provides robustness. In stark contrast, Nemo-Nemo maintains stable throughput at 900k cmd/sec, showing no throughput degradation despite network randomization. This results in Nemo-Nemo outperforming Multi-Paxos by 3× and QuePaxa by 2.25×, in throughput, under random asynchrony. Nemo-Nemo’s robustness arises from its DAG-based architecture: all replicas disseminate commands concurrently, creating multiple parallel paths to commitment. Nemo-Nemo adapts to network conditions without performance degradation. 11
7.9
network messages to commit a batch of commands, resulting in high latency overhead (see in Figure 3). In contrast, NemoNemo embeds command dissemination directly into the DAG, avoiding extra message hops and achieving lower latency and higher throughput.
Resource utilization
We measure the CPU utilization of Nemo-Nemo and follow Matte et al. [33], who use CPU utilization as a proxy for resource consumption. We record per-replica CPU utilization once per second with Go’s “gopsutil” tool [16], aggregate the readings across replicas, and report the mean per-replica utilization in Figure 9. Figure 9 shows that Nemo-Nemo uses only 1% CPU at 100k cmd/sec, compared to 9%, 15%, and 7% for Multi-Paxos, QuePaxa, and EPaxos.4 The same pattern holds at 10k and 200k cmd/sec. Multi-Paxos, QuePaxa, and EPaxos consume more CPU because they process more messages: Nemo-Nemo broadcasts one message per block, while existing protocols require at least two propose–vote rounds to commit a batch. This extra communication directly increases their CPU cost, whereas Nemo-Nemo avoids it.
8
DAG-based protocols. DAG-based consensus protocols are recent advancements in Byzantine fault-tolerance (BFT), but have not been explored in the context of crash fault-tolerant (CFT) systems. Existing BFT DAG-based protocols can be classified into two categories: certified DAGs [14, 46] and uncertified DAGs [5, 23, 25]. Nemo-Nemo is the first CFT protocol to adopt a DAG-based architecture, specifically using an uncertified DAG design. DAG-Rider [24], Tusk [14], Bullshark [46], and DumboNG [19] are representative certified DAG protocols that use consistent broadcast to explicitly certify each DAG block [44]. Fides [60] is a TEE-assisted BFT DAG protocol that also uses certified blocks, achieving certification in two rounds without signatures by leveraging TEE guarantees. Explicit certification ensures that equivocating blocks cannot exist, simplifying the commit rule. However, certification adds at least 3 message delays per DAG round and increases latency, as seen in Bullshark’s results in Figure 8. It also raises bandwidth and CPU costs, since replicas must disseminate, receive, and verify cryptographic certificates. To avoid these drawbacks, Nemo-Nemo employs an uncertified DAG architecture. Cordial Miners [25], Mysticeti [5], Mahi-Mahi [23], and BlueBottle [58] operate over uncertified DAGs, where each block is disseminated using best-effort to all replicas. NemoNemo also builds on an uncertified DAG, but differs fundamentally from these BFT protocols in two key ways. First, by targeting crash faults instead of Byzantine faults, NemoNemo’s protocol structure requires one less DAG-round to commit, reducing message delays from 3 to 2. Second, NemoNemo avoids expensive cryptographic operations such as signature generation and verification, and hash computation and verification. The combination of fewer message delays and zero cryptographic overhead enables Nemo-Nemo to achieve significantly lower latency than Mysticeti (see in Figure 8).
Related Work
Leader-based protocols. Most deployed consensus protocols rely on a leader to order requests and achieve one-round-trip normal-case commit latency [27, 39, 40]. While simple and efficient in favorable conditions, leader-based protocols suffer from two fundamental limitations: all client requests must funnel through a single leader, limiting throughput scalability, and performance degrades significantly under asynchronous or poor network conditions when the leader or its closest quorum experiences delays. As shown in Figures 3 to 5 and 7, Nemo-Nemo outperforms leader-based protocols in both throughput and latency by distributing load evenly across replicas, providing robustness under network randomization. Multi-leader protocols. To address the leader bottleneck, several protocols enable multiple concurrent leaders. Mencius [32] statically partitions the replicated log across replicas, but its main drawback is that SMR progress depends on the slowest replica. In contrast, Nemo-Nemo progresses at the speed of the majority. Generalized Paxos [28] and EPaxos [36] support multi-leaders by exploiting request dependencies and allowing partial order of commands. Under low load, EPaxos achieves lower latency than Nemo-Nemo, but under high load, the dependency-checking overhead becomes a bottleneck, degrading performance. Fast Paxos [29] and Multi-coordinated Paxos [11] also permit multiple leaders but deliver suboptimal performance in practice [36].
Orthogonal goals. Nemo-Nemo focuses on high-performance, simple consensus, but does not address several other important goals: e.g., scalability via partitioning commands and state [2, 18, 36, 43], shrinking quorum sizes [2, 21], exploiting WAN locality [2, 38], storage optimization with erasure coding [57, 59], or reducing replica load by outsourcing work [61]. We plan to explore how techniques from these complementary efforts can integrate with Nemo-Nemo in future work.
Parallel dissemination. SADL-RACS [53] takes a different approach by decoupling command dissemination from the consensus critical path, following a design similar to Narwhal [14]. Unlike Nemo-Nemo, SADL-RACS does not build a DAG; instead, it uses the SADL overlay to maintain a perreplica chain of blocks, which are committed when the next RACS block is committed. This separation requires at least 5 4 QuePaxa adopts a gRPC-based multi-threaded design, while Multi-Paxos
uses a single-threaded one, which increases QuePaxa’s CPU usage.
12
on Principles of distributed computing, pages 316–317, 2007.
References [1] Ittai Abraham, Neil Giridharan, and Kartik Nayak. What’s dag got to do with it? https://decentralizedthoughts.github.io/ 2025-08-08-DAGs/, August 2025.
[12] Miguel Castro and Barbara Liskov. Practical Byzantine fault tolerance. In Proceedings of the 3rd USENIX Symposium on Operating Systems Design and Implementation (OSDI), February 1999.
[2] Ailidani Ailijiang, Aleksey Charapko, Murat Demirbas, and Tevfik Kosar. WPaxos: Wide area network flexible consensus. IEEE Transactions on Parallel and Distributed Systems, 31(1):211–223, 2019.
[13] CoinEx. What Is IKA? IKA: Exploring the Fastest MPC Network on Sui Blockchain, 2025. CoinEx Academy. [14] George Danezis, Lefteris Kokoris-Kogias, Alberto Sonnino, and Alexander Spiegelman. Narwhal and Tusk: a DAG-based mempool and efficient BFT consensus. In ACM EuroSys, 2022.
[3] Mohammadreza Alimadadi, Hieu Mai, Shenghsun Cho, Michael Ferdman, Peter Milder, and Shuai Mu. Waverunner: An elegant approach to hardware acceleration of state machine replication. In 20th USENIX Symposium on Networked Systems Design and Implementation (NSDI 23), pages 357–374, 2023.
[15] George Danezis, Jovan Komatovic, Lefteris KokorisKogias, Alberto Sonnino, and Igor Zablotchi. Byzantine consensus in the random asynchronous model. arXiv preprint arXiv:2502.09116, 2025.
[4] Amazon. AWS instance types. https://aws.amazon. com/ec2/instance-types/, 2023.
[16] DataDog. gopsutil. https://github.com/DataDog/ gopsutil, 2025.
[5] Kushal Babel, Andrey Chursin, George Danezis, Lefteris Kokoris-Kogias, and Alberto Sonnino. Mysticeti: Lowlatency dag consensus with fast commit path. arXiv preprint arXiv:2310.14821, 2023.
[17] Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. Consensus in the presence of partial synchrony. Journal of the ACM (JACM), 35(2):288–323, 1988.
[6] Leemon Baird and Atul Luykx. The Hashgraph Protocol: Efficient Asynchronous BFT for High-Throughput Distributed Ledgers. In 2020 International Conference on Omni-layer Intelligent Systems (COINS), 2020.
[18] Vitor Enes, Carlos Baquero, Tuanir França Rezende, Alexey Gotsman, Matthieu Perrin, and Pierre Sutra. State-machine replication for Planet-Scale systems. In Proceedings of the Fifteenth European Conference on Computer Systems (EuroSys ’20), April 2020.
[7] Michael Ben-Or. Another advantage of free choice (extended abstract): Completely asynchronous agreement protocols. In Proceedings of the Second Annual ACM Symposium on Principles of Distributed Computing, PODC ’83, pages 27–30. ACM, August 1983.
[19] Yingzi Gao, Yuan Lu, Zhenliang Lu, Qiang Tang, Jing Xu, and Zhenfeng Zhang. Dumbo-ng: Fast asynchronous bft consensus with throughput-oblivious latency. In ACM CCS, 2022.
[8] Sam Blackshear, Andrey Chursin, George Danezis, Anastasios Kichidis, Lefteris Kokoris-Kogias, Xun Li, Mark Logan, and et al. Sui lutris: A blockchain combining broadcast and consensus. In CCS, 2024.
[20] Neil Giridharan, Florian Suri-Payer, Ittai Abraham, Lorenzo Alvisi, and Natacha Crooks. Autobahn: Seamless high speed bft. In Proceedings of the ACM SIGOPS 30th Symposium on Operating Systems Principles, pages 1–23, 2024.
[9] Nathan Bronson, Zach Amsden, George Cabrera, Prasad Chakka, Peter Dimov, Hui Ding, Jack Ferris, Anthony Giardullo, Sachin Kulkarni, Harry Li, Mark Marchukov, Dmitri Petrov, Lovro Puzar, Yee Jiun Song, and Venkat Venkataramani. TAO: Facebook’s distributed data store for the social graph. In USENIX Annual Technical Conference USENIX ATC 13, pages 49–60, June 2013.
[21] Heidi Howard, Dahlia Malkhi, and Alexander Spiegelman. Flexible Paxos: Quorum intersection revisited. In Proceedings of the 20th International Conference on Principles of Distributed Systems (OPODIS 2016), December 2016.
[10] Christian Cachin, Rachid Guerraoui, and Luís Rodrigues. Introduction to Reliable and Secure Distributed Programming. Springer Science & Business Media, 2011.
[22] IOTA Stiftung. Consensus on IOTA. https:// docs.iota.org/about-iota/iota-architecture/ consensus, 2025. IOTA Documentation.
[11] Lásaro Jonas Camargos, Rodrigo Malta Schmidt, and Fernando Pedone. Multicoordinated paxos. In Proceedings of the twenty-sixth annual ACM symposium
[23] Philipp Jovanovic, Lefteris Kokoris Kogias, Bryan Kumara, Alberto Sonnino, Pasindu Tennage, and Igor Zablotchi. Mahi-mahi: Low-latency asynchronous bft 13
dag-based consensus. 45th IEEE International Conference on Distributed Computing Systems, 2025.
[37] Iulian Moraru, David G Andersen, Michael Kaminsky, and Pasindu Tennage. EPaxos go-lang – modified for QuePaxa experiments. https://github.com/dedis/ quepaxa-ePaxos-open-loop, September 2023.
[24] Idit Keidar, Eleftherios Kokoris-Kogias, Oded Naor, and Alexander Spiegelman. All You Need is DAG. In ACM PODC, 2021.
[38] Faisal Nawab, Divyakant Agrawal, and Amr El Abbadi. DPaxos: Managing data closer to users for low-latency and mobile applications. In ACM SIGMOD/PODS Conference on Management of Data, June 2018.
[25] Idit Keidar, Oded Naor, Ouri Poupko, and Ehud Shapiro. Cordial Miners: Fast and Efficient Consensus for Every Eventuality. In DISC, 2023.
[39] Brian M Oki and Barbara H Liskov. Viewstamped replication: A new primary copy method to support highly-available distributed systems. In Proceedings of the Seventh Annual ACM Symposium on Principles of Distributed Computing, pages 8–17, January 1988.
[26] Mysten Labs. Mysticeti: Low-latency dag consensus with fast commit path. https://github.com/ asonnino/mysticeti, 2024. [27] Leslie Lamport. Paxos made simple. ACM SIGACT News (Distributed Computing Column) 32, 4, 32:51–58, December 2001.
[40] Diego Ongaro and John Ousterhout. In search of an understandable consensus algorithm. In 2014 USENIX Annual Technical Conference ATC14, pages 305–319, June 2014.
[28] Leslie Lamport. Generalized consensus and Paxos. Technical Report MSR-TR-2005-33, Microsoft Research, March 2005.
[41] Haochen Pan, Jesse Tuglu, Neo Zhou, Tianshu Wang, Yicheng Shen, Xiong Zheng, Joseph Tassarotti, Lewis Tseng, and Roberto Palmieri. Rabia. https://github. com/haochenpan/rabia, 2021. Rabia implementation in the Go language (GitHub repository).
[29] Leslie Lamport. Fast paxos. Distributed Computing, 19(2):79–103, 2006. [30] Nick Lord. Binomial averages when the mean is an integer. The Mathematical Gazette 94, 331-332, 2010.
[42] Haochen Pan, Jesse Tuglu, Neo Zhou, Tianshu Wang, Yicheng Shen, Xiong Zheng, Joseph Tassarotti, Lewis Tseng, and Roberto Palmieri. Rabia: Simplifying statemachine replication through randomization. In Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles, pages 472–487, October 2021.
[31] Dahlia Malkhi and Pawel Szalachowski. Maximal extractable value (mev) protection on a dag. In Tokenomics, 2022. [32] Yanhua Mao, Flavio Junqueira, and Keith Marzullo. Mencius: Building efficient replicated state machines for WANs. In 8th USENIX Symposium on Operating Systems Design and Implementation (OSDI 08), December 2008.
[43] Sebastiano Peluso, Alexandru Turcu, Roberto Palmieri, Giuliano Losa, and Binoy Ravindran. Making fast consensus generally faster. In Proceedings of the 46th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN), June 2016.
[33] Venkata Swaroop Matte, Aleksey Charapko, and Abutalib Aghayev. Scalable but wasteful: Current state of replication in the cloud. In Proceedings of the 13th ACM Workshop on Hot Topics in Storage and File Systems, pages 42–49, July 2021.
[44] Mayank Raikwar, Nikita Polyanskii, and Sebastian Müller. SoK: DAG-based Consensus Protocols. In IEEE ICBC, 2024. [45] Bianca Schroeder, Adam Wierman, and Mor HarcholBalter. Open versus closed: A cautionary tale. In Proceedings of the 3rd USENIX Symposium on Networked Systems Design and Implementation (NSDI 06). USENIX, May 2006.
[34] Michael S. Paterson Michael J. Fischer, Nancy A. Lynch. Impossibility of distributed consensus with one faulty process. Journal of ACM, 1985. [35] Iulian Moraru, David G Andersen, and Michael Kaminsky. EPaxos go-lang. https://github.com/ efficient/epaxos/, 2013.
[46] Alexander Spiegelman, Neil Giridharan, Alberto Sonnino, and Lefteris Kokoris-Kogias. Bullshark: DAG BFT Protocols Made Practical. In ACM CCS, 2022.
[36] Iulian Moraru, David G Andersen, and Michael Kaminsky. There is more consensus in egalitarian parliaments. In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles, pages 358–372, November 2013.
[47] Alexander Spiegelman, Neil Giridharan, Alberto Sonnino, and Lefteris Kokoris-Kogias. Bullshark: the partially synchronous version. arXiv preprint arXiv:2209.05633, 2022. 14
[48] The Sui team. Sui. https://github.com/mystenLabs/sui, 2024.
[60] Shaokang Xie, Dakai Kang, Hanzheng Lyu, Jianyu Niu, and Mohammad Sadoghi. Fides: Scalable censorshipresistant dag consensus via trusted components. ArXiv preprint arXiv:2501.01062, 2025.
[49] The Tokio Team. Tokio. https://tokio.rs, 2024. [50] Pasindu Tennage. Paxos and Raft, September 2023. GitHub repository https://github.com/ dedis/paxos-and-raft.
[61] Zichen Xu, Christopher Stewart, and Jiacheng Huang. Elastic, geo-distributed RAFT. In Proceedings of the International Symposium on Quality of Service. Association for Computing Machinery, 2019.
[51] Pasindu Tennage. QuePaxa, September 2023. GitHub repository https://github.com/dedis/quepaxa.
[62] Maofan Yin, Dahlia Malkhi, Michael K Reiter, Guy Golan Gueta, and Ittai Abraham. Hotstuff: Bft consensus with linearity and responsiveness. In ACM PODC, 2019.
[52] Pasindu Tennage, Cristina Basescu, Lefteris KokorisKogias, Ewa Syta, Philipp Jovanovic, Vero EstradaGalinanes, and Bryan Ford. Quepaxa: Escaping the tyranny of timeouts in consensus. In Proceedings of the 29th Symposium on Operating Systems Principles, pages 281–297, 2023. [53] Pasindu Tennage, Antoine Desjardins, and Lefteris Kokoris-Kogias. Racs-sadl: Robust and understandable randomized consensus in the cloud. In 2025 IEEE 18th International Conference on Cloud Computing (CLOUD), pages 362–373, 2025. [54] Sarah Tollman, Seo Jin Park, and John K Ousterhout. EPaxos revisited. In USENIX Symposium on Networked Systems Design and Implementation (NSDI 21), pages 613–632, April 2021. [55] Giorgos Tsimos, Anastasios Kichidis, Alberto Sonnino, and Lefteris Kokoris-Kogias. Hammerhead: Leader reputation for dynamic scheduling. In 2024 IEEE 44th International Conference on Distributed Computing Systems (ICDCS), pages 1377–1387, 2024. [56] Ubuntu. Ubuntu Linux. https://releases.ubuntu. com/focal/, 2023. [57] Muhammed Uluyol, Anthony Huang, Ayush Goel, Mosharaf Chowdhury, and Harsha V. Madhyastha. Nearoptimal latency versus cost tradeoffs in geo-distributed storage. In Proceedings of the 17th USENIX Symposium on Networked Systems Design and Implementation (NSDI ’20), February 2020. [58] Preston Vander Vos, Alberto Sonnino, Giorgos Tsimos, Philipp Jovanovic, and Lefteris Kokoris-Kogias. BlueBottle: Fast and Robust Blockchains through Subsystem Specialization. ArXiv preprint arXiv:2511.15361, 2025. [59] Zizhong Wang, Tongliang Li, Haixia Wang, Airan Shao, Yunren Bai, Shangming Cai, Zihan Xu, and Dongsheng Wang. CRaft: An Erasure-coding-supported version of Raft for reducing storage cost and network cost. In Proceedings of the 18th USENIX Conference on File and Storage Technologies (FAST ’20), February 2020. 15