arXiv CSopen access

Duet: Co-Optimizing P2P Message Propagation and Rotating-Leader Consensus

Duet: Co-Optimizing P2P Message Propagation and Rotating-Leader Consensus Yifeng Ye

Rongji Huang

Gerui Wang

Shanghai Jiao Tong University China

Shanghai Academy of Future Internet Technology China

Beijing Academy of Blockchain and Edge Computing China

Mingchao Wan

Yuxing Duan

Jingjing Zhang

Beijing Academy of Blockchain and Edge Computing China

Beijing Academy of Blockchain and Edge Computing China

Fudan University China

Shengyun Liu

arXiv:2607.22209v1 [cs.DC] 24 Jul 2026

Shanghai Jiao Tong University China

Abstract

liveness [25], the consensus layer and the underlying network are typically designed independently. Compared with all-to-all communication, P2P networks allow each node to maintain connections with and forward messages to only a small subset of neighbors, effectively reducing message and communication complexity while preserving reliability with high probability. Hence, P2P networks combined with gossipbased message dissemination have become the de facto approach to scaling blockchain networks. Taking two representative permissionless blockchains as examples, Bitcoin [42] uses an unstructured P2P network to connect nodes, whereas Ethereum [13] employs a Kademlia-based [40] structured overlay for node discovery. Other permissionless blockchains, such as XRP [60], Filecoin [5], which is built on top of IPFS [59], and Avalanche [51], also rely on P2P networks. Permissioned blockchains, such as Hyperledger Fabric [3, 8], also support P2P networks for large-scale deployment. Napster was launched in 1999 as the first generation of P2P networks [17]. Since then, P2P overlays have been studied extensively in both academia and industry [24, 36, 37, 49, 52, 57]. Prior to blockchain, P2P networks were mainly used for decentralized content sharing and communication, where no centralized module or equivalent functionality was available. Despite decades of research, the most-widely used P2P networks are either unstructured [50] or variants of Kademlia [19]. In sharp contrast, blockchain systems can naturally be abstracted as replicated state machines [53], providing logically centralized (yet practically decentralized) consensus and contract-execution layers that can be leveraged to facilitate the management of the underlying network. Besides, in existing blockchain deployments, the consensus protocol and the underlying P2P network still treat each other as opaque components, limiting opportunities for further optimization.

In blockchain systems, peer-to-peer (P2P) overlay networks play a crucial role in providing reliable, scalable and efficient message-delivery services to upper layers. However, the consensus layer and the underlying P2P network remain mutually opaque in existing blockchains, waiving the opportunity for further improvement. In contrast to other P2P applications, blockchain can naturally be abstracted as a state machine. We therefore leverage this abstraction to record network topologies and latencies in a trusted and coordinated manner. With this support, we propose three improvements to rotating-leader consensus protocols and their underlying P2P networks: (1) accelerating leader rotation; (2) introducing a reliable-broadcast paradigm that employs tree-based dissemination in the normal case and falls back to gossip only when necessary; and (3) constructing latency-aware dissemination trees. We integrate the above ideas into Tendermint and libp2p, and conduct empirical evaluation on Amazon EC2 platform using up to 300 nodes distributed across 10 regions. The results demonstrate that, compared with gossip-based dissemination over the same topology, our prototype improves peak throughput by up to 7.26×.

1

Introduction

Blockchain systems, especially permissionless ones that allow the open participation of widely-scattered players, are typically deployed on a peer-to-peer (P2P) overlay network. P2P networks play a crucial role in providing reliable, scalable and efficient message transmission services to upper layers, such that each message is delivered by every correct node eventually. Such features are essential for achieving scalability and simplifying the design, implementation, and maintenance of the upper-layer consensus protocol, which reaches agreement on the order of blocks among nodes. Although most consensus protocols depend on timing assumptions about message delivery to ensure safety and/or 1

P2P network simplifies the design and implementation of the upper-layer consensus protocol by providing a reliable broadcast primitive. For instance, Nakamoto consensus [42] follows a very simple rule in which honest nodes extend the longest chain they are aware of, which represents the greatest cumulative proof-of-work effort. Tendermint [12] relies solely on a three-phase message exchange to both reach agreement and rotate proposers, even in the presence of faulty nodes. HashGraph [10] reaches consensus through a gossip-about-gossip protocol, in which nodes disseminate transactions together with their communication histories, allowing each node to determine consensus locally through virtual voting without exchanging explicit vote messages. In contrast, traditional Byzantine fault-tolerant (BFT) protocols [18, 26, 32, 62] typically introduce an explicit viewchange procedure to replace faulty proposers. Although P2P networks offer such an appealing feature, their randomly connected topologies and gossip-based dissemination mechanisms still limit the efficiency of highperformance blockchain systems. In this work, we specifically target rotating-leader consensus (RLC) [6, 12, 22, 61, 62], a paradigm widely adopted by modern permissioned and permissionless blockchains [13, 14, 33, 42]. In RLC protocols, the leader or proposer rotates across block heights to distribute block-proposal opportunities evenly among nodes. Rotating-leader consensus avoids relying on a single leader while retaining the simplicity and efficiency of leader-based consensus. Moreover, this paradigm enables nodes to reach consensus also on execution results rather than merely on the transactions themselves, thereby effectively mitigating the non-determinism problem [16]. Simply recording the underlying network topology and latencies on-chain allows us to leverage this information to improve consensus and message routing in multiple ways:

protocol must therefore be adapted accordingly to preserve liveness and other properties. We conduct an empirical evaluation on Amazon EC2 using up to 300 nodes distributed across 10 regions. We also compare Duet against gossip-based dissemination and a 𝐾ary tree. The results demonstrate that Duet achieves up to 7.26× higher throughput than gossip-based dissemination over the same topology. Duet can be readily integrated into permissioned blockchains, which typically provide a configuration module for membership management. Duet can also be applied to permissionless blockchains, such as Ethereum, to maintain a network backbone, for example by deploying a smart contract through which nodes stake to participate. It may be even more promising to extend the ideas of Duet to multi-leader or DAG-based consensus protocols [20, 30, 35, 55, 56], as they allow multiple concurrent proposals and typically incur higher bandwidth consumption.

2

Background

2.1

System model

We consider a system with 𝑁 nodes Π at some time. We assume all point-to-point communications are authenticated and reliable: all messages exchanged between any two correct nodes will eventually arrive. To prevent message tampering, node 𝑝𝑖 utilizes its private key to generate a signature 𝜎𝑖 attached to message 𝑚 it sends. Upon receiving 𝑚, the receiver needs to verify 𝜎𝑖 by 𝑝𝑖 ’s public key. Regarding “deliver”, we mean a node successfully receives and verifies a message. Since nodes in a P2P network are not fully connected, we adopt a gossip-based protocol for message propagation (i.e., broadcast): for each message 𝑚, every node except the original sender will forward it to neighbors once the node delivers 𝑚. We focus on the following two ideal properties [15]: • Validity: If a correct node broadcasts a message 𝑚, then every correct node eventually delivers 𝑚. • Totality: If a correct node delivers a message 𝑚, then every correct node eventually delivers 𝑚. We assume a partially synchronous network model [23], meaning that after a global stabilization time (GST), messages exchanged between correct nodes are guaranteed to arrive within a bounded delay Δ. Hence, the system requires 𝑁 ≥ 3𝑓 + 1, where 𝑓 is the number of Byzantine faulty nodes. In a P2P network, messages may be relayed through multiple intermediate nodes before eventually reaching every node.

• We can optimize the proposer sequence and accelerate proposer rotation, thereby improving the throughput of RLC protocols; • By cleverly leveraging votes in the consensus protocol as acknowledgments, we can first employ an efficient (but not reliable) tree-based dissemination scheme to broadcast proposals and resort to gossip-based dissemination only as a fallback; and, • We can construct an efficient dissemination tree to minimize the cost of disseminating messages. We instantiate the above ideas by integrating them into a pipelined variant of Tendermint [12] and libp2p [4], a classical RLC protocol built upon P2P networks and a modular P2P networking framework adopted by many decentralized applications, respectively. We refer to our prototype as Duet. Note that integrating tree-based dissemination into a P2Pbased consensus protocol is non-trivial, as the assumption that all correct nodes receive every message within Δ time after a global stabilization time (GST) no longer holds. The

2.2

P2P network and libp2p

Blockchain systems typically build consensus protocols on top of peer-to-peer (P2P) overlay networks. The underlying P2P network disseminates transactions, blocks, and consensus messages among nodes, while the consensus layer determines the ordering and finality of transactions. These 2

two layers are often designed independently: the consensus layer assumes reliable or eventually timely message delivery, whereas the P2P layer treats upper-layer messages as opaque payloads. This separation simplifies system design but leaves substantial room for cross-layer optimization. In a fully connected network, the totality property is typically ensured by requiring each node to relay every message to all other nodes, increasing message and communication complexities to 𝑁 2 and |𝑚|𝑁 2 , respectively. Introducing a P2P network and its gossip-based dissemination mechanism reduces the message and communication complexities to 𝑁𝑑 and |𝑚|𝑁𝑑, where 𝑑 denotes the average node degree or fanout. In P2P networks, several bootstrapping nodes (i.e., bootnodes) are distributed geographically outside the network and provide participation guidance for new nodes. Although bootnodes are out of the consensus, they help new nodes discover existing peers and obtain basic network metadata, such as node information, group information, and network structure. In a sense, bootnodes serve as a bridge between the system and the outside world. libp2p [4] is a modular peer-to-peer networking framework for building decentralized applications. It provides a publish–subscribe abstraction in which peers subscribe to topics and receive messages disseminated through the P2P overlay, without requiring the publisher to maintain a connection to every subscriber. GossipSub is libp2p’s commonly used PubSub routing protocol. For each topic, GossipSub maintains a bounded mesh of peers. The mesh is designed to avoid eager all-to-all forwarding: a peer sends full message payloads only to a small set of mesh neighbors, which bounds per-message fanout while still creating multiple dissemination paths across the overlay. The mesh size is therefore an important performance parameter: a larger mesh can improve reachability and reduce dissemination delay, but it also increases redundant payload traffic and bandwidth consumption. To control the mesh size while preserving reachability, GossipSub separates eager data forwarding from lazy metadata gossip: besides sending full messages over mesh links, peers periodically advertise message identifiers through IHAVE control messages, and a receiver that learns about an unseen message can reply with an IWANT message to request the corresponding payload. The IHAVE/IWANT exchange therefore serves as a repair and discovery mechanism: it lets peers detect and fetch missing messages while keeping most redundant traffic at the level of compact message identifiers rather than full payloads. 2.3

Node 0 Node 1

PROPOSE phase

2𝑓 + 1 2𝑓 + 1 PREVOTE PRECOMMIT PREVOTE PRECOMMIT COMMIT(𝑣) phase phase

𝑣

Node 2 Node 3 𝑡𝑚𝑟 ,

𝑡𝑚𝑟 ,

𝑡𝑚𝑟 ,

Figure 1. The message pattern of Tendermint (𝑁 = 3𝑓 + 1). using only a three-phase message pattern, even across proposer rotations triggered by faulty or malicious proposers. Tendermint also proactively rotates proposers across block heights to ensure a fair distribution of proposal opportunities. Within each height, Tendermint proceeds through repeated rounds, with each containing propose, prevote, and precommit phases. The message pattern is depicted in Figure 1. In each round, a designated proposer or leader broadcasts a proposal, i.e., a candidate block. Other nodes first prevote for a valid proposal and then precommit after observing more than two-thirds of prevotes for the same proposal. A proposal is committed once it receives precommits from more than two-thirds of the nodes. Nodes lock on sufficiently supported proposals to prevent conflicting decisions across rounds, while proposer rotation across rounds ensures progress once the network stabilizes. Each phase is associated with a timer, upon the expiration of which nodes advance to the next step. In addition to its locking mechanism, Tendermint heavily relies on the underlying P2P network to avoid introducing an explicit view-change protocol or dedicated view-change messages, thereby simplifying implementation and maintenance. Specifically, Tendermint relies on the following important invariant to ensure liveness. Invariant 1. After GST, all correct nodes advance to the next step within Δ time. The next step may be the subsequent phase within the current round, the next round, or even the next height. Pipelined extension. The original version of Tendermint is not pipelined: a proposal at height ℎ is issued only after the proposal at height ℎ − 1 has been committed. In the effort to improve our enterprise-grade permissioned blockchain, which uses Tendermint as its consensus module, we found that pipelining is key to boosting the performance of rotatingleader consensus, as also demonstrated by a pipelined HotStuff [22]. In this work, we target a pipelined variant of Tendermint, in which the proposer at each height issues a proposal upon receiving the proposal from the preceding height. Each node maintains a round number shared across heights, which is incremented only when a precommit timer expires at some height. Nodes may precommit a proposal or

Tendermint and its pipelined extension

Tendermint [12] is a leader-based Byzantine fault-tolerant consensus protocol inspired by the seminal PBFT [18]. The core idea of Tendermint is to combine the normal-case operations of PBFT with a novel locking mechanism and the underlying P2P network, enabling nodes to reach agreement 3

new node

a

system p node

p

proxy

bootnode b

request to join

propose to leave

3.2 detect failure

Optimized proposer sequence

The proposer sequence refers to the order in which nodes are selected to propose the next block. The de facto approach for assigning proposers, especially in permissioned blockchains, is to use a round-robin scheme [12, 62]. In permissionless settings, such a sequence may instead be generated using randomness. Due to latency discrepancies among geo-distributed nodes, even in a fully connected network, rotating proposers incurs non-negligible overhead. Assume there are 𝑁 geographically distributed proposers across the globe, with pairwise communication delays denoted by 𝑑 (𝑖, 𝑗). Consider a random path that visits every proposer exactly once and returns to the starting proposer, i.e., it forms a cycle (𝑣 1, 𝑣 2, . . . , 𝑣 𝑁 , 𝑣 1 ). The total latency of the cycle is

propose to remove

Consensus Layer reconfigure

Network Layer

Figure 2. The procedures for network evolution.

start any timer at height ℎ only after committing a proposal at height ℎ − 1. 𝐿=

𝑁 ∑︁

𝑑 (𝑣𝑘 , 𝑣𝑘+1 ),

𝑣 𝑁 +1 = 𝑣 1 .

𝑘=1

3

Co-design ideas

3.1

Ledgers for networking

The expected latency of a uniformly random cycle is ¯ E[𝐿] = 𝑁 𝑑,

By recording network topologies and latencies on-chain, every node in the system keeps the current network information locally; for every membership change, the system is required to reach a consensus on it to synchronize the new network information. Similar to the Group Membership abstraction [15], we abstract a network configuration component as the core of the underlying network management, in order to smoothly handle network evolution. Abstraction of network reconfiguration (NR). The procedure that all nodes in the network obtain consistent and accurate information about the nodes joining and leaving and the consequent network topology update can be abstracted as a Network Reconfiguration (NR) primitive. Assume Λ denotes the edge (link) set of the network, i.e., the network topology, and together with an evolution view identifier 𝑣𝑖𝑑 and the node set Π form the network information 𝜒 = (𝑣𝑖𝑑, Π, Λ) kept by every node. The initial evolution view is 0. Any node that joins or leaves the network can propose 𝜒 ′ = (𝑣𝑖𝑑 ′, Π ′, Λ′ ), with 𝑣𝑖𝑑 ′ = 𝑣𝑖𝑑 + 1, Π ′ the node set after the change and Λ′ the consequent network topology, as an input to the NR. There may exist more than one 𝜒 ′ as inputs to the NR. By consensus, the output of the NR is only one 𝜒 ′ that every node verifies and installs on its local 𝜒. The following properties must hold: (1) Monotonicity: If a correct node installs 𝜒 = (𝑣𝑖𝑑, Π, Λ) and subsequently installs 𝜒 ′ = (𝑣𝑖𝑑 ′, Π ′, Λ′ ), then 𝑣𝑖𝑑 < 𝑣𝑖𝑑 ′ . (2) Agreement: If some correct node installs 𝜒 = (𝑣𝑖𝑑, Π, Λ) and another correct node installs some 𝜒 ′ = (𝑣𝑖𝑑, Π ′, Λ′ ), then Π = Π ′, Λ = Λ′ . (3) Completeness: If a node 𝑝 (i) joins (ii) leaves / crashes, then eventually every correct node installs 𝜒 = (𝑣𝑖𝑑, Π, Λ) such that (i) 𝑝 ∈ Π (ii) 𝑝 ∉ Π. Figure 2 depicts the procedures for the network evolution.

where 𝑑¯ =

∑︁ 2 𝑑 (𝑖, 𝑗) 𝑁 (𝑁 − 1) 𝑖< 𝑗

is the average pairwise latency among all proposer pairs. Intuitively, a random cycle contains 𝑁 edges, and the expected latency of each edge equals the average pairwise la¯ Typically, the intercontinental RTTs between AWS tency 𝑑. regions is in the range of 150-350 ms [1]. Ideally, assume proposers are arranged sequentially along the equator and rotated accordingly. The time required to traverse the equator by optical fiber cable is only a few hundred milliseconds, which is independent of 𝑁 . We have the following heuristic. Heuristic 1. The faster a proposer receives the preceding proposals, the sooner it can generate its own proposal. Consider a P2P network where nodes are not fully connected, the problem is formulated as a (variant of) traveling salesman problem [28] (TSP) on a weighted undirected graph. Given a weighted undirected graph 𝐺 = (𝑉 , 𝐸, 𝑤), find a cycle such that every vertex in 𝑉 is visited exactly once, and the total weight 𝑛 ∑︁ 𝑤 (𝑣𝑖 , 𝑣𝑖+1 ), 𝑣 𝑁 +1 = 𝑣 1 𝑖=1

is minimized. 3.3

Efficient and reliable message propagation

Byzantine reliable broadcast protocols rely on all-to-all message propagation to ensure totality, which is critical for liveness (and also for safety in synchronous consensus). In the 4

Timer (𝜹) expires 𝑝

Dissemination tree

Votes in consensus as ACK Efficient yet best-effort broadcast Per-node retransmission

Node 𝑝 and its

Stage II

Stage I

descendants

Proposer

Redundant dissemination

retransmission

Figure 3. Illustration of proposal dissemination in tree-based and gossip-based Communication Networks. Through gossip, each node propagates messages to three neighbors. Assume 𝑓 = 5 and there are a total of 𝑁 = 3𝑓 + 1 = 16 nodes. Without redundant dissemination, if node 𝑝 crashes, its descendants in the tree can no longer receive the proposal. As they constitute more than 𝑓 nodes, the upper consensus layer can no longer guarantee liveness.

No ACK

No ACK

Figure 4. Two-stage reliable broadcast. and reliable proposal dissemination, we divide the proposaldissemination step into two stages: a highly-efficient treebased broadcast stage and a gossip-based re-transmission stage. The two stages are linked by the votes cast by individual nodes, with a timer triggering the transition from the first stage to the second (see Figure 4). As the message dissemination process is now split into two stages, we must re-examine the guarantees provided by the upper-layer consensus protocol. All properties provided by the original protocol must remain intact. For synchronous protocols, both safety and liveness must be carefully re-examined. For partially synchronous and asynchronous protocols, only liveness is affected, since safety is guaranteed by quorum intersection. Note that once the topology of 𝑁 nodes is recorded through consensus, the dissemination tree of each proposer is determined.

gossip-based communication model, each node instead propagates messages to all or a subset of its neighbors, such that totality is guaranteed with high probability. Although redundant propagation provides strong robustness guarantees, it (unnecessarily) consumes bandwidth in WANs, where bandwidth is both costly and shared among competing messages. Following the common principle of consensus protocol optimization that normal-case operations should be made as efficient as possible, such redundancy can be eliminated as long as messages can be delivered successfully. We however must deal with the cases where some non-leaf nodes are faulty. Note that, in fully connected settings, all-to-all flooding may be avoided through a pull-based dissemination mechanism [63], since proposers are required to send their proposals directly to all nodes. As long as the proposer is correct and the network remains synchronous, the protocol can make progress in a timely manner regardless of the presence of up to 𝑓 problematic nodes. Nodes that do not possess the original proposal can request other nodes to retransmit it. However, such a pull-based mechanism does not readily apply to tree dissemination, since in the tree any faulty non-leaf node may disrupt reliable message delivery, even when the proposer behaves correctly. Assume each node propagates messages to 𝐾 neighbors. Gossip-based dissemination incurs 𝐾 × 𝑁 × |𝑚| communication costs, while such value is (𝑁 − 1) × |𝑚| for tree-based dissemination. Furthermore, the latency to future proposers and the farthest node in the dissemination tree, and the maximum fanout should all be taken into account during tree construction. We observe that a common pattern in most BFT protocols is that every node votes for a proposal using a dedicated message, which naturally serves as an acknowledgment of the proposal’s delivery. Hence, towards achieving efficient

4

Duet

Duet is primarily a proposal-dissemination protocol co-designed for Tendermint, serving as a concrete instantiation of the ideas discussed in §3. In the following, we elaborate on each of the optimizations introduced above. 4.1

Greedy algorithm for arranging proposers

Given a weighted undirected graph 𝐺 = (𝑉 , 𝐸, 𝑤), where vertices represent nodes, edges represent network connections, and each edge weight denotes the RTT between the corresponding pair of nodes, the goal is to find a cycle that visits every vertex in 𝑉 at least once while minimizing the total weight: 𝑁 ∑︁

𝑤 (𝑣𝑖 , 𝑣𝑖+1 ),

𝑣 𝑁 +1 = 𝑣 1 .

𝑖=1

Each vertex in 𝐺 is connected to 𝑑 randomly selected vertices, where 𝑑 = log 𝑁 + 𝐷 and 𝐷 is a configurable parameter. So 𝐺 is a sparse graph. We first solve the all-pairs shortest-path problem by running Dijkstra’s algorithm 𝑁 times. Since the graph is sparse, using a binary heap yields a total time complexity of 𝑂 (𝑉 (𝑉 + 𝐸) log 𝑉 ) = 𝑂 (𝑁 2 log2 𝑁 ), as |𝑉 | = 𝑁 . We thus reduce the original problem to the Traveling Salesman Problem (TSP), which is still NP-hard. We 5

Algorithm 1 Proposer ring construction.

edges with exactly one endpoint in the tree. The edges are ranked by the propagation delays from the proposer to their endpoints outside the tree. In each iteration, we extract log 𝑛 edges with the smallest delays from the heap and select, among them, the edge with the minimum time according to the following formula.

1: function ConstructRing(𝐺)

⊲ 𝐺 = (𝑉 , 𝐸, 𝑤), |𝑉 | = 𝑁 𝑀 ← 𝐴𝑙𝑙𝑃𝑎𝑖𝑟𝑠𝐷𝑖 𝑗𝑘𝑠𝑡𝑟𝑎(𝐺) 𝑝 0 ← 𝑅𝑎𝑛𝑑𝑜𝑚(𝑉 ) 𝑈 ← 𝑉 \{𝑝 0 } for 𝑖 = 1..𝑁 − 1 do 𝑝𝑖 ← argmin𝑣 ∈𝑈 𝑀 [𝑝𝑖 −1 ] [𝑣] 𝑈 ← 𝑈 \{𝑝𝑖 } 8: return 𝑝 0, 𝑝 1, ..., 𝑝 𝑁 −1

2: 3: 4: 5: 6: 7:

𝑡𝑖𝑚𝑒 (𝑢, 𝑣) = 𝑑𝑒𝑙𝑎𝑦 (𝑣) + |𝑚| ×

where 𝑑𝑒𝑔(𝑢) is the fanout of 𝑢 after adding (𝑢, 𝑣) and 𝐵(𝑢, 𝑣) is the bandwidth of (𝑢, 𝑣). The first term in the formula represents the propagation delay and the second term approximates the transmission delay of message 𝑚 over edge (𝑢, 𝑣). The time complexity for constructing 𝑁 dissemination trees is thus 𝑂 (𝑁 2 log2 𝑁 ). Finally, if the estimated delays of two edges differ by less than 10%, we select the edge whose destination node is closer to the current proposer in the proposer sequence, thereby prioritizing the upcoming proposers. In practice, we approximate the bandwidth of edge (𝑢, 𝑣) from its RTT. Motivated by the window-limited TCP throughput model [39], in which the single-flow throughput over a long-haul link is inversely proportional to its RTT, we set
𝐵(𝑢, 𝑣) = min 𝐵 max, 𝜅/RTT(𝑢, 𝑣) ,

employ a simple greedy heuristic to obtain a practical solution by iteratively selecting the unvisited node closest to the current one. The procedure is depicted in Algorithm 1. The overall time complexity is dominated by the 𝑁 executions of Dijkstra’s algorithm. 4.2

𝑑𝑒𝑔(𝑢) , 𝐵(𝑢, 𝑣)

Multi-Factor-Aware Tree Dissemination

Tree-based dissemination schemes eliminate redundancy in the normal case, thereby minimizing bandwidth contention among concurrently transmitted messages. We aim to construct 𝑁 cost-efficient dissemination trees based on the network topology and latencies recorded in the ledger. We first simplify the problem by considering each proposer independently. The goal is to construct, for each proposer, a spanning tree (of 𝐺) that minimizes the maximum delay to any node. If only latency is considered, the optimal solution is a shortest-path tree (or a breadth-first search tree when all latencies are equal) rooted at the proposer. However, achieving efficient proposal dissemination requires taking several factors into account.

where 𝜅 and 𝐵 max are configurable parameters adapted to the target deployment and hardware. The payload size 𝑚 is likewise a configurable parameter, set to the block size adopted by the target deployment. 4.3

Tree dissemination with Tendermint

As we described in §2.3, Tendermint exchanges three types of messages in each round: proposal, prevote and precommit. We apply the idea discussed in §3.3 to propose and prevote, meaning that proposal messages are disseminated through the tree-based manner, while prevote messages act as an acknowledgement for the propose messages within the same round. Both prevote and precommit are still propagated through gossip. We focus primarily on the modifications made to vanilla Tendermint. The full pseudocode is postponed to Appendix A. Since Tendermint broadly relies on timers to drive progress, the best-effort broadcast must be seamlessly integrated with the existing timers without compromising liveness or other properties. Assume that, through gossip, node 𝑝 sends messages to the neighbors in peer(𝑝); through tree-based dissemination, 𝑝 instead sends messages to children(𝑝). Liveness guarantee. With the best-effort broadcast, we must take two specific problems into consideration. First, some correct nodes may not be able to receive the proposal through tree-based dissemination, even if the proposer is correct and the network is synchronous. To address this issue with Tendermint, sufficient time must be allowed for other correct nodes, especially the proposer, to retransmit the proposal via gossip.

• For geo-distributed deployments, proposals must be efficiently disseminated across regions while minimizing unnecessary long-haul transmissions (latency); • Given the limited bandwidth available at each node, its fanout must be constrained accordingly (bandwidth); • To enable rapid proposer handoff, each proposer’s dissemination tree should prioritize the next few proposers in the sequence (proposer rotation). The problem is to select 𝑁 − 1 edges that connect all nodes in 𝐺 while minimizing the maximum delay from the proposer to any node. Because a node’s bandwidth is shared among multiple connections, concurrent transmissions inevitably introduce bandwidth contention. Consequently, the delay of each edge cannot be computed independently, rendering the shortest-path tree solution inapplicable. We further simplify the bandwidth constraints by considering only the fanout of the forwarding node on the last hop, namely node 𝑢 when adding edge (𝑢, 𝑣). As 𝑁 may be large, we adopt a simple greedy algorithm that selects 𝑛 − 1 edges incrementally. Initially, only the proposer is included in the dissemination tree, and its outgoing edges are inserted into a binary heap, which maintains the 6

Node 0 Node 1

TREE phase

2𝑓 + 1 PREVOTE PREVOTE PRECOMMIT phase phase

𝑡𝑚𝑟 , TREE phase

COMMIT(𝑣) Node 0 Node 1

𝑣

Node 2

expires

2𝑓 + 1 PREVOTE PROPOSE PRECOMMIT phase phase

COMMIT(𝑣)

𝑣

Node 2

Node 3

Node 3

Node 4

Node 4

Node 5

Node 5

Node 6

Node 6 PROPOSAL

PREVOTE

PRECOMMIT

PROPOSAL

(a) Normal case

PREVOTE

PRECOMMIT

(b) Crash case

Figure 5. Examples for Duet tree-based dissemination (𝑛 = 7). In Figure ??, the propose phase is skipped as all correct nodes receive proposal 𝑣 during the tree phase. In Figure ??, nodes 2 and 4 crash; consequently, nodes 5 and 6 cannot receive proposal 𝑣 during the tree phase. When 𝑡𝑚𝑟𝑟,tree expires, other nodes relay 𝑣 to nodes 5 and 6 because neither node has sent a prevote message. We therefore explicitly introduce a tree-based broadcast phase, denoted by tree, along with a corresponding timer, 𝑡𝑚𝑟𝑟,tree , at the beginning of each round 𝑟 . Upon entering round 𝑟 , the proposer of round 𝑟 broadcasts its proposal through the tree-based dissemination, while other nodes start 𝑡𝑚𝑟𝑟,tree . Upon receiving a valid proposal 𝑣𝑟 for the first time, node 𝑝 proceeds as in vanilla Tendermint and broadcasts a prevote message for 𝑣𝑟 . If node 𝑝 is still in the tree phase, it also relays the proposal 𝑣𝑟 to its designated children in the dissemination tree and directly enters the prevote phase, thereby skipping the gossip-based propose phase. Otherwise, if timer 𝑡𝑚𝑟𝑟,tree expires without node 𝑝 receiving any valid proposal in round 𝑟 , 𝑝 proceeds to the propose phase and starts the timer 𝑡𝑚𝑟𝑟,propose , following vanilla Tendermint. After 𝑡𝑚𝑟𝑟,tree expires, if node 𝑝 receives any proposal 𝑣𝑟 , node 𝑝 relays 𝑣𝑟 to the nodes in peer(𝑝) from which it has not yet received prevote messages for 𝑣𝑟 , effectively falling back to gossip. When 𝑡𝑚𝑟𝑟,propose expires, node 𝑝 also follows vanilla Tendermint and broadcasts a prevote 𝑛𝑖𝑙 message in order to proceed to the prevote phase. Figure 5 illustrates examples of message dissemination in Duet. With the introduction of the tree phase, correct nodes that have not yet received a proposal must wait for both 𝑡𝑚𝑟𝑟,tree and 𝑡𝑚𝑟𝑟,propose to expire before sending a 𝑛𝑖𝑙 prevote. As long as Invariant 1 holds and 𝑡𝑚𝑟𝑟,propose ≥ 2Δ, the first correct node to enter round 𝑟 can receive 𝑣𝑟 before proceeding to the prevote phase. Reorg resilience. Introducing the best-effort broadcast to Tendermint gives rise to another subtle issue that should be addressed. Specifically, some correct nodes may have already advanced to height ℎ + 1, while others, including node 𝑝, may not yet have received the proposal at height ℎ. If the proposer of height ℎ + 1 is also 𝑝, it may not be

able to disseminate its proposal in time, thereby losing the opportunity to have its proposal committed. This situation actually breaks invariant 1, as 𝑝 may enter height ℎ + 1 only when it receives the proposal for height ℎ, which can take up to 𝑡𝑚𝑟𝑟,tree + Δ time. To address this issue, nodes entering a new height must wait for a sufficient amount of time before proceeding to the prevote phase. That is, the duration of 𝑡𝑚𝑟𝑟,propose of height ℎ + 1 must be sufficiently long to accommodate 𝑡𝑚𝑟𝑟,tree of height ℎ, i.e., 𝑡𝑚𝑟𝑟,propose ≥ 2Δ + 𝑡𝑚𝑟𝑟,tree . Finally, timers must be carefully configured. The settings of 𝑡𝑚𝑟𝑟,propose , 𝑡𝑚𝑟𝑟,prevote and 𝑡𝑚𝑟𝑟,precommit are key to ensuring liveness and are therefore closely tied to the assumed maximum network delay Δ. In contrast, 𝑡𝑚𝑟𝑟,tree can be set more aggressively to better reflect the actual network delay. We assume 𝑡𝑚𝑟𝑟,tree is set to 2𝛿 and 𝑡𝑚𝑟𝑟,propose is set to 2Δ + 2𝛿, where 𝛿 ≤ Δ. In contrast to vanilla Tendermint, Duet introduces an additional 2×𝑡𝑚𝑟𝑟,tree = 4𝛿 waiting time per round to handle situations where correct nodes need to advance to the next round (e.g., the proposer is faulty). Correctness argument. The safety property of Duet follows directly from that of Tendermint. We now focus on the property that, after GST, every proposal issued by a correct proposer is prevoted by all correct nodes, which is critical for liveness and reorg resilience. Assume node 𝑖 is the first correct node that enters round 𝑟 of height ℎ at time 𝑡, and node 𝑝 is the proposer of round 𝑟 . In vanilla Tendermint, node 𝑝 should enter round 𝑟 before time 𝑡 + Δ. In Duet, after GST, node 𝑝 should enter round 𝑟 and broadcast its proposal before time 𝑡 + Δ + 2𝛿, as the proposer of round 𝑟 − 1 (or height ℎ − 1) may take another 2𝛿 time to switch to the retransmission stage. At height ℎ and round 𝑟 , node 𝑝 first best-effort broadcasts its proposal before 𝑡 + Δ + 2𝛿. Then, node 𝑝 gossips its proposal before time 𝑡 + Δ + 4𝛿, at which time other nodes should already have their timers expired. 7

So, at time (𝑡 + 2𝛿) + (2Δ + 2𝛿), node 𝑖 should have received the proposal. Thus, every correct node receives the proposal before the propose timer expires. Further discussion. Topology visibility also introduces a deployment tradeoff. Exposing complete neighbor and latency information can improve tree quality but may also increase the attack surface by revealing information useful for topology inference or targeted attacks [27, 54]. To this end, deployments can mitigate this risk by exposing only a subset of each node’s links for tree construction. We analyze the performance impact of this limited-visibility setting in §5.2 and Figure 6.

5

Evaluation

5.1

Implementation and Experimental Setup

tree captures the balanced-tree dissemination structure used by Kauri [44], a state-of-the-art tree-based BFT protocol. All three prototypes use the same implementation for proposal buffering and pipelining. Nodes buffer proposal messages by height and the proposer proposes at height ℎ as soon as all preceding proposals—the prefix of height ℎ—are received. Thus, the evaluated approaches differ only in their proposal dissemination schemes, while vote dissemination, prefix buffering, and pipelining logic remain the same. Experimental setup. Unless otherwise specified, experiments run over 10 AWS regions: three regions in the US (N. Virginia, Ohio, and N. California), three in Europe (Ireland, London, and Frankfurt), and four in Asia-Pacific (Tokyo, Singapore, Sydney, and Mumbai). Each node runs on a m4.xlarge instance with 4 vCPUs and 16 GiB of memory. The nodes are split evenly across regions by default. Latency is measured from the time a proposal is issued to the time it is committed, and each transaction is 1 KB in size.

Implementation. We implement Duet on top of Tendermint [12] and libp2p [4]. The code is available at https: //github.com/Decentralized-Computing-Lab/Duet. Specifically, proposal messages are disseminated along each proposer’s dissemination tree, while prevote and precommit messages use libp2p’s gossipsub with target mesh degree set to 6. For each height, nodes record the mesh peers that sent prevote messages. When the tree-phase timer 𝑡𝑚𝑟𝑟,tree expires, the retransmission stage pushes the proposal only to those mesh peers from which no prevote has been observed, and sends the corresponding IHAVE messages to its non-mesh peers. To compare all protocols on an identical network, we use the same topology 𝐺 = (𝑉 , 𝐸, 𝑤) for Duet and both baselines, so that they differ only in how they disseminate proposals over it. The topology is fully connected at 𝑁 = 10, with average degree 20 at 𝑁 = 50 and 40 at 𝑁 ∈ {100, 300}. Its edge weights are the RTTs measured between the AWS regions of our deployment. From 𝐺, each Duet node deterministically derives the proposer ring (§4.1) and its dissemination trees (§4.2), and forwards each proposal to its children in the corresponding proposer’s tree. Since these constructions are deterministic functions of 𝐺, every node obtains identical structures without extra coordination. For tree construction, we instantiate the bandwidth model of §4.2 with 𝜅 = 20000 and 𝐵 max = 800 Mb/s, and set the payload size to |𝑚| = 10 MB. Baselines. We compare against two baselines implemented in the same prototype. For both protocols, prevote and precommit messages use the same gossipsub configuration as in Duet; only the dissemination of proposal messages differs. Gossip forwards each proposal over the same gossipsub mesh. K-ary tree disseminates each proposal along a perproposer balanced tree with branching factor 𝐾, assigning children level by level: Each parent takes as children up to 𝐾 of its neighbors in 𝐺 that have not yet been placed in the tree. We choose these two schemes as baselines because Gossip is the default dissemination mode in libp2p, while the K-ary

5.2

Normal-case performance

This experiment evaluates the normal-case scaling behavior of Duet and other protocols. We vary the node set from 𝑁 = 10 to 𝑁 = 300 on the balanced 10-region WAN deployment and gradually increase the batch size until each protocol is saturated. We set the K-ary branching factor to 𝐾 = 3 for 𝑁 = 10 and to 𝐾 = 5 for 𝑁 ∈ {50, 100, 300}. As Figure 6 shows, at 𝑁 = 10, Gossip is limited by redundant cross-region forwarding. With one node per region, mesh-based forwarding repeatedly consumes scarce WAN bandwidth. The K-ary tree performs considerably better at this scale. When 𝐾 = 3, the K-ary tree has limited depth, allowing upcoming proposers to receive the prefix quickly enough for the pipeline to utilize the available bandwidth efficiently. As a result, Duet has only a modest throughput advantage over the K-ary tree at 𝑁 = 10. For example, Duet reaches 14.07k tps with a corresponding latency of 1264 ms, while the K-ary tree reaches 11.94k tps with a corresponding latency of 1224 ms. The performance gap widens as the system scales to 𝑁 = 50 and 𝑁 = 100. By better accounting for geographic locality, Duet minimizes the distance traveled during proposal dissemination. In contrast, the K-ary tree selects children randomly from each node’s remaining neighbors. Moreover, the K-ary tree is limited by prefix delivery. These balanced trees may place later proposers behind additional inter-region hops and fail to prioritize upcoming proposers, thereby delaying prefix delivery and preventing later heights from entering the pipeline promptly. As a result, the proposal pipeline cannot fully utilize the available bandwidth, and throughput falls sharply relative to the 10-node case. At 𝑁 = 50, the K-ary tree reaches 5.36k tps with a corresponding latency of 2373 ms. Gossip similarly suffers from delayed prefix delivery, while its fixed target mesh degree further incurs costly redundant WAN traffic at every scale. At 𝑁 = 50, Gossip reaches 8

Latency (ms)

Duet

Duet-LimitedView

3000

1500

2000

1000

1000

500 0

K-ary tree

0

6

12

0

18

0

Throughput (ktps) N = 10

6

12

18

Gossip

4000 3000 2000 1000 0

0

Throughput (ktps) N = 50

6

12

18

24

Throughput (ktps) N = 100

Figure 6. Performance as the system scales from 𝑁 =10 to 𝑁 =100.

Throughput (tps)

Duet

K-ary tree 22,028

20k

15,160

10k

11,936 6,609

0

10

ℎ 2 , we say the pipeline depth is ℎ 1 − ℎ 2 . Duet reaches an average depth of 8, compared with 2 for the K-ary tree and 1 for Gossip. Consistent with this gap, Duet achieves 21.09k tps at this setting; the K-ary tree and Gossip reach 4.70k and 3.44k tps, respectively. The latency curves in Figure 6 reflect the same effect of pipeline utilization. Since latency is measured from the time the proposal is issued, deeper pipelining can increase throughput while individual blocks still wait for earlier heights to commit. Thus, the throughput gain does not always come with lower latency at the same batch size. At 𝑁 = 100, Duet reaches 21.09k tps at 3080 ms, while the K-ary tree reaches 4.70k tps at 3276 ms. Gossip shows lower latency because it has fewer blocks in flight, at the cost of much lower throughput. Figure 7 extends the scaling experiment to 𝑁 = 300. Duet sustains 20.5k tps at 𝑁 = 300, close to its 22.0k tps peak at 𝑁 = 100, while the K-ary tree and Gossip fall to 4.2k and 2.8k tps, respectively. Duet thus achieves 7.26× the throughput of Gossip at this scale. The modest drop from 𝑁 = 100 to 𝑁 = 300 likely reflects diminishing returns from deeper pipelining and increased gossip-based vote traffic as the number of nodes grows.

Gossip 20,504

17,081

5,473

4,943

3,762

3,442

4,212 2,821

50 100 300 Number of nodes (N)

Figure 7. Peak throughput as 𝑁 scales from 10 to 300.

only 3.40k tps with a corresponding latency of 1531 ms. For both baselines, the additional drop from 𝑁 = 50 to 𝑁 = 100 is smaller because the pipeline is already partially underutilized at 𝑁 = 50. Larger scale mainly worsens the same bottleneck rather than introducing a new one. Duet follows the opposite trend from 𝑁 = 10 to 𝑁 = 100. At larger scale, tree construction has a richer set of low-RTT candidate links for connecting nearby nodes and upcoming proposers. Prefix delivery becomes faster for consecutive heights, enabling deeper pipelining and higher bandwidth utilization. At 𝑁 = 50, Duet already improves to 16.57k tps with a corresponding latency of 2125 ms. Figure 6 also includes Duet-LimitedView at 𝑁 = 100, where nodes use the same topology but each node exposes only 20 links for tree construction. This limited visibility reduces the quality of the selected trees: Duet-LimitedView reaches 19.00k tps with 4196 ms latency, compared with 21.09k tps and 3080 ms for Duet. The result shows that richer link visibility improves tree quality, while the limited-view variant still remains well above the baselines. We use pipeline depth to explain the throughput gap at 𝑁 = 100 with the batch size set to 10k. If a proposer has proposed at height ℎ 1 while the latest committed height is

5.3

Ablation study

To isolate how dissemination and proposer order affect performance, we combine each of three proposal dissemination methods {Gossip, K-ary tree, Duet tree} with each of two proposer orders {random, greedy}. Gossip uses the same unstructured mesh as in §5.1, while the K-ary tree uses balanced per-proposer trees with 𝐾=5. The random order is generated by drawing a random permutation of nodes, whereas the greedy order is produced by the Dijkstra-greedy algorithm used throughout the rest of the evaluation. Under a random order, the Duet tree is still constructed by the rule of §4.2. All configurations share the same 100-node 10-region WAN deployment and the same workload (batch size 10k). 9

Gossip

K-ary tree

3100

1.829 1.5 25k 21,189 21,090 1.208 20k 16,695 13,592 12,016 1.0 15k 10k 0.5 0.574 5k 0.004 0.045 0 0.0

5s

Duet tree

2899

2.0

3s

2s

1s 500ms

4000 3000

latency (ms)

2784

3943

Pushes per node-height

Throughput (tps)

Throughput (tps)

25k random-order 21,090 greedy-order 20k 15k 10k 4,875 5k 3,479 6,885 4,698 3,442 0

3248

2000 1000 0

tree-phase timer

Figure 8. Ablation Study of Dissemination and Proposer Ordering (𝑁 =100, 10-region WAN, batch size 10k).

Figure 9. tree phase timer sensitivity (𝑁 =100, batch size 10k, fault-free).

Figure 8 shows that Gossip is almost insensitive to proposer order. Its mesh is unstructured: a proposal reaches the next proposer through multi-hop mesh dissemination and redundant forwarding, rather than along paths that account for geographic locality and prioritize upcoming proposers. As a result, replacing a random order with the greedy one barely changes throughput, from 3.44k to 3.48k tps (1.01×). The K-ary tree has the same limitation in a non-redundant setting. It avoids duplicate proposal traffic, but its balanced trees are constructed randomly. A greedy proposer order therefore does not ensure that the next proposer is close in the dissemination tree, so later heights still wait for prefix delivery before they can enter the pipeline. Its throughput improves only from 4.70k to 4.88k tps (1.04×). Duet improves most when dissemination trees and the greedy order are combined. The trees minimize propagation distance and prioritize upcoming proposers, while the greedy ordering places consecutive proposers closer to one another. As a result, prefixes are delivered more quickly, allowing more heights to enter the pipeline. With a random order, the Duet tree reaches 6.89k tps; with both mechanisms enabled, Duet reaches 21.09k tps, exceeding Gossip under the same greedy order by 6.06×.

mesh peers (degree 6) to which a node sends retransmission pushes at each height. With a 5 s or 3 s tree phase timer, retransmission is rarely triggered in the fault-free case: throughput remains around 21k tps and pushed peers stay near zero. At 2 s, some prevote messages arrive after the timer expires, so nodes start retransmission even though the tree would have completed dissemination. Throughput drops to 16.70k tps and latency rises to 3100 ms. At 1 s and 500 ms, this effect becomes more pronounced, as retransmission traffic rises above one pushed peer per node-height and throughput falls to 13.59k and 12.02k tps, respectively. The tree-phase timer is therefore a critical deployment-specific parameter that must be carefully tuned.

5.4

5.5

Ethereum-Like heterogeneous deployment

To better understand the performance of Duet under a more realistic deployment, we construct an Ethereum-like placement based on the country-level distribution of consensus nodes reported by Ethernodes [2]. We map each country to its nearest AWS region and normalize the resulting distribution to 100 nodes. The resulting placement is concentrated in Frankfurt (30 nodes) and N. Virginia (20 nodes), with a continental split of 39% North America, 46% Europe, and 15% Asia-Pacific. Full per-region counts are listed in Appendix B. Figure 10 shows that Duet retains a clear performance advantage under this skewed placement. Gossip and the K-ary tree do not explicitly leverage this regional skewness: Gossip forwards over an unstructured mesh, while the K-ary tree builds balanced trees without optimizing for regional placement. Duet better exploits this skewed placement because its multi-factor-aware trees prioritize low-latency paths within the node-dense Europe and US-East regions. Comparing the latencies at a throughput of approximately 13–14k tps in Figure 6 (𝑁 = 100) and Figure 10, Duet commits in 1493 ms under the skewed placement, versus 2269 ms under the uniform 100-node placement, owing to the greater geographic locality of nodes in the skewed deployment.

Timer Sensitivity

The gossip-based retransmission stage of Duet is highly sensitive to the duration of the tree-phase timer. A shorter timer starts retransmission earlier and can complete dissemination faster when crashes or network disturbances break the tree. However, if the timer is set too aggressively, it may expire even during normal execution before the prevote messages have been received. In that case, a node may treat slow prevote messages as missing acknowledgments and push the proposal to mesh peers that would have received it without retransmission. Figure 9 studies this effect in a 100-node, batch-size-10k setting without faults. The “push peers per node-height” metric reports the average number of 10

4000 3000 2000 1000 0

0

3

K-ary tree

6

9

Gossip

12

15

18

Latency (ms)

Latency (ms)

Duet

21

Duet

7,000 6,000 5,000 4,000 3,000 2,000 1,000 0

Gossip

K-ary tree

t inia Ohio fornia eland ndon nkfur Tokyo apore ydney li Ir Lo Fra g S a C Sin N.

irg .V

Throughput (ktps)

N

Figure 10. Throughput–latency under the Ethereum-like deployment (𝑁 =100).

Figure 11. Per-region commit latency under the Ethereumlike deployment (average vs. p95), 𝑁 =100, tx=10000.

Figure 11 further shows that this gain does not come at the expense of distant regions (𝑁 = 100, batch size 10k). Duet keeps average latency within 3.13–3.31 s across regions, with p95 latency between 4.12 s and 4.53 s. The tail of Gossip grows in Asia-Pacific, reaching 5.04 s at p95 in Sydney, while the K-ary tree has a p95 above 4.70 s in every region.

live descendants would then need repair. Duet reaches 17.5k tps at 5% crash and 16.2k tps at 10%. At 33% crash, however, both random and region failures require frequent retransmission, so the throughput of Duet approaches that of Gossip. Region crashes lose this advantage at such a ratio because three entire regions disappear: live regions that were reached through them are cut off as well, so the branches removed no longer consist of crashed nodes alone. This result is expected: once dissemination trees are insufficient to reach a quorum of nodes, progress is dominated by the 3 s tree phase timer and the subsequent gossip-based retransmission. Duet falls slightly below Gossip at this extreme because every height must first wait out the tree timer before retransmission begins, an overhead Gossip does not incur. At the same time, Duet does not fall far below Gossip because retransmission starts from nodes already reached by the tree: when the timer expires, these nodes can participate in disseminating the proposal, and their prevote messages help other nodes avoid redundant proposal retransmissions. Retransmission also does not require topology reconfiguration before it can make progress. Duet keeps the existing gossip mesh available for retransmission rather than waiting for a new dissemination tree to be installed. These results show that the tree phase preserves high normal-case throughput and remains effective under region-concentrated faults. When the dissemination tree is insufficient to reach a quorum, retransmission provides an additional path. Leader Failures. We next inject a single leader failure, which retransmission cannot mitigate because the failed leader never issues a proposal. Waiting out a crashed leader is inherent to all rotating-leader protocols, but Duet extends the wait: it first waits out one tree timer before entering the propose-timer path, which is itself lengthened to cover the preceding height’s tree timer (§4.3); Gossip incurs neither delay. As Figure 14 shows, Duet therefore resumes progress more slowly during the failed-leader window, but returns to its pre-failure throughput once a correct leader takes over. The tree timer is thus on the critical path of recovery for

5.6

Resilience under Failures and Limitations

We further distinguish between non-leader and leader failures. Non-leader failure experiments evaluate whether retransmission can complete proposal dissemination when internal relays fail, and how such failures affect performance. Leader failure experiments capture the timeout delay incurred when moving past a crashed proposer. Non-Leader Node Crashes. We vary the fraction of crashed non-leader nodes (5%, 10%, 33%) and exclude them from the proposer schedule. In random crash, failed nodes are scattered across the deployment. In region crash, they are geographically concentrated, with the 33% case disabling three full regions and three nodes in a fourth region. Figures 12 and 13 show that random crashes can disrupt multiple proposer trees because failed nodes often serve as internal relays. At 5% random crash, 11% of proposer trees reach fewer than two-thirds of nodes through the dissemination tree alone. At 10%, this rises to 43%. At 33%, no tree reaches a quorum through tree dissemination alone, as the crashed nodes leave barely two-thirds of nodes alive while virtually every tree loses internal relays. We then investigate how this reduced coverage affects performance. Nodes must wait for the 3 s tree phase timer to expire before retransmission, and the subsequent proposers cannot build their blocks until they receive the missing prefix. Thus, a small fraction of delayed dissemination can stall many subsequent heights: Duet drops to 10.7k tps at 5% random crash and 4.3k tps at 10%. Region-concentrated crashes are less harmful at moderate fault ratios: since Duet constructs its trees to account for geographic locality, nodes in a crashed region tend to form contiguous subtrees, so their failure removes whole branches of already-crashed nodes rather than internal relays whose 11

20,000 10,000

Duet + region crash

17508

Cumulative fraction of trees

Throughput (tps)

Duet + random crash

Gossip

16175

10673 3251 4299

0

5%

3121

2364 2354 2775

10%

Crashed-node fraction

Figure 12. Throughput leader/proposer crashes).

33%

1.00 0.75

5% crash

10% crash

33% crash

100% below quorum 43% below quorum

0.50 0.25

11% below quorum

2/3 quorum 0.00 0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0

Tree dissemination coverage

(no

Figure 13. CDF of per-tree dissemination coverage under random crash (5%, 10%, 33%), 100-node 10-region WAN.

both failure types, delaying retransmission in one and extending the failover window in the other; following §5.4, we set it to 3 s to sustain normal-case throughput, while deployments that prioritize faster recovery can choose a smaller value at the cost of more fault-free retransmission traffic.

introduces pipelined tree-based dissemination and aggregation for HotStuff-style protocol. Kauri triggers reconfiguration when the current tree is deemed insufficiently robust. Our design is complementary: rather than relying on tree reconfiguration, Duet uses consensus votes as acknowledgments and introduces per-node retransmission through gossip when best-effort dissemination fails to reach some nodes. Moreover, Duet optimizes dissemination trees using network topology, link latency, node fanout, and the positions of upcoming proposers. Network-layer optimization. Some work optimizes message dissemination without fundamentally modifying the upper-layer consensus protocol. Graphene [45] compresses block propagation through interactive set reconciliation, while Erlay [43] reduces Bitcoin transaction-relay overhead by replacing extensive flooding with efficient reconciliation. FRING [47] constructs a geography-aware P2P overlay for blockchain systems and introduces a broadcast algorithm that reduces redundant transmissions while retaining sufficient robustness. These approaches optimize the network layer but generally do not exploit consensus semantics. In contrast, Duet leverages acknowledgments provided by the consensus layer to eliminate redundant transmissions. Network-aware consensus. A broader body of work exploits network structure or locality to accelerate replication. Ring Paxos [38] organizes communication in a ring to achieve high-throughput atomic broadcast. WPaxos [7] uses multiple leaders and flexible quorums to reduce widearea communication costs. RS-Paxos [41] reduces network and storage overhead by integrating erasure coding with state-machine replication. These systems optimize consensus communication patterns, quorum placement, or datatransfer costs. In contrast, Duet jointly optimizes proposer rotation and proposal dissemination upon a P2P overlay. Recent work further explores adaptive consensus under changing network conditions. Crossword [29] dynamically trades off coded-shard assignment and quorum size in response to workload and network conditions, while using lazy follower gossip for failover. Aspen [46] introduces a

under

tree-phase timeout

Throughput (K tx/s)

20 0

Leader failure (a) Duet 3s

20

25

crash

faults

propose-timeout 5s+3s

30

35

40

45

25

30

35

2.5 Leader failure 0.0

(b) Gossip

5s

10

20

15

Time (s)

Figure 14. Performance under leader faults.

6

Related Work

P2P networks. P2P overlay networks have been extensively studied since the early 2000s [24, 36, 37, 49, 52, 57]. Most previous work focused on structured overlays, where a well-defined (and rather intricate) rule is used to guide node connections and routing. It would be interesting to further extend the ideas of Duet to structured overlays. More recently, Aradhya et al.[9] also proposed a cross-layer design in which the blockchain assists in maintaining its underlying P2P overlay and enables recovery from catastrophic failures. In contrast, we simply record network topologies and latencies via the blockchain and focus on proposer rotation and message propagation. Tree-based BFT dissemination and aggregation. Several BFT protocols organize communication using trees. ByzCoin [31] uses communication trees and collective signing to improve the scalability of Byzantine consensus. Kauri [44] 12

best-effort sequencing layer based on loosely synchronized clocks and network-delay estimates to accelerate speculative leaderless BFT replication. These approaches reinforce the potential of adapting consensus behavior to observed network conditions, although they target different replication models from rotating-leader consensus. In-network consensus acceleration. Another line of work moves ordering or consensus logic into programmable network devices. NOPaxos [34] replaces coordination on the normal path with an ordered-unreliable-multicast primitive implemented in the network. P4xos [21] implements Paxos logic directly in programmable forwarding devices, exposing consensus as a network service. Related programmablenetwork frameworks, such as Emu [58], simplify the prototyping of network services on reconfigurable hardware. These approaches achieve substantial acceleration by relying on datacenter-network functionality or programmable devices. By contrast, Duet retains host-based consensus and operates over conventional P2P networks without requiring specialized network hardware. Gossip protocols and topology-aware overlays. Gossipbased dissemination has long been studied as a robust communication primitive [11]. Its redundancy improves resilience, but it may incur unnecessary bandwidth consumption and propagation delay when directly applied to large proposals. Prior work has also investigated whether Internet latency and bandwidth can be approximated using tree-like models [48]. These observations motivate the design of Duet.

7

[7] Ailidani Ailijiang, Aleksey Charapko, Murat Demirbas, and Tevfik Kosar. 2020. WPaxos: Wide Area Network Flexible Consensus. IEEE Trans. Parallel Distrib. Syst. 31, 1 (Jan. 2020), 211–223. doi:10.1109/ TPDS.2019.2929793 [8] Elli Androulaki, Artem Barger, Vita Bortnikov, Christian Cachin, Konstantinos Christidis, Angelo De Caro, David Enyeart, Christopher Ferris, Gennady Laventman, Yacov Manevich, Srinivasan Muralidharan, Chet Murthy, Binh Nguyen, Manish Sethi, Gari Singh, Keith Smith, Alessandro Sorniotti, Chrysoula Stathakopoulou, Marko Vukolić, Sharon Weed Cocco, and Jason Yellick. 2018. Hyperledger Fabric: A Distributed Operating System for Permissioned Blockchains. In Proceedings of the Thirteenth EuroSys Conference (Porto, Portugal) (EuroSys ’18). Association for Computing Machinery, New York, NY, USA, Article 30, 15 pages. doi:10.1145/3190508.3190538 [9] Vijeth Aradhya, Seth Gilbert, and Aquinas Hobor. 2025. Robust overlays meet blockchains: On handling high churn and catastrophic failures. Theoretical Computer Science 1051 (2025), 115415. doi:10.1016/j. tcs.2025.115415 [10] Leemon Baird. 2016. The swirlds hashgraph consensus algorithm: Fair, fast, byzantine fault tolerance. Swirlds Tech Reports SWIRLDS-TR-201601, Tech. Rep 34 (2016), 9–11. [11] Ken Birman. 2007. The promise, and limitations, of gossip protocols. SIGOPS Oper. Syst. Rev. 41, 5 (Oct. 2007), 8–13. doi:10.1145/1317379. 1317382 [12] Ethan Buchman, Jae Kwon, and Zarko Milosevic. 2018. The latest gossip on BFT consensus. CoRR abs/1807.04938 (2018). arXiv:1807.04938 [13] Vitalik Buterin et al. 2014. A next-generation smart contract and decentralized application platform. white paper 3, 37 (2014). [14] Vitalik Buterin, Diego Hernandez, Thor Kamphefner, Khiem Pham, Zhi Qiao, Danny Ryan, Juhyeok Sin, Ying Wang, and Yan X. Zhang. 2020. Combining GHOST and Casper. CoRR abs/2003.03052 (2020). arXiv:2003.03052 https://arxiv.org/abs/2003.03052 [15] Christian Cachin, Rachid Guerraoui, and Luís Rodrigues. 2011. Introduction to reliable and secure distributed programming. Springer Science & Business Media. [16] Christian Cachin, Simon Schubert, and Marko Vukolić. 2016. Non-determinism in Byzantine Fault-Tolerant Replication. arXiv:1603.07351 [cs.DC] https://arxiv.org/abs/1603.07351 [17] Bengt Carlsson and Rune Gustavsson. 2001. The Rise and Fall of Napster - An Evolutionary Approach. In Active Media Technology, Jiming Liu, Pong C. Yuen, Chun-hung Li, Joseph Ng, and Toru Ishida (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 347–354. [18] Miguel Castro and Barbara Liskov. 1999. Practical Byzantine fault tolerance. In Proceedings of the Third Symposium on Operating Systems Design and Implementation (New Orleans, Louisiana, USA) (OSDI ’99). USENIX Association, USA, 173–186. [19] Scott A Crosby and Dan S Wallach. 2007. An analysis of bittorrent’s two kademlia-based dhts. (2007). [20] George Danezis, Lefteris Kokoris-Kogias, Alberto Sonnino, and Alexander Spiegelman. 2022. Narwhal and Tusk: A DAG-Based Mempool and Efficient BFT Consensus. In Proceedings of the Seventeenth European Conference on Computer Systems (Rennes, France) (EuroSys ’22). Association for Computing Machinery, New York, NY, USA, 34–50. [21] Huynh Tu Dang, Pietro Bressana, Han Wang, Ki Suh Lee, Noa Zilberman, Hakim Weatherspoon, Marco Canini, Fernando Pedone, and Robert Soulé. 2020. P4xos: Consensus as a Network Service. IEEE/ACM Trans. Netw. 28, 4 (aug 2020), 1726–1738. doi:10.1109/TNET.2020. 2992106 [22] Isaac Doidge, Raghavendra Ramesh, Nibesh Shrestha, and Joshua Tobkin. 2024. Moonshot: Optimizing Block Period and Commit Latency in Chain-Based Rotating Leader BFT. In 2024 54th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN). 470–482. doi:10.1109/DSN58291.2024.00052

Conclusion

We present Duet, a cross-layer design for improving rotatingleader consensus. Duet optimizes the proposer sequence by accounting for the geographic locality of nodes, thereby accelerating proposer rotation. By leveraging consensus votes as acknowledgments, Duet eliminates redundant proposal transmissions in the normal case while preserving reliable delivery under failures. We integrate Duet into Tendermint and libp2p and evaluate our prototype on Amazon EC2. It is promising to further integrate the ideas of Duet into multileader or leaderless consensus.

References [1] [n. d.]. AWS Latency Monitoring. https://www.cloudping.co/. Accessed: 2026-05-28. [2] [n. d.]. Ethernodes: Ethereum Mainnet Node Explorer. https://www. ethernodes.org/. Accessed: 2026-05-28. [3] [n. d.]. Gossip data dissemination protocol. https://hyperledger-fabric. readthedocs.io/en/release-1.2/gossip.html#gossip-protocol. Accessed: 2026-05-28. [4] [n. d.]. A modular p2p network stack. https://libp2p.io/. Accessed: 2026-05-28. [5] 2017. Filecoin: A Decentralized Storage Network. https://filecoin.io/ filecoin.pdf. [6] Ittai Abraham, Kartik Nayak, and Nibesh Shrestha. 2021. Optimal Good-case Latency for Rotating Leader Synchronous BFT. Cryptology ePrint Archive, Paper 2021/1138. doi:10.4230/LIPIcs.OPODIS.2021.27 13

In 2010 IEEE/IFIP International Conference on Dependable Systems and Networks (DSN). 527–536. doi:10.1109/DSN.2010.5544272 [39] Matthew Mathis, Jeffrey Semke, Jamshid Mahdavi, and Teunis Ott. 1997. The macroscopic behavior of the TCP congestion avoidance algorithm. ACM SIGCOMM Computer Communication Review 27, 3 (1997), 67–82. [40] Petar Maymounkov and David Mazières. 2002. Kademlia: A Peer-toPeer Information System Based on the XOR Metric. In Revised Papers from the First International Workshop on Peer-to-Peer Systems (IPTPS ’01). Springer-Verlag, Berlin, Heidelberg, 53–65. [41] Shuai Mu, Kang Chen, Yongwei Wu, and Weimin Zheng. 2014. When paxos meets erasure code: reduce network and storage cost in state machine replication. In Proceedings of the 23rd International Symposium on High-Performance Parallel and Distributed Computing (Vancouver, BC, Canada) (HPDC ’14). Association for Computing Machinery, New York, NY, USA, 61–72. doi:10.1145/2600212.2600218 [42] Satoshi Nakamoto. 2008. Bitcoin: A Peer-to-Peer Electronic Cash System. https://bitcoin.org/bitcoin.pdf. [43] Gleb Naumenko, Gregory Maxwell, Pieter Wuille, Alexandra Fedorova, and Ivan Beschastnikh. 2019. Erlay: Efficient Transaction Relay for Bitcoin. In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security (London, United Kingdom) (CCS ’19). Association for Computing Machinery, New York, NY, USA, 817–831. doi:10.1145/3319535.3354237 [44] Ray Neiheiser, Miguel Matos, and Luís Rodrigues. 2021. Kauri: Scalable BFT Consensus with Pipelined Tree-Based Dissemination and Aggregation. In Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles. Association for Computing Machinery, New York, NY, USA, 35–48. [45] A. Pinar Ozisik, Gavin Andresen, Brian N. Levine, Darren Tapp, George Bissias, and Sunny Katkuri. 2019. Graphene: efficient interactive set reconciliation applied to blockchain propagation. In Proceedings of the ACM Special Interest Group on Data Communication (Beijing, China) (SIGCOMM ’19). Association for Computing Machinery, New York, NY, USA, 303–317. doi:10.1145/3341302.3342082 [46] Daniel Qian, Xiyu Hao, Jinkun Geng, Yuncheng Yao, Aurojit Panda, Jinyang Li, and Anirudh Sivaraman. 2026. Revisiting Speculative Leaderless Protocols for Low-Latency BFT Replication. arXiv:2601.03390 [cs.DC] https://arxiv.org/abs/2601.03390 [47] Haoran Qiu, Tao Ji, Shixiong Zhao, Xusheng Chen, Ji Qi, Heming Cui, and Sen Wang. 2023. A Geography-Based P2P Overlay Network for Fast and Robust Blockchain Systems. IEEE Transactions on Services Computing 16, 3 (2023), 1572–1588. doi:10.1109/TSC.2022.3189667 [48] Venugopalan Ramasubramanian, Dahlia Malkhi, Fabian Kuhn, Mahesh Balakrishnan, Archit Gupta, and Aditya Akella. 2009. On the treeness of internet latency and bandwidth. In Proceedings of the Eleventh International Joint Conference on Measurement and Modeling of Computer Systems (Seattle, WA, USA) (SIGMETRICS ’09). Association for Computing Machinery, New York, NY, USA, 61–72. doi:10.1145/1555349.1555357 [49] Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, and Scott Shenker. 2001. A Scalable Content-Addressable Network. In Proceedings of the 2001 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (San Diego, California, USA) (SIGCOMM ’01). Association for Computing Machinery, New York, NY, USA, 161–172. doi:10.1145/383059.383072 [50] M. Ripeanu. 2001. Peer-to-peer architecture case study: Gnutella network. In Proceedings First International Conference on Peer-to-Peer Computing. 99–100. doi:10.1109/P2P.2001.990433 [51] Team Rocket, Maofan Yin, Kevin Sekniqi, Robbert van Renesse, and Emin Gün Sirer. 2019. Scalable and probabilistic leaderless BFT consensus through metastability. arXiv preprint arXiv:1906.08936 (2019).

[23] Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. 1988. Consensus in the Presence of Partial Synchrony. J. ACM 35, 2 (April 1988), 288–323. doi:10.1145/42282.42283 [24] Michael Feldmann, Christian Scheideler, and Stefan Schmid. 2020. Survey on Algorithms for Self-Stabilizing Overlay Networks. ACM Comput. Surv. 53, 4, Article 74 (jul 2020), 24 pages. doi:10.1145/3397190 [25] Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. 1985. Impossibility of distributed consensus with one faulty process. J. ACM 32, 2 (apr 1985), 374–382. doi:10.1145/3149.214121 [26] G. Golan Gueta, I. Abraham, S. Grossman, D. Malkhi, B. Pinkas, M. Reiter, D. Seredinschi, O. Tamir, and A. Tomescu. 2019. SBFT: A Scalable and Decentralized Trust Infrastructure. In 2019 49th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN). 568–580. [27] Ethan Heilman, Alison Kendler, Aviv Zohar, and Sharon Goldberg. 2015. Eclipse Attacks on Bitcoin’s Peer-to-Peer Network. In 24th USENIX Security Symposium (USENIX Security 15). 129–144. [28] Karla L Hoffman, Manfred Padberg, Giovanni Rinaldi, et al. 2013. Traveling salesman problem. Encyclopedia of operations research and management science 1 (2013), 1573–1578. [29] Guanzhou Hu, Yiwei Chen, Andrea Arpaci-Dusseau, and Remzi ArpaciDusseau. 2025. Crossword: Adaptive Consensus for Dynamic DataHeavy Workloads. arXiv:2509.07157 [cs.DC] https://arxiv.org/abs/ 2509.07157 [30] Rongji Huang, Xiangzhe Wang, Xiaofeng Yan, Lei Fan, Guangtao Xue, and Shengyun Liu. 2025. Chitu: Avoiding Unnecessary Fallback in Byzantine Consensus. In 2025 USENIX Annual Technical Conference (USENIX ATC 25). USENIX Association, Boston, MA, 923–942. https: //www.usenix.org/conference/atc25/presentation/huang-rongji [31] Eleftherios Kokoris-Kogias, Philipp Jovanovic, Nicolas Gailly, Ismail Khoffi, Linus Gasser, and Bryan Ford. 2016. Enhancing bitcoin security and performance with strong consistency via collective signing. In Proceedings of the 25th USENIX Conference on Security Symposium (Austin, TX, USA) (SEC’16). USENIX Association, USA, 279–296. [32] Ramakrishna Kotla, Lorenzo Alvisi, Mike Dahlin, Allen Clement, and Edmund Wong. 2010. Zyzzyva: Speculative Byzantine Fault Tolerance. ACM Trans. Comput. Syst. 27, 4, Article 7 (jan 2010), 39 pages. [33] Jae Kwon and Ethan Buchman. 2019. Cosmos whitepaper. A Netw. Distrib. Ledgers 27, 1-32 (2019), 24. [34] Jialin Li, Ellis Michael, Naveen Kr. Sharma, Adriana Szekeres, and Dan R. K. Ports. 2016. Just say no to paxos overhead: replacing consensus with network ordering. In Proceedings of the 12th USENIX Conference on Operating Systems Design and Implementation (Savannah, GA, USA) (OSDI’16). USENIX Association, USA, 467–483. [35] Shengyun Liu, Wenbo Xu, Chen Shan, Xiaofeng Yan, Tianjing Xu, Bo Wang, Lei Fan, Fuxi Deng, Ying Yan, and Hui Zhang. 2023. Flexible Advancement in Asynchronous BFT Consensus. In Proceedings of the 29th Symposium on Operating Systems Principles (Koblenz, Germany) (SOSP ’23). Association for Computing Machinery, New York, NY, USA, 264–280. doi:10.1145/3600006.3613164 [36] Dmitri Loguinov, Anuj Kumar, Vivek Rai, and Sai Ganesh. 2003. GraphTheoretic Analysis of Structured Peer-to-Peer Systems: Routing Distances and Fault Resilience. In Proceedings of the 2003 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (Karlsruhe, Germany) (SIGCOMM ’03). Association for Computing Machinery, New York, NY, USA, 395–406. doi:10.1145/863955.863999 [37] Dahlia Malkhi, Moni Naor, and David Ratajczak. 2002. Viceroy: a scalable and dynamic emulation of the butterfly. In Proceedings of the Twenty-First Annual Symposium on Principles of Distributed Computing (Monterey, California) (PODC ’02). Association for Computing Machinery, New York, NY, USA, 183–192. doi:10.1145/571825.571857 [38] Parisa Jalili Marandi, Marco Primi, Nicolas Schiper, and Fernando Pedone. 2010. Ring Paxos: A high-throughput atomic broadcast protocol. 14

A

[52] Antony I. T. Rowstron and Peter Druschel. 2001. Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-toPeer Systems. In Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg (Middleware ’01). SpringerVerlag, Berlin, Heidelberg, 329–350. [53] Fred B. Schneider. 1990. Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial. ACM Comput. Surv. 22, 4 (Dec. 1990), 299–319. doi:10.1145/98163.98167 [54] Ruisheng Shi, Yuxuan Liang, Zijun Guo, Qin Wang, Lina Lan, Chenfeng Wang, and Zhuoyi Zheng. 2026. Eclipse Attacks on Ethereum’s Peerto-Peer Network. In Proceedings of the ACM Web Conference 2026. 2740–2751. [55] Alexander Spiegelman, Neil Giridharan, Alberto Sonnino, and Lefteris Kokoris-Kogias. 2022. Bullshark: DAG BFT Protocols Made Practical. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security (Los Angeles, CA, USA) (CCS ’22). Association for Computing Machinery, New York, NY, USA, 2705–2718. doi:10.1145/3548606.3559361 [56] Chrysoula Stathakopoulou, Matej Pavlovic, and Marko Vukolić. 2022. State Machine Replication Scalability Made Simple. In Proceedings of the Seventeenth European Conference on Computer Systems (Rennes, France) (EuroSys ’22). Association for Computing Machinery, New York, NY, USA, 17–33. doi:10.1145/3492321.3519579 [57] Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, and Hari Balakrishnan. 2001. Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications. In Proceedings of the 2001 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (San Diego, California, USA) (SIGCOMM ’01). Association for Computing Machinery, New York, NY, USA, 149–160. doi:10.1145/383059.383071 [58] Nik Sultana, Salvator Galea, David Greaves, Marcin Wojcik, Jonny Shipton, Richard Clegg, Luo Mai, Pietro Bressana, Robert Soulé, Richard Mortier, Paolo Costa, Peter Pietzuch, Jon Crowcroft, Andrew W Moore, and Noa Zilberman. 2017. Emu: Rapid Prototyping of Networking Services. In 2017 USENIX Annual Technical Conference (USENIX ATC 17). USENIX Association, Santa Clara, CA, 459–471. https://www.usenix. org/conference/atc17/technical-sessions/presentation/sultana [59] Dennis Trautwein, Aravindh Raman, Gareth Tyson, Ignacio Castro, Will Scott, Moritz Schubotz, Bela Gipp, and Yiannis Psaras. 2022. Design and Evaluation of IPFS: A Storage Layer for the Decentralized Web. In Proceedings of the ACM SIGCOMM 2022 Conference (Amsterdam, Netherlands) (SIGCOMM ’22). Association for Computing Machinery, New York, NY, USA, 739–752. doi:10.1145/3544216.3544232 [60] Vytautas Tumas, Sean Rivera, Damien Magoni, and Radu State. 2023. Topology Analysis of the XRP Ledger. In Proceedings of the 38th ACM/SIGAPP Symposium on Applied Computing (Tallinn, Estonia) (SAC ’23). Association for Computing Machinery, New York, NY, USA, 1277–1284. doi:10.1145/3555776.3577611 [61] Yann Vonlanthen, Jakub Sliwinski, Massimo Albarello, and Roger Wattenhofer. 2024. Banyan: Fast Rotating Leader BFT. In Proceedings of the 25th International Middleware Conference (Hong Kong, Hong Kong) (Middleware ’24). Association for Computing Machinery, New York, NY, USA, 494–507. doi:10.1145/3652892.3700788 [62] Maofan Yin, Dahlia Malkhi, Michael K. Reiter, Guy Golan Gueta, and Ittai Abraham. 2019. HotStuff: BFT Consensus with Linearity and Responsiveness. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (Toronto ON, Canada) (PODC ’19). Association for Computing Machinery, New York, NY, USA, 347–356. [63] Siyuan Zhou and Shuai Mu. 2021. Fault-Tolerant Replication with Pull-Based Consensus in MongoDB. In 18th USENIX Symposium on Networked Systems Design and Implementation (NSDI 21). USENIX Association, 687–703. https://www.usenix.org/conference/nsdi21/ presentation/zhou

Pseudocode of Duet Tendermint

We present the pseudocode of Duet Tendermint in Algorithms 2 and 3, which respectively describes the events and functions. We highlight the modifications to Tendermint in grey .

B

Per-Region Node Placement

Table 1 gives the exact per-region node counts for the Ethereumrealistic deployment of Section 5.5, derived as described there and renormalized to 100 nodes. Counts are taken from Ethernodes [2] (by node count) and mapped to the nearest supported AWS region. Table 1. Per-region node counts for the Ethereum-realistic deployment (100 nodes). AWS region (location)

15

nodes

North America us-east-1 (Virginia) us-east-2 (Ohio) us-west-1 (N. California) subtotal

20 10 9 39

Europe eu-central-1 (Frankfurt) eu-west-1 (Ireland) eu-west-2 (London) subtotal

30 12 4 46

Asia-Pacific ap-northeast-1 (Tokyo) ap-southeast-1 (Singapore) ap-southeast-2 (Sydney) ap-south-1 (Mumbai) subtotal

7 6 2 0 15

Total

100

Algorithm 2 Tendermint code for node 𝑝: events. Init: ℎ𝑝 ← 0, 𝑟𝑜𝑢𝑛𝑑𝑝 ← 0, 𝑠𝑡𝑒𝑝 𝑝 ∈ {𝑏𝑒𝑠𝑡, 𝑝𝑟𝑜𝑝𝑜𝑠𝑒, 𝑝𝑟𝑒𝑣𝑜𝑡𝑒, 𝑝𝑟𝑒𝑐𝑜𝑚𝑚𝑖𝑡 } , 𝑑𝑒𝑐𝑖𝑠𝑖𝑜𝑛𝑝 [ ] ← 𝑛𝑖𝑙 , 𝑙𝑜𝑐𝑘𝑒𝑑𝑉 𝑎𝑙𝑢𝑒𝑝 ← 𝑛𝑖𝑙 , 𝑙𝑜𝑐𝑘𝑒𝑑𝑅𝑜𝑢𝑛𝑑𝑝 ← −1, 𝑣𝑎𝑙𝑖𝑑𝑉 𝑎𝑙𝑢𝑒𝑝 ← 𝑛𝑖𝑙 , 𝑣𝑎𝑙𝑖𝑑𝑅𝑜𝑢𝑛𝑑𝑝 ← −1

1: upon start do 𝑠𝑡𝑎𝑟𝑡𝑅𝑜𝑢𝑛𝑑 (0) 2: upon ⟨ proposal, ℎ𝑝 , 𝑟𝑜𝑢𝑛𝑑𝑝 , 𝑣, −1⟩ from proposer (ℎ𝑝 , 𝑟𝑜𝑢𝑛𝑑𝑝 ) while 𝑠𝑡𝑒𝑝𝑝 = 𝑝𝑟𝑜𝑝𝑜𝑠𝑒 ∨𝑠𝑡𝑒𝑝𝑝 = 𝑏𝑒𝑠𝑡 do 3: if 𝑣𝑎𝑙𝑖𝑑 (𝑣) ∧ (𝑙𝑜𝑐𝑘𝑒𝑑𝑅𝑜𝑢𝑛𝑑𝑝 = −1 ∨ 𝑙𝑜𝑐𝑘𝑒𝑑𝑉 𝑎𝑙𝑢𝑒𝑝 = 𝑣) then 4: broadcast ⟨ prevote, ℎ𝑝 , 𝑟𝑜𝑢𝑛𝑑𝑝 , ℎ𝑎𝑠ℎ (𝑣) ⟩ 5: if 𝑠𝑡𝑒𝑝 𝑝 = 𝑝𝑟𝑜𝑝𝑜𝑠𝑒 then 6: 7: 8: 9:

𝐺𝑜𝑠𝑠𝑖𝑝 (ℎ𝑝 , 𝑟𝑜𝑢𝑛𝑑𝑝 ) else broadcast ⟨ prevote, ℎ𝑝 , 𝑟𝑜𝑢𝑛𝑑𝑝 , 𝑛𝑖𝑙 ⟩ 𝑠𝑡𝑒𝑝𝑝 ← 𝑝𝑟𝑒𝑣𝑜𝑡𝑒

10: upon ⟨ proposal, ℎ𝑝 , 𝑟𝑜𝑢𝑛𝑑𝑝 , 𝑣, 𝑣𝑟 ⟩ from proposer (ℎ𝑝 , 𝑟𝑜𝑢𝑛𝑑𝑝 ) AND 2𝑓 + 1 ⟨ prevote, ℎ𝑝 , 𝑣𝑟, ℎ𝑎𝑠ℎ (𝑣) ⟩ while (𝑠𝑡𝑒𝑝𝑝 = 𝑝𝑟𝑜𝑝𝑜𝑠𝑒 ∨𝑠𝑡𝑒𝑝𝑝 = 𝑏𝑒𝑠𝑡 )∧(𝑣𝑟 ≥ 0 ∧ 𝑣𝑟 < 11: 12: 13: 14: 15: 16: 17:

𝑟𝑜𝑢𝑛𝑑𝑝 ) do if 𝑣𝑎𝑙𝑖𝑑 (𝑣) ∧ (𝑙𝑜𝑐𝑘𝑒𝑑𝑅𝑜𝑢𝑛𝑑𝑝 ≤ 𝑣𝑟 ∨ 𝑙𝑜𝑐𝑘𝑒𝑑𝑉 𝑎𝑙𝑢𝑒𝑝 = 𝑣) then broadcast ⟨ prevote, ℎ𝑝 , 𝑟𝑜𝑢𝑛𝑑𝑝 , ℎ𝑎𝑠ℎ (𝑣) ⟩ if 𝑠𝑡𝑒𝑝 𝑝 = 𝑝𝑟𝑜𝑝𝑜𝑠𝑒 then

𝐺𝑜𝑠𝑠𝑖𝑝 (ℎ𝑝 , 𝑟𝑜𝑢𝑛𝑑𝑝 ) else broadcast ⟨ prevote, ℎ𝑝 , 𝑟𝑜𝑢𝑛𝑑𝑝 , 𝑛𝑖𝑙 ⟩ 𝑠𝑡𝑒𝑝𝑝 ← 𝑝𝑟𝑒𝑣𝑜𝑡𝑒

18: upon 2𝑓 + 1 ⟨ prevote, ℎ𝑝 , 𝑟𝑜𝑢𝑛𝑑𝑝 , ∗⟩ while 𝑠𝑡𝑒𝑝𝑝 = 𝑝𝑟𝑒𝑣𝑜𝑡𝑒 for the first time do 19: schedule 𝑂𝑛𝑇 𝑖𝑚𝑒𝑜𝑢𝑡𝑃𝑟𝑒𝑣𝑜𝑡𝑒 (ℎ𝑝 , 𝑟𝑜𝑢𝑛𝑑𝑝 ) to be executed after 𝑡𝑖𝑚𝑒𝑜𝑢𝑡𝑃𝑟𝑒𝑣𝑜𝑡𝑒 (𝑟𝑜𝑢𝑛𝑑𝑝 ) (2Δ′ time) 20: upon ⟨ proposal, ℎ𝑝 , 𝑟𝑜𝑢𝑛𝑑𝑝 , 𝑣, ∗⟩ from proposer (ℎ𝑝 , 𝑟𝑜𝑢𝑛𝑑𝑝 ) AND 2𝑓 + 1 ⟨ prevote, ℎ𝑝 , 𝑟𝑜𝑢𝑛𝑑𝑝 , ℎ𝑎𝑠ℎ (𝑣) ⟩ while 𝑣𝑎𝑙𝑖𝑑 (𝑣) ∧ 𝑠𝑡𝑒𝑝𝑝 ≥ 𝑝𝑟𝑒𝑣𝑜𝑡𝑒 for the first time do 21: if 𝑠𝑡𝑒𝑝 𝑝 = 𝑝𝑟𝑒𝑣𝑜𝑡𝑒 then 22: 𝑙𝑜𝑐𝑘𝑒𝑑𝑉 𝑎𝑙𝑢𝑒𝑝 ← 𝑣 23: 𝑙𝑜𝑐𝑘𝑒𝑑𝑅𝑜𝑢𝑛𝑑𝑝 ← 𝑟𝑜𝑢𝑛𝑑𝑝 24: broadcast ⟨ precommit, ℎ𝑝 , 𝑟𝑜𝑢𝑛𝑑𝑝 , ℎ𝑎𝑠ℎ (𝑣) ⟩ 25: 𝑠𝑡𝑒𝑝𝑝 ← 𝑝𝑟𝑒𝑐𝑜𝑚𝑚𝑖𝑡 26: 𝑣𝑎𝑙𝑖𝑑𝑉 𝑎𝑙𝑢𝑒𝑝 ← 𝑣 27: 𝑣𝑎𝑙𝑖𝑑𝑅𝑜𝑢𝑛𝑑𝑝 ← 𝑟𝑜𝑢𝑛𝑑𝑝 28: upon 2𝑓 + 1 ⟨ prevote, ℎ𝑝 , 𝑟𝑜𝑢𝑛𝑑𝑝 , 𝑛𝑖𝑙 ⟩ while 𝑠𝑡𝑒𝑝𝑝 = 𝑝𝑟𝑒𝑣𝑜𝑡𝑒 do 29: broadcast ⟨ precommit, ℎ𝑝 , 𝑟𝑜𝑢𝑛𝑑𝑝 , 𝑛𝑖𝑙 ⟩ 30: 𝑠𝑡𝑒𝑝𝑝 ← 𝑝𝑟𝑒𝑐𝑜𝑚𝑚𝑖𝑡 31: upon receiving 2𝑓 + 1 ⟨ precommit, ℎ𝑝 , 𝑟𝑜𝑢𝑛𝑑𝑝 , ∗, ∗⟩ for the first time do 32: schedule 𝑂𝑛𝑇 𝑖𝑚𝑒𝑜𝑢𝑡𝑃𝑟𝑒𝑐𝑜𝑚𝑚𝑖𝑡 (ℎ𝑝 , 𝑟𝑜𝑢𝑛𝑑𝑝 ) to be executed after 𝑡𝑖𝑚𝑒𝑜𝑢𝑡𝑃𝑟𝑒𝑐𝑜𝑚𝑚𝑖𝑡 (𝑟𝑜𝑢𝑛𝑑𝑝 ) (2Δ′ time) 33: upon ⟨ proposal, ℎ𝑝 , 𝑟, 𝑣, ∗⟩ from proposer (ℎ𝑝 , 𝑟 ) AND 2𝑓 + 1 ⟨ precommit, ℎ𝑝 , 𝑟, ℎ𝑎𝑠ℎ (𝑣) ⟩ while 𝑑𝑒𝑐𝑖𝑠𝑖𝑜𝑛𝑝 [ℎ𝑝 ] = 𝑛𝑖𝑙 do 34: if 𝑣𝑎𝑙𝑖𝑑 (𝑣) then 35: 𝑑𝑒𝑐𝑖𝑠𝑖𝑜𝑛[ℎ𝑝 ] ← 𝑣 36: ℎ𝑝 ← ℎ𝑝 + 1 37: reset 𝑙𝑜𝑐𝑘𝑒𝑑𝑅𝑜𝑢𝑛𝑑𝑝 , 𝑙𝑜𝑐𝑘𝑒𝑑𝑉 𝑎𝑙𝑢𝑒𝑝 , 𝑣𝑎𝑙𝑖𝑑𝑅𝑜𝑢𝑛𝑑𝑝 , 𝑣𝑎𝑙𝑖𝑑𝑉 𝑎𝑙𝑢𝑒𝑝 to initial values and empty message log 38: 𝑆𝑡𝑎𝑟𝑡𝑅𝑜𝑢𝑛𝑑 (0) 39: upon 𝑓 + 1 ⟨∗, ℎ𝑝 , 𝑟𝑜𝑢𝑛𝑑, ∗, ∗, ∗⟩ with 𝑟𝑜𝑢𝑛𝑑 > 𝑟𝑜𝑢𝑛𝑑𝑝 do 40: 𝑆𝑡𝑎𝑟𝑡𝑅𝑜𝑢𝑛𝑑 (𝑟𝑜𝑢𝑛𝑑 )

16

Algorithm 3 Tendermint code for node 𝑝: functions. 1: Function 𝑠𝑡𝑎𝑟𝑡𝑅𝑜𝑢𝑛𝑑 (𝑟𝑜𝑢𝑛𝑑 ) : 2: 𝑟𝑜𝑢𝑛𝑑𝑝 ← 𝑟𝑜𝑢𝑛𝑑 3: 𝑠𝑡𝑒𝑝𝑝 ← 𝑏𝑒𝑠𝑡 4: if proposer (ℎ𝑝 , 𝑟𝑜𝑢𝑛𝑑𝑝 ) = 𝑝 then 5: if 𝑣𝑎𝑙𝑖𝑑𝑉 𝑎𝑙𝑢𝑒𝑝 ≠ 𝑛𝑖𝑙 then 6: 𝑝𝑟𝑜𝑝𝑜𝑠𝑎𝑙 ← 𝑣𝑎𝑙𝑖𝑑𝑉 𝑎𝑙𝑢𝑒𝑝 7: else 8: 𝑝𝑟𝑜𝑝𝑜𝑠𝑎𝑙 ← 𝑔𝑒𝑡𝑉 𝑎𝑙𝑢𝑒 ( ) Tree-broadcast ⟨ proposal, ℎ𝑝 , 𝑟𝑜𝑢𝑛𝑑𝑝 , proposal, 𝑣𝑎𝑙𝑖𝑑𝑅𝑜𝑢𝑛𝑑𝑝 ⟩ 9: 10: else 11: schedule 𝑂𝑛𝑇 𝑖𝑚𝑒𝑜𝑢𝑡𝐷𝑖𝑠𝑠 (ℎ𝑝 , 𝑟𝑜𝑢𝑛𝑑𝑝 ) to be executed after 𝑡𝑖𝑚𝑒𝑜𝑢𝑡𝐷𝑖𝑠𝑠 (𝑟𝑜𝑢𝑛𝑑𝑝 ) (2𝛿 time) 12: Function 𝑂𝑛𝑇 𝑖𝑚𝑒𝑜𝑢𝑡𝐷𝑖𝑠𝑠 (ℎ𝑒𝑖𝑔ℎ𝑡, 𝑟𝑜𝑢𝑛𝑑 ) : 13:

if ℎ𝑒𝑖𝑔ℎ𝑡 = ℎ𝑝 ∧ 𝑟𝑜𝑢𝑛𝑑 = 𝑟𝑜𝑢𝑛𝑑𝑝 ∧ 𝑠𝑡𝑒𝑝 𝑝 = 𝑏𝑒𝑠𝑡 then

14:

schedule 𝑂𝑛𝑇 𝑖𝑚𝑒𝑜𝑢𝑡𝑃𝑟𝑜𝑝𝑜𝑠𝑒 (ℎ𝑝 , 𝑟𝑜𝑢𝑛𝑑𝑝 ) to be executed after 𝑡𝑖𝑚𝑒𝑜𝑢𝑡𝑃𝑟𝑜𝑝𝑜𝑠𝑒 (𝑟𝑜𝑢𝑛𝑑𝑝 ) (2Δ + 2𝛿 time)

15:

𝑠𝑡𝑒𝑝𝑝 ← 𝑝𝑟𝑜𝑝𝑜𝑠𝑒

16: 17:

else

𝐺𝑜𝑠𝑠𝑖𝑝 (ℎ𝑒𝑖𝑔ℎ𝑡, 𝑟𝑜𝑢𝑛𝑑 )

18: Function 𝐺𝑜𝑠𝑠𝑖𝑝 (ℎ𝑒𝑖𝑔ℎ𝑡, 𝑟𝑜𝑢𝑛𝑑 ) : 19: 20: 21:

for ∀𝑝 ′ ∈ peer (𝑝 ) do if not received ⟨ prevote, ℎ𝑒𝑖𝑔ℎ𝑡, 𝑟𝑜𝑢𝑛𝑑, ∗⟩ from 𝑝 ′ then send ⟨ proposal, ℎ𝑒𝑖𝑔ℎ𝑡, 𝑟𝑜𝑢𝑛𝑑, 𝑣, ∗⟩ to 𝑝 ′

22: Function 𝑂𝑛𝑇 𝑖𝑚𝑒𝑜𝑢𝑡𝑃𝑟𝑜𝑝𝑜𝑠𝑒 (ℎ𝑒𝑖𝑔ℎ𝑡, 𝑟𝑜𝑢𝑛𝑑 ) : 23: if ℎ𝑒𝑖𝑔ℎ𝑡 = ℎ𝑝 ∧ 𝑟𝑜𝑢𝑛𝑑 = 𝑟𝑜𝑢𝑛𝑑𝑝 ∧ 𝑠𝑡𝑒𝑝 𝑝 = 𝑝𝑟𝑜𝑝𝑜𝑠𝑒 then 24: broadcast ⟨ prevote, ℎ𝑝 , 𝑟𝑜𝑢𝑛𝑑𝑝 , 𝑛𝑖𝑙 ⟩ 25: 𝑠𝑡𝑒𝑝𝑝 ← 𝑝𝑟𝑒𝑣𝑜𝑡𝑒 26: Function 𝑂𝑛𝑇 𝑖𝑚𝑒𝑜𝑢𝑡𝑃𝑟𝑒𝑣𝑜𝑡𝑒 (ℎ𝑒𝑖𝑔ℎ𝑡, 𝑟𝑜𝑢𝑛𝑑 ) : 27: if ℎ𝑒𝑖𝑔ℎ𝑡 = ℎ𝑝 ∧ 𝑟𝑜𝑢𝑛𝑑 = 𝑟𝑜𝑢𝑛𝑑𝑝 ∧ 𝑠𝑡𝑒𝑝 𝑝 = 𝑝𝑟𝑒𝑣𝑜𝑡𝑒 then 28: broadcast ⟨ precommit, ℎ𝑝 , 𝑟𝑜𝑢𝑛𝑑𝑝 , 𝑛𝑖𝑙, −1⟩ 29: 𝑠𝑡𝑒𝑝𝑝 ← 𝑝𝑟𝑒𝑐𝑜𝑚𝑚𝑖𝑡 30: Function 𝑂𝑛𝑇 𝑖𝑚𝑒𝑜𝑢𝑡𝑃𝑟𝑒𝑐𝑜𝑚𝑚𝑖𝑡 (ℎ𝑒𝑖𝑔ℎ𝑡, 𝑟𝑜𝑢𝑛𝑑 ) : 31: if ℎ𝑒𝑖𝑔ℎ𝑡 = ℎ𝑝 ∧ 𝑟𝑜𝑢𝑛𝑑 = 𝑟𝑜𝑢𝑛𝑑𝑝 then 32: 𝑆𝑡𝑎𝑟𝑡𝑅𝑜𝑢𝑛𝑑 (𝑟𝑜𝑢𝑛𝑑𝑝 + 1)

17