Dispel: Byzantine SMR with Distributed Pipelining

The leader-based pattern typically starts with a message exchange phase where a specific node, called the leader, aims at proposing a command to the rest of the nodes. If the leader is faulty, the system may choose another leader. As it is impossible to distinguish a slow network from a mute leader in a partially synchronous environment, such changes affect performance (SRM12, ; MAK13, ; AMQ13, ; GPB16, ). If the leader is correct and the network is timely, then the command is decided by all nodes. But in this case, the leader may have to send its proposal to many, making its NIC the bottleneck (JRS11, ). One may think of batching proposals within the same consensus instance (FH06, ), so that multiple proposals are piggybacked in the same messages and can be decided in a row. This increases the information conveyed to all nodes by the leader, hence adding to the congestion.

To mitigate the leader bottleneck once the proposals are conveyed to all nodes, the nodes typically hash the content of the proposal into some digest (CL02, ; BSA14, ; YMR19, ) and exchange the resulting digests to refer to specific proposals. On the one hand, this reduces considerably the network utilization in the phases following the prepare phase. On the other hand, the subsequent phases convey more frequent but smaller messages than in the first phase whose treatment consumes CPU. The hashing function necessary to encode these messages is also CPU intensive. As the communication is partially synchronous it is likely that the hashing function execution overlaps at many nodes with the reception of these message digests, hence further increasing the CPU usage.

When requests must be cryptographically verified (BSA14, ), as in cryptocurrency applications (Nak08, ; Woo15, ), or when the phases require message authenticators (CL02, ), the system can become CPU bound. To put things in perspective, an AWS EC2 c5.xlarge instance has an upload bandwidth of 600 MiB/s but a CPU of this same instance can only hash 425 MiB/s with SHA256 and verify up to 5 MiB/s for 400 byte transactions with the fastest ECDSA curve provided by OpenSSL as we detail in §6. BFT SMRs typically alternate between the network-intensive phase and these CPU-intensive phases.

To bypass the leader completely, several deterministic leaderless Byzantine consensus were proposed. Lamport suggests a virtual leader election (Lam10, ; Lam11, ) to transform a leader-based Byzantine consensus algorithm into a leaderless one, however, no virtual leader election algorithm is given. Borran and Schiper (BS10, ) proposed a Byzantine leaderless consensus whose communication complexity is exponential.

Recently, Crain et al. (CGLR18, ) proposed a leaderless deterministic Byzantine consensus algorithm. The algorithm called Democratic BFT (DBFT), is depicted in Algorithm 1 and builds upon a reduction of the problem of multivalue consensus to the problem of binary consensus (BKR94, ) and a resilient-optimal and time-optimal deterministic binary consensus algorithm that was formally verified using model checking (TG19, ): Each replica of id $0\leq k<n-1$ reliably broadcasts its input value such that all correct replicas deliver the same value (B87, ) into the $k^{th}$ coordinate of a local array. Later, DBFT spawns $n$ binary instances whose $k^{th}$ takes input value 1 if the $k^{th}$ coordinate of the array was reliably delivered, or 0 if it was not yet delivered. The decisions of the $n$ binary instances form a bitmask that is applied to the array of values to extract the decidable values. DBFT outputs the first of these values to solve the classic Byzantine consensus problem, the Red Belly Blockchain extends DBFT (CNG18, ) to output all these values hence committing more transactions, unfortunately, it runs consensus instances sequentially.

Once the bottleneck effects are mitigated, one can further improve the throughput of SMRs by reducing the latency of one consensus instance or by overlapping different consensus instances. First, a long series of results (FV97, ; KAD07, ; SR08, ; SB12, ; MBS13, ; VCB13, ) reduce the latency of the BFT consensus, sometimes by assuming correct clients (KAD07, ), tolerating less Byzantine nodes (SR08, ) or using a trusted execution environment (VCB13, ; KBC12, ). The effect of reducing latency on increasing the throughput is quite visible (MBS13, ), however, this increase is limited by the sequential execution of these consensus instances.

Second, some form of centralized pipelining was proposed (SS13, ; YMR19, ). This technique inherited from networking (PM95, ), consists of executing some consensus instance before another terminates. This approach is “centralized” because it is leader-based: a leader is needed to spawn a new pipeline epoch. The benefit of centralized pipelining was observed to be limited (SS13, ), again due to the network bottleneck at the leader (cf. §2.1). HotStuff (YMR19, ) is a recent BFT SMR that piggybacks phases of consecutive consensus instances and Facebook is building Libra (BBC19, ) on top of its variant.²²2https://medium.com/ontologynetwork/hotstuff-the-consensus- protocol-behind-facebooks-librabft-a5503680b151. Unfortunately, it again relies on a leader. Dispel is the first distributed pipeline SMR as described below.

Figure 2 shows the architecture and the main steps of one pipeline epoch that runs one consensus instance. This epoch consists of creating a batch of commands, called transactions in the context of blockchains, exchanging batches with other replicas and selecting an ordered subset of the batches created by the replicas. A Dispel replica continuously listens for client transactions and stores them in its transaction pool (step 1). When a replica decides to spawn a new pipeline epoch, it concatenates all the transactions in the pool to create a batch. The replica then broadcasts the batch as the first step of the reliable broadcast of the DBFT consensus protocol (§2.3). In parallel, a dedicated hashing thread computes the sha256 checksum of the batch (step 2A).

All Dispel replicas decide independently to spawn a new pipeline epoch. We describe this process in details in §4.1. As a consequence, a replica receives batches from the other replicas in parallel to steps 1 and 2A (in step 2B). When a hashing thread has computed the hash of a batch, it stores the batch and its associated hash in the manager component (step 3). The hashing thread also transmits the hash to the consensus component. From this point on, the consensus component sent the hash digest instead of the batch itself when communicating with other replicas. The consensus component exchanges hashes to complete the reliable broadcast and executes the subsequent steps of Algorithm 1 (step 2C). When the replicas decide a set of hashes, the consensus component transmit the decision to the manager (step 4). The manager then fetches the batches associated to the decided hashes and gives these decided batches to the pipeline epoch orderer that we describe in §4.5 (step 5).

Unlike traditional SMRs, Dispel leverages bandwidth, CPU and memory resources. Traditional SMRs start a new consensus instance no sooner than when the previous consensus instance decides. Dispel uses a different approach in order to leverage the network bandwidth and the CPU resources. As we described in §3.1, a pipeline epoch first receives transactions from clients to create a batch, then hashes this batch, broadcasts it and finally executes a consensus over small hash values. This results in four distinct phases depicted in Figure 3: a network reception phase (Rx), a CPU intensive hash phase (H), a network transmission phase (Tx) and a wait-mostly consensus phase (C).

The goal of Dispel is to have all these phases executing at the same time from different pipeline epochs, hence leveraging most resources. To this end, a Dispel replica spawns a new pipeline epoch before the previous epoch terminates. Figure 3 illustrates a 4-epoch pipeline where each replica of Dispel starts a new epoch as soon as its resources permit. Each row stands for a pipeline epoch and has four phases, Rx, H, Tx and V. As soon as four epochs run concurrently, the replica can execute all these distinct phases at the same time, one phase per epoch, and leverages most resources. This technique called pipelining is especially effective when most of the transactions are issued by geodistributed clients to their closest replicas and when most concurrent transactions do not conflict because such phases consume different resources. Recall that the fact that concurrent transactions are usually not conflicting was observed before and benefited others (KAD07, ; MAK13, ).

The first phase (Rx) of a pipeline epoch (Fig. 3) consists of receiving transactions from clients in the transaction pool, as we explained in §3.1. As a replica has no control over the number of transactions that the clients send, its only responsibility is to ensure that there is always space in the pool to collect new transactions. If the pool is full, incoming client transactions are discarded and the client must retry later or on another replica. This motivates the first condition to spawn a new pipeline epoch: having a full transaction pool. Spawning a new epoch before the pool is full would result in fewer transactions per batch and thus in a lower throughput. When the clients send transactions slowly, filling a transaction pool takes a long time. To prevent old transactions from hanging in the transaction pool for too long, a replica also spawns a new pipeline epoch after a timeout expires, however, this never happens in our experiments as the demand is high.

The next phase (Tx) consists of broadcasting an epoch batch to the other replicas. A pipeline epoch can only progress to its next phase if the previous epoch has finished the same phase. A second condition for spawning a new epoch is thus to have an idle network, at least for the sending part. To detect when the network is idle, each replica of Dispel continuously monitors its network usage. Every 2 ms, each node measures its sending rate and compares this sending rate after 3 samples (over the resulting 6 ms duration) to the 600 MiB/s physical network capacity (as we measure in §5). If the network usage is lower than 5% of the physical network bandwidth limit, then the network is considered idle.

It is also important for a node to spawn a new pipeline epoch only if it has enough memory available. The risk is, otherwise, for replicas to inflate the latency of a consensus instance by accepting to participate in too many concurrent epochs. To decide the maximum number of epochs, each replica divides, prior to the execution, the amount of available memory (returned by the OS command free) by the batch size. Each replica also keeps a few megabytes to store thread stacks, consensus instance states and other small sized objects. This available memory is observed offline because it is hard to assess the memory available in real-time in Java due to the garbage collector of OpenJDK11 that is unpredictable.

Each pipeline epoch corresponds to a new epoch in which one consensus instance executes. By monitoring its own resource usage, a replica decides when to spawn a new pipeline epoch independently of the other replicas. Each replica tags the pipeline epochs it spawns with an increasing epoch number based on the current index of the pipeline—if two replicas spawn two pipeline epochs with the same number then it means that there are actually the same epoch. Additionally, all the consensus messages associated with an epoch are prefixed by the epoch number of the epoch. A replica considers that the received messages tagged with the same epoch number belong to the same pipeline epoch and thus to the same consensus instance. With this simple method, replicas join an existing pipeline epoch by spawning an epoch locally which happens to have the same epoch number.

A replica participates to remotely spawned epochs depending on its local state and the received messages. When every replica in the system receives an equal number of transactions from the clients, the replicas end up spawning new pipeline epochs at the same rate. In this ideal scenario, all replicas participate to the same pipeline epochs without any additional synchronization. When the clients load is imbalanced among the replicas, some replicas may never decide to spawn a new epoch on their own. However, sufficiently many replicas must participate in a consensus instance for this instance to terminate. For this reason, when a replica receives a message from a pipeline epoch to which it does not participate, if the previous epoch is decided then this replica participates to the epoch. This restriction of having the previous epoch decided prevents a malicious node from making other replicas participate in epochs in a distant future, which could lead to starvation.

Algorithm 2 summarizes with pseudocode how Dispel decides to spawn new epochs. If a replica $p_{i}$ meets the three conditions (a) the transaction pool $\mathord{\it batch}_{i}$ is full, (b) its network is idle and (c) there is enough available memory, then the replica spawns a new pipeline epoch (lines  7–9). The epoch number of this new epoch is the immediately greater integer than the epoch number of the newest pipeline epoch to which the replica $p_{i}$ participated. Additionally, when a replica receives a message from a pipeline epoch to which it does not participate, it waits for the previous epoch to decide and then participates (lines  11,12). If this new epoch is the new epoch the replica $p_{i}$ has spawned on its own, it participates with the content of its transaction pool (lines  13–15). Otherwise, it participates with an empty batch (lines  16). This avoids submitting a batch to a consensus instance that is likely to already have accepted $n-t$ batches from other replicas. In this case, the batch submitted by the replica $p_{i}$ is not part of the decision set. The epoch spawning routine (lines  18–25) starts a new consensus instance (cf. §2.3) tagged by an epoch number and delivers the consensus decisions in the order of the epoch numbers. We detail how a replica orders the decision inside a epoch in §4.4 and across epochs in §4.5.

An interesting side effect of our pipeline is that correct replicas may decide upon the hash of batches before receiving the corresponding batches in full. As we mentioned in §3.1, because replicas decide locally to spawn a new epoch, the transactions reception and the batches exchange happen concurrently. Additionally, as the consensus decides on hashes and not on batches, the consensus decision also happens concurrently with the batch exchange. As a result of this concurrency, a replica sometimes decides on batches it has not yet received. Indeed, as we described in §2.3, the DBFT consensus algorithm starts by a reliable broadcast and then executes a binary consensus on every reliably delivered value. During the first step of a reliable broadcast, a Dispel correct replica sends the batch to all the replicas.

The two following steps of a reliable broadcast are all-to-all broadcasts used to prevent correct replicas from delivering values broadcast by Byzantine to only a subset of the replicas or from delivering different values. Dispel correct replicas only send hashes during these to all-to-all broadcasts in order to save bandwidth. A reliable broadcast delivers its value when the replica delivers enough messages from the two all-to-all reliable broadcast. As a result, a Dispel correct replica sometimes has the hash of a batch reliably delivered without knowing the corresponding batch. This is not an issue since this is only possible if at least one correct replica knows the batch. A replica handles this corner case by broadcasting a batch request for the decided hashes with an unknown batch at the end of each pipeline epoch. When a replica knows all the decided batches, it sorts them with their hash as a sorting key.

Having each pipeline epoch deciding an ordered set of batches is not sufficient. Because of the concurrency between pipeline epochs, the order in which epochs are decided is not always the order in which they are spawned. Replicas solve this issue by transmitting the pipeline epochs decisions sorted by the epoch number of these epochs. More formally, a replica transmits the decision of a pipeline epoch with the epoch number $k$ to the application only after transmitting the decisions of the previous pipeline epochs for all $j<k$ to the application. This corresponds to the lines  22–24 in Algorithm 2.

Figure 4 illustrates how both intra and inter-epoch orderings take place. It shows the evolution of three pipeline epochs on a replica when this replica receives messages. Initially ($T_{0}$), only two epochs $C^{0}$ and $C^{1}$ are running. The replica has received the batch A for $C^{0}$ and the batches A, B and C for $C^{1}$. Upon reception of the batch B for $C^{2}$ from another replica ($T_{1}$), the receiving replica spawns locally the new pipeline epoch $C^{2}$ as described in lines  11–15 of Algorithm 2. Upon reception of the consensus messages for $C^{0}$ ($T_{2}$), the replica reaches consensus and decides on the batches A and B. However, as we explain in §4.4, the replica has not received the decided batch B. Upon reception of this batch, the epoch $C^{0}$ is marked as decided but not yet ready to commit (i.e., to transmit the decision to the application). The replica then receives consensus messages for $C^{1}$ ($T_{3}$) and decides on the batches A, B and C. Since the replica knows the decided hashes, it is ready to commit $C^{1}$ but waits for the previous epoch $C^{0}$ before transmitting to the application. Finally, the replica receives the batch B for $C^{0}$ ($T_{4}$). The replica then commits both epochs $C^{0}$ and $C^{1}$ and mark them as terminated.

To conclude, we summarize three properties for the distributed pipelining that allows to proceed efficiently:

1. (1)

   Early epoch: this requires launching a epoch $k+1$ early, typically epoch $k+1$ should start before the epoch $k$ completed in order to guarantee that the pipeline translates into higher throughput.

2. (2)

   Oldest epoch priority: epoch $k$ always has priority over epoch $k+1$ to ensure that the number of concurrently active epochs eventually decreases, preventing undesirable situations like starvation.

3. (3)

   Pipeline feeding: the SMR must guarantee that commands are enqueued into the upcoming epochs to guarantee progress, despite the workload induced by the inter replicas communications.

Guaranteeing these three properties help ensure the good performance of the distributed pipelining.

For this evaluation, we implement Dispel, a leaderless SMR using the DBFT consensus described in §2 and the pipelined architecture described in §3 and §4. Dispel is written in Java using only the standard Java libraries. We compare Dispel against four SMRs:

• •

  BFT-SMaRt: is a leader-based BFT SMR similar to PBFT with further optimizations that has been maintained in Java for more than a decade (BSA14, ). It was used for the ordering service of Hyperledger Fabric (ABB18, ) to tolerate Byzantine failures (SBV18, ). We used the branch weat2 of the official BFT-SMaRt git repo https://github.com/bft-smart/library that outperforms the master branch when geo-distributed (SB15, ; BRS19, ).

• •

  EPaxos: is a leaderless crash fault tolerant (CFT) SMR (MAK13, ) that does not provide the guarantees of a BFT SMR but that serves as a fast baseline. It is an improved version of Paxos with no leader and a fast path for non conflicting commands. We use the Go author’s library from https://github.com/efficient/epaxos.git.

• •

  HotStuff: is a recent leader-based BFT SMR. It outperforms BFT-SMaRt by having the leader piggybacking phases of distinct consensus instances into the same messages (YMR19, ). Facebook is currently developing in Rust the Libra state machine (BBC19, ) on a variant of HotStuff (Fac19, ). We use the C++ authors’ library from https://github.com/hot-stuff/libhotstuff.

• •

  Zyzzyva: is a leader-based BFT SMR designed to reduce decisions latency (KAD07, ). To this end, Zyzzyva replicas reply optimistically to the client before reaching consensus and let the client solve disagreements. We use the Zlight C++ implementation (AGK14, ) that we patched to make it run on a geo-distributed setup. More precisely, the original implementation uses IP multicast and UDP communication without any mechanism to handle packet loss. We replace the UDP implementation by a standard event-driven loop TCP implementation.

Other SMRs: there is a long body of BFT SMRs papers, however, not all implementations are available: we contacted the authors of BFT-Mencius (MBS13, ) and ezBFT (APR19, ), two leaderless BFT protocols, but there were no readily available implementation.

This evaluation takes place on AWS EC2 instances. We use c5.xlarge instances for running replica and client processes. Each instance is a KVM virtual machine with four hardware threads implemented by two hyperthreaded Intel Xeon core running at 3 GHz, with 8 GiB of memory and a network interface of 600 MiB/s upload and download speed. Each virtual machine is running a Ubuntu 18.04 distribution with an AWS modified Linux kernel 4.15, OpenJRE 11 and the glibc 2.27. The SMRs are compiled using OpenJDK 11, gcc 7.5 and go 1.10.4.

We ran BFT-SMaRt, Zyzzyva, HotStuff and EPaxos in their default configurations indicated in their original papers or reports (BSA14, ; AGK14, ; YMR19, ; MAK13, ). Each Dispel replica uses a batch size of $25/n$ MB where $n$ is the number of replica. We configure Dispel replicas to use up to 12 pipeline epochs. In every experiment, we execute one replica process per VM. In addition, we dedicate two VMs per region to execute the client processes. For EPaxos, BFT-SMaRt, HotStuff and Dispel, each client VM executes a single client process which sends many parallel transactions to the replicas. Zyzzyva clients only implement blocking requests. For Zyzzyva, we execute 100 client processes per client VM. We found that this number of client process is sufficient to saturate Zyzzyva replicas.

The goal of the following experiments is to compare the throughput that each SMR delivers. This throughput increases with the client load. As a tradeoff, increasing the client load generally results in a higher latency. To provide a fair comparison, we choose to explore different client loads for every data points we plot. We then select the client loads resulting in a throughput of at least 90% of the best observed throughput. Among these selected loads, we pick the one resulting in the best latency. The intuition behind this methodology is that when the client load increases, the latency remains stable until an inflection point and then skyrockets. The throughput increases until this inflection point and then remains stable. Our methodogy identifies the inflection point by selecting the set of client loads with the best throughputs and then pick the latency obtained in this set right before the inflection point. All the data points are the average over at least 5 runs.

As we expect the pipeline to increase throughput despite high latency, we start by comparing the throughput and latency of Dispel to EPaxos, HotStuff, BFT-SMaRt and Zyzzyva within a single continent. More precisely, we measured the throughput and latency on up to 256 VMs located in Europe (Ireland, London, Paris and Frankfurt). Table 1 summarizes the latencies and bandwidth between the four datacenters, mesured with nuTCP.

Figure 5(a) depicts the throughput of Dispel, EPaxos, HotStuff and Zyzzyva. We found that BFT-SMaRt and HotStuff exhibit the same behavior although BFT-SMaRt throughput is consistently at least $2\times$ lower than HotStuff throughput. We choose to not plot BFT-SMaRt for sake of clarity. First, we observe that Zyzzyva does not perform as well as the others with a throughput of 25 Kops/s at 4 nodes and of 2 Kops/s or below with 64 nodes or more. This is because Zyzzyva is optimized to perform in a local area network (LAN): it does not batch requests and executes sequentiallySecond, as expected, EPaxos outperforms HotStuff by delivering a throughput up to $7\times$ larger at 32 nodes and still $3\times$ larger at 256 nodes. EPaxos does not offer the same level of fault tolerance than HotStuff: it does not tolerate Byzantine failures while HotStuff does. Third, all solutions perform significantly slower than Dispel due to their lack of pipeline. Dispel exhibits the best performance at 4 nodes with a throughput of 462 Kops/s (more than $2\times$ larger than EPaxos and $13\times$ larger than HotStuff). At worst, with 256 nodes, Dispel has a throughput of 73 Kops/s (still $2\times$ larger than EPaxos and $6\times$ larger than HotStuff).

Pipelining typically hides the increase in latency through parallelization, executing multiple consensus instances at a time. Although HotStuff pipelines to some extent, its pipeline only piggybacks phases of consecutive consensus instances into the same messages and does not leverage resources from any replicas like Dispel’s pipeline does. Interestingly, Dispel also doubles the performance of EPaxos at 4, 128 and 256 nodes even though EPaxos does not tolerate Byzantine failures. As we consider only non-conflicting requests here, all command leaders of EPaxos should commit their command in parallel—similarly to a pipeline. The difference is that EPaxos does not spawn new leader proposal based on resources as Dispel does, hence unable to detect resource contention.

A surprising phenomenon is the unexpected high throughput of Dispel with 4 replicas and the througput drop between 4 and 16 replicas. As we describe later in §5.5, we expect the throughput of Dispel to increase with the number of replicas while the number of replica is small, then to decrease. This is what we observe from 16 replicas, however the throughput of Dispel at 4 replicas is $1.68\times$ larger than at 16 nodes. Although we do not have a definitive explanation for this throughput, we are confident that it does not come from either our measurement nor the methodology we use. Indeed, over the 5 runs we use to compute the average throughput of this point, the individual throughputs are all between 449 Kops/s and 499 Kops/s. The client load we use is the one that results in the best throughput over the explored values. Our main hypothesis is that for this small number of replica, all the replicas progress at the same rate in the pipeline, which is the ideal scenario that we describe in §4.2 where all replicas always participate with full batches.

Figure 5(b) depicts the latencies obtained for the four SMRs, Dispel, EPaxos, HotStuff and Zyzzyva, in the same settings as above (§5.3). This shows that Dispel does not offer the best latency. This is because the pipeline does not need to reduce the latency to increase throughput. Zyzzyva, designed for LANs, offers consistently the lowest latency by staying below 300 ms until 64 nodes and always below 1700 ms. In contrast with other solutions, the latency of HotStuff improves with the system size at small scale, which is likely due to our measurements that extract the best throughput runs of all runs before selecting the best latency run within these values (§5.2). Due to HotStuff lower communication complexity, HotStuff latency increases slower than other SMRs. As a result, the best throughput values are observed in conditions where all latencies are relatively similar. Given that Facebook aims at deploying a variant of HotStuff on 100 nodes and more as part of their Libra blockchain (Fac19, , §5), it is particularly interesting to compare performance at 128 nodes: the latencies of HotStuff and Dispel are in the same order of magnitude, respectively 1300 ms and 2100 ms, whereas the throughput of Dispel (Fig. 5(a)) is more than $12\times$ higher than HotStuff. We realized that the default HotStuff is limited so in §6 we tune HotStuff to obtained better performance on geodistributed experiments, however, as we will see, it remains significantly slower than Dispel.

Because TCP preserves ordering, using one connection to transmit independent data often leads to the head-of-line (HOL) blocking suboptimal phenomenon (SK06, ) where the loss of one packet actually delays the reception of potentially numerous subsequent packets until after the packet is retransmitted and successfully delivered. As simple way to circumvent this phenomenon is to use several TCP connections in parallel. Table 2 illustrates the difference between the NIC physical limit and the bandwidth limit of a single TCP connection. As one can see, the network usage increases linearly with the number of parallel connections until the limit of the network interface is met at around 533 MB/s, after which the bandwidth per stream decreases due to this physical limit.

Despite having several open TCP connections, one per peer, sequential SMRs replicas are unable to benefit from this parallelism. Indeed, when such sequential replicas broadcast a message, they must wait the transmission of this message completes on all the TCP connections before to progress. On the contrary, Dispel replicas do not wait the transmission completion of every TCP connection thanks to their pipeline structure.

To illustrate how Dispel cirumvents the HOL blocking phenomenon, we measure the throughput of EPaxos, HotStuff, Zyzzyva and Dispel when the number of replica varies on two setups. The first setup evenly spreads the replicas across two regions, North Virginia and North California. The bandwidth of one TCP connection between these two regions if 23 MiB/s. The second setup evenly spreads the replicas across North Virginia and Tokyo. The TCP bandwidth between these two regions 11 MiB/s. On these two setups where the TCP bandwidth is low, Dispel benefits from an increasing number of replicas. However, when the number of replicas becomes too large, the probability of having a packet loss on a majority of TCP connections becomes significant and Dispel does not benefit from additional replicas.

We report on Figure 6 the throughput for Dispel and EPaxos on the two setups, 11 MiB/s and 23 MiB/s of TCP bandwidth, when the number of replica increases with transactions of 128 bytes. We do not report the throughput for HotStuff, BFT-SMaRt and Zyzzyva as their throughput is systematically below respectively 20 Kops/s, 14 Kops/s and 6 Kops/s. We observe that for each setup and every number of replica, the throughput of Dispel is larger than for the other SMRs. Moreover, the throughput of Dispel first increases up to 108 MiB/s at 6 replicas in the 23 MiB/s bandwidth setup and up to 85 MiB/s at 10 replicas in the 11 MiB/s bandwidth setup. This increase is caused by Dispel replicas using more TCP connections in parallel when the number of replicas increases. We observe a similar yet less pronounced evolution for EPaxos. Indeed, EPaxos replicas decide transactions in parallel as long as they are non conflicting. This parallelism makes EPaxos also using TCP connections in parallel although to a lesser extent. While we do not observe this phenomenon on HotStuff, BFT-SMaRt and Zyzzyva, their throughput is too small to conclude.

In order to assess the performance of Dispel and HotStuff under failures, we ran an experiment for 122 seconds on $n=32$ nodes spread evenly in Ireland, London, Paris and Frankfurt during which we manually injected crash failures. In this experiment, each transaction is of size 400 bytes, similar to the size of simple Bitcoin transactions.