spacing=nonfrench countblanklinestrue[t]#1

# uBFT: Microsecond-Scale BFT using Disaggregated Memory [Extended Version]

Marcos K. Aguilera<EMAIL_ADDRESS>VMware ResearchUnited States ,  Naama
Ben-David<EMAIL_ADDRESS>VMware ResearchUnited States ,  Rachid
Guerraoui<EMAIL_ADDRESS>École Polytechnique Fédérale de Lausanne
(EPFL)Switzerland ,  Antoine Murat<EMAIL_ADDRESS>École Polytechnique
Fédérale de Lausanne (EPFL)Switzerland ,  Athanasios Xygkis
<EMAIL_ADDRESS>École Polytechnique Fédérale de Lausanne
(EPFL)Switzerland and  Igor Zablotchi<EMAIL_ADDRESS>MITUnited States

###### Abstract.

We propose uBFT, the first State Machine Replication (SMR) system to achieve
microsecond-scale latency in data centers, while using only $2f{+}1$ replicas
to tolerate $f$ Byzantine failures. The Byzantine Fault Tolerance (BFT)
provided by uBFT is essential as pure crashes appear to be a mere illusion
with real-life systems reportedly failing in many unexpected ways. uBFT relies
on a small non-tailored trusted computing base—disaggregated memory—and
consumes a practically bounded amount of memory. uBFT is based on a novel
abstraction called Consistent Tail Broadcast, which we use to prevent
equivocation while bounding memory. We implement uBFT using RDMA-based
disaggregated memory and obtain an end-to-end latency of as little as 10 µs.
This is at least 50$\times$ faster than MinBFT, a state-of-the-art $2f{+}1$
BFT SMR based on Intel’s SGX. We use uBFT to replicate two KV-stores
(Memcached and Redis), as well as a financial order matching engine
(Liquibook). These applications have low latency (up to 20 µs) and become
Byzantine tolerant with as little as 10 µs more. The price for uBFT is a small
amount of reliable disaggregated memory (less than 1 MiB), which in our
prototype consists of a small number of memory servers connected through RDMA
and replicated for fault tolerance.

Byzantine fault tolerance, microsecond scale, replication, disaggregated
memory, fast path, finite memory, RDMA

††conference: the 28th ACM International Conference on Architectural Support
for Programming Languages and Operating System; March 25–29, 2023; Vancouver,
Canada [Preprint]††ccs: Computer systems organization Reliability††ccs:
Computer systems organization Availability

##  1\. Introduction

Data center applications such as social networks, web search, e-commerce, and
banking increasingly need both microsecond-scale performance (Barroso et al.,
2017; Schneider, 2012; Ibanez et al., 2021; Boucher et al., 2018) and strong
fault tolerance, in order to deliver on their promise of being the backbone of
today’s online services. Indeed, strong fault tolerance is required by real-
life systems which reportedly fail in many unexpected ways. Apart from simple
crashes, failures in distributed systems range from software/configuration
bugs (Leesatapornwongsa et al., 2016; Oppenheimer et al., 2003), to hardware
failures (Meza et al., 2015; Narayanan et al., 2016; Meza et al., 2018), to
hardly detectable hardware bugs (Hochschild et al., 2021; Dixit et al., 2022;
Gunawi et al., 2018; Huang et al., 2017) and up to malicious activity (Shieh
et al., 2011; Arzani et al., 2020). Traditionally, protecting against the
plethora of different failures required slow and expensive Byzantine Fault
Tolerant (BFT) protocols.

The standard way to achieve fault tolerance is state machine replication
(SMR).  A BFT protocol implementing SMR incurs milliseconds of latency
(Bessani et al., 2014; Androulaki et al., 2018), requires a large number of
replicas ($3f{+}1$ to tolerate $f$ failures) (Castro and Liskov, 1999; Yin et
al., 2019; Miller et al., 2016), consumes unbounded memory (Veronese et al.,
2013), and/or relies on a large trusted computing base (Behl et al., 2017;
Kapitza et al., 2012; Veronese et al., 2013). These reasons might explain why
BFT has had no adoption in data centers.

In this paper, we propose uBFT, the first BFT SMR system that simultaneously
offers four key features: (1) microsecond-scale latency, (2) few replicas
($2f{+}1$), (3) practically bounded memory, and (4) a small non-tailored
trusted computing base. In the common case, uBFT leverages unanimity to
replicate requests in as little as 10 µs end-to-end without invoking the
trusted computing base or expensive cryptographic primitives. In the slow
path—when there are failures or slowness in the network—uBFT uses a novel
protocol that combines digital signatures with judicious use of a trusted
computing base. The trusted computing base in uBFT is non-tailored and small:
rather than trusted enclaves with arbitrary logic such as Intel’s SGX (Costan
and Devadas, 2016) or trusted hypervisors (Zhuo et al., 2014)—which have large
attack surfaces due to their complexity (Fei et al., 2021; Cui et al.,
2021)—uBFT relies solely on disaggregated memory, a technology increasingly
present in data centers due to the availability of RDMA (Technologies, 2015)
today and CXL (Cutress, 2019) in a few years. The key mechanism from
disaggregated memory we leverage in uBFT are single-writer regions (regions of
memory that can be written by one designated host and can be read by others),
implemented in hardware through access permissions.

Providing the above four features is challenging for BFT protocols. To get
microsecond-scale latency, BFT protocols need to avoid expensive public-key
cryptography and reduce communication rounds in the common path—and doing so
has typically required increasing rather than decreasing the number of
replicas (Kotla et al., 2010; Abd-El-Malek et al., 2005; Martin and Alvisi,
2006). Meanwhile, decreasing the number of replicas has usually required
unbounded memory, sophisticated, or tailored trusted computing bases such as
append-only-memory (Chun et al., 2007), SGX (Behl et al., 2017), TrInc (Levin
et al., 2009), or reliable hypervisors (Zhuo et al., 2014). Limiting the
amount of memory is a significant challenge in the design of uBFT, as the
standard technique to handle Byzantine behavior in systems with $2f{+}1$
replicas requires storing all messages received, leading to long message
histories (Aguilera et al., 2021; Veronese et al., 2013), which consume
unbounded memory. Finally, not tailoring the trusted computing base to our
needs requires designing around existing technologies—in our case
disaggregated memory—rather than custom hardware.

To respond to these challenges, uBFT introduces a new abstraction called
Consistent Tail Broadcast (CTBcast) that we use to prevent equivocation
(Madsen and Debois, 2020), while requiring a practically bounded amount of
memory.111 The required memory is logarithmic in the number of operations.
Everywhere we use a bounded number of bits except for sequence numbers.
Equivocation—a major source of problems in a system with Byzantine failures
(Chun et al., 2007)—occurs when a faulty process incorrectly sends different
information to different processes, which may cause the state of replicas to
diverge. CTBcast prevents equivocation for all messages, but only ensures the
delivery of the last $t$ broadcast messages, where $t$ is a parameter that
trades memory for latency (we explain how to set it in Section 7).

The price for uBFT is a small amount (less than 1 MiB) of reliable
disaggregated memory. uBFT is designed modularly to work with a generic such
component; our current prototype implements this component using RDMA and a
set of memory nodes that themselves are replicated for fault tolerance. These
nodes add to the total number of replicas, but these replicas are tiny and
simple: they do not store the state of the application, just a few in-flight
coordination messages. Moreover, their functionality is application
independent, so they can be shared among many applications, amortizing their
cost. The memory nodes that provide the disaggregated memory constitute the
trusted computing base in our prototype and are assumed to fail only by
crashing.  This shrinks the vulnerability of the system compared to currently
deployed crash-tolerant SMR systems, in which _all_ components can fail only
by crashing, effectively making the trusted computing base be the entire data
center.

We evaluate uBFT against two state-of-the-art systems. First, we compare it
against Mu, the fastest SMR system to our knowledge, but that tolerates only
crash failures. Compared to Mu, uBFT increases the end-to-end latency by only
$2\times$, while tolerating Byzantine failures. Second, we compare uBFT
against MinBFT, a state-of-the-art $2f{+}1$ BFT SMR system, and showcase that
our system has more than $50\times$ and $2\times$ better latency when
operating in its fast and slow path, respectively. We also use uBFT to
replicate two low-latency KV-stores (Memcached (Interactive, 2022) and Redis
(Sanfilippo, 2022)), and a financial order matching engine (Liquibook
(Newhuis, 2022)). All these applications have request latencies of less than
20 µs when unreplicated and become Byzantine-resilient with as little as 10 µs
more.

In summary, our main contributions are the following:

  * •

The design of uBFT, a BFT system for state machine replication with
microsecond-scale latency in the common case, using only $2f{+}1$ replicas,
practically bounded memory, and a small trusted computing base (disaggregated
memory).

  * •

A new abstraction against equivocation, Consistent Tail Broadcast (CTBcast),
and a protocol for CTBcast that uses a small amount of disaggregated memory
and has a signature-less fast path.

  * •

An open-source implementation of uBFT, CTBcast, and reliable shared
disaggregated memory using RDMA, available at https://github.com/LPD-
EPFL/ubft.

  * •

A thorough evaluation of the performance of uBFT and its applications.

##  2\. Background

###  2.1. State Machine Replication

State Machine Replication (SMR) is an approach to replicate a service (e.g., a
key-value store) across the memory of multiple machines called _replicas_ to
tolerate failures. With SMR, replicas receive requests in the same order, and
thus remain in sync. If durability of SMR is desired, we rely on persistent
rather than volatile memory.

The heart of an SMR system is consensus (Cachin et al., 2011), which ensures
total order in the sense that replicas agree on the same sequence of client
requests. Consensus protocols are often leader-based (Castro and Liskov, 1999;
Aublin et al., 2013; Hunt et al., 2010; Mao et al., 2008; Moraru et al., 2013;
Gupta et al., 2016): a replica designated as the _leader_ orders the client
requests, and forwards them to the other _follower_ replicas to ensure
agreement. Every replica feeds the client requests to its local copy of the
service, and forwards the service’s output to the clients.

Consensus and SMR differ in their memory consumption. Consensus must  ensure
agreement among participants indefinitely, so decided requests must be
retained forever if a participant is unresponsive, thereby requiring unbounded
memory.  In contrast, SMR need not store all requests, as it cares only about
replicating the application state, which can be finite even if there are
infinitely many requests. Thus SMR systems need to adapt consensus to use
finite memory (Shahmirzadi et al., 2009).

###  2.2. Non-Equivocation

Byzantine processes can equivocate, i.e., they can maliciously say different
things to different processes. In SMR, specifically, a Byzantine leader may
propose different values to try to cause replicas to diverge, justifying why
SMR protocols must ensure non-equivocation.

Under the Byzantine asynchronous model, $3f{+}1$ replicas are needed to
prevent equivocation (Lamport et al., 1982). However, if equivocation is
prevented and transferable authentication is available, Byzantine SMR requires
only $2f{+}1$ replicas (Correia et al., 2004), the same number as in the
crash-stop case.  With transferable authentication, a process that verifies a
proof about the origin of a message can transfer the proof to other processes
and be assured they can also verify it. For example, digital signatures
provide transferable authentication, while arrays of Message Authentication
Codes (MACs) do not (Aiyer et al., 2008).

Preventing equivocation using up to $2f{+}1$ replicas requires a compromise
(Correia et al., 2004), i.e., a hybrid model where part of the system—called
the _trusted computing base_ —fails only by crashing. Ideally, this base is as
small as possible, since a small and simple base is less likely to be
susceptible to failures (e.g., vulnerabilities, bugs).

###  2.3. Disaggregated Memory

Disaggregated memory is an emerging data center technology that separates
compute from memory, by providing a shared memory pool that compute nodes
access over a network. The memory pool has limited compute capabilities, which
it uses for management tasks such as connection handling. Disaggregated memory
improves memory utilization, separates the scaling of compute and memory, and
achieves better availability due to the separation of fault domains (Wang et
al., 2022).

Disaggregated memory can be provided by different technologies. The emerging
CXL standard will support disaggregated memory in the future (Gouk et al.,
2022), while today disaggregated memory is available via Remote Direct Memory
Access (RDMA) (Technologies, 2015) on InfiniBand (Jin et al., 2002) or RoCE
(Beck and Kagan, 2011). RDMA is a networking technology that allows a process
to read or write the memory of another machine without involving the CPU of
the latter. Combined with kernel-bypass, RDMA enables sub-microsecond
communication and stringent tail latency. Access rights to RDMA-exposed memory
can be set individually for each accessor.

Figure 1. Overview of uBFT’s architecture.

###  2.4. Model

We consider a system with $2f{+}1$ compute nodes and single-writer multiple-
reader disaggregated memory. Up to $f$ compute nodes are Byzantine and may
thus fail arbitrarily.  We assume network connections are authenticated and
tamper-proof (processes know who they get messages from and messages cannot be
altered) and eventually available (network partitions are intermittent). We
also assume that the disaggregated memory is trusted: it may fail only by
crashing.  The disaggregated memory is divided into chunks, where each chunk
is readable by all compute nodes and writable by a designated compute node. We
assume the existence of public-key cryptography: processes can sign messages
using their private key and verify unforgeable signatures using the pre-
published public keys of all processes. We further assume eventual synchrony:
network and processing delays are unbounded until an unknown _Global
Stabilization Time_ (GST) after which delays are bounded by a known $\delta$.
Lastly, our system assumes bounded clock drift for safety, i.e., the clocks of
correct processes drift from each other with a bounded rate. These assumptions
are common for distributed systems in data centers (Castro and Liskov, 1999;
Aguilera and Walfish, 2009; Leners et al., 2011; Yang et al., 2019; Dragojević
et al., 2015; Guerraoui et al., 2022).

In our prototype, we do _not_ assume that we are given a reliable
disaggregated memory (Zhou et al., 2022; Lee et al., 2019), but rather show
how to implement a reliable disaggregated memory using RDMA.222 uBFT’s clean
encapsulation of disaggregated memory allows future replacement of its RDMA
implementation with CXL-powered memory.  To do so, we assume $2f_{m}{+}1$
memory nodes out of which $f_{m}$ can fail. Memory nodes are part of the
trusted computing base: they are not Byzantine and may fail by crashing only.
Memory nodes are simple: they just provide read and write functionality with
access control. Their size and functionality do not depend on the application
being replicated, and they can be shared among many applications.

##  3\. Design

###  3.1. Overview

uBFT follows the design of PBFT (Castro and Liskov, 1999), a seminal paper
that describes how to build practical BFT SMR systems. Figure 1 depicts the
architecture of uBFT. On the left, a client sends requests to replicas on the
right and waits for responses from a majority of them. The replicas go through
two stages. First, they totally order client requests using a leader-based BFT
consensus protocol. Second, they execute the ordered requests on their local
instance of the replicated application before forwarding the outcome of the
execution to the client. To achieve microsecond-scale latency, the consensus
engine uses a fast/slow path approach. As long as the system is synchronous
and all replicas collaborate, the fast path orders requests without
signatures. If the fast path does not make progress, uBFT’s consensus switches
to the slow path, which makes progress with a mere majority of processes using
signatures and disaggregated memory.

uBFT significantly differs from PBFT in the way it prevents equivocation.
PBFT, being a $3f{+}1$ fault tolerant protocol, relies on intersecting quorums
to ensure that malicious replicas do not make the state of honest replicas
diverge. By contrast, uBFT operates with $2f{+}1$ replicas, and therefore
cannot rely on the same mechanism as PBFT; instead, it relies on trusted
disaggregated memory, which is encapsulated within a new primitive called
_Consistent Tail Broadcast_ (CTBcast).

CTBcast is a variant of Consistent Broadcast (Aguilera et al., 2021).
Consistent Broadcast prevents equivocation by ordering all messages broadcast
by a given process. With it, a Byzantine leader is constrained from sending
different request orderings to different followers. Our _tail_ variant is a
relaxation that requires correct processes to deliver  only the last $t$
messages sent by a correct broadcaster, while preserving non-equivocation for
all messages. This relaxation is essential to practically bound the memory
use. Importantly, the implementation of CTBcast has a signatureless fast-path
to achieve the latency requirements of uBFT.

Figure 2. Overview of uBFT’s consensus engine.

Figure 2 depicts uBFT’s consensus component with its fast/slow path design.
After receiving a request from RPC, the leader proposes its ordering via a
round of CTBcast. The rest of consensus tries to turn this ordering into a
globally accepted one (i.e., stable across leaders). Depending on the
synchrony of the system and the number of faulty replicas, this round of
CTBcast might execute the fast or slow path. In the former case, consensus
continues with its fast path and executes two rounds of Tail Broadcast
(TBcast), a form of best-effort broadcast designed for finite memory (§4.1).
Importantly, none of these three broadcasts involve signatures nor
disaggregated memory. If liveness is lost during the fast path of consensus,
uBFT activates the slow path, shown by the dashed arrows, which executes a
certification round and another round of CTBcast. The slow path is also
executed if the fast path of the initial CTBcast fails. Differently from the
three rounds of the fast path, the three rounds of the slow path all require
signatures, and CTBcast invocations additionally require disaggregated memory.

###  3.2. Challenges

uBFT addresses the following challenges:

#### 2f+1 Replicas and Finite Memory.

Previous theoretical work (Aguilera et al., 2019) proposed to prevent
equivocation with fewer than $3f{+}1$ replicas by building Consistent
Broadcast on top of shared registers. However, this abstraction requires
replicas to use infinite memory in order to store and deliver _all_ broadcast
messages, which is not implementable in practice. We work around this memory
issue by designing CTBcast, a weaker form of Consistent Broadcast where
replicas are allowed to skip the delivery of old messages in order to favor
the delivery of newer ones (§4).

#### SMR with CTBcast.

The reliance of uBFT on CTBcast brings additional complexity to its consensus
algorithm, notably on preventing equivocation _across_ messages. Typically,
protocols rely on the entire history of messages to prevent equivocation. Yet,
CTBcast only guarantees the delivery of the tail, which may lead correct
replicas to have gaps in their delivery history. uBFT works around this
limitation via _CTBcast summaries_ , which allow a replica to make progress in
spite of gaps (§5).

#### Microsecond-Scale Operation.

Systems that operate at the microsecond scale should avoid signatures on their
critical path. Yet, Aguilera et al. (Aguilera et al., 2021) show that
Consistent Broadcast cannot completely remove signatures. Moreover, recycling
memory requires the generation of proofs which also involve signatures. uBFT
addresses this challenge by avoiding expensive cryptography in the fast path
of CTBcast and relegating the few bookkeeping signatures to a background task
(§5.4).

#### Resilient Disaggregated Memory.

uBFT relies on RDMA to implement disaggregated memory. However, raw memory
exposed over RDMA is not enough to implement our SMR protocol. Indeed, RDMA-
exposed memory does not tolerate failures, and data accesses can be
inconsistent, since RDMA provides only 8-byte atomicity. uBFT addresses these
limitations of RDMA using efficient, yet Byzantine fault tolerant, algorithms
(§6).

##  4\. Consistent Tail Broadcast

_Consistent Tail Broadcast_ (CTBcast) is a novel variant of Consistent
Broadcast (CBcast) that uBFT uses to prevent equivocation. Briefly, CTBcast
resembles CBcast, except that it allows processes not to deliver outdated
messages. In this way, CTBcast avoids maintaining the full history of
messages, to bound memory use.

###  4.1. Definition

CTBcast is defined in terms of two primitives, broadcast(k,m) and
deliver(k,m,p),  where $k$ is a numeric identifier, $m$ is a message, and $p$
is a process.  When $p$ invokes broadcast(k,m), we say that $p$ broadcasts
$(k,m)$, i.e., it broadcasts message $m$ with identifier $k$. A correct
broadcaster increments $k$ sequentially at every broadcast, starting with
$k=1$. Similarly, when a process $q$ invokes deliver(k,m,p), we say that $q$
delivers $(k,m)$ from $p$.

In simple terms, CTBcast is a multi-shot abstraction that prevents correct
processes from delivering different messages from a given broadcaster $p$ for
the same identifier $k$. CTBcast is parameterized by a tail $t$, which
specifies which messages are guaranteed to be delivered. Informally, in
CTBcast, a correct process $q$ is only required to deliver the last $t$
messages broadcast by a correct process $p$, while the delivery of previous
messages is best-effort.

CTBcast has the following properties:

Tail-validity:

If a correct process $p$ broadcasts $(k,m)$ and never broadcasts a message
$(k^{\prime},m^{\prime})$ with $k^{\prime}\geq k+t$, then all correct
processes eventually deliver $(k,m)$.

Agreement:

If $p$ and $q$ are correct processes, $p$ delivers $(k,m)$ from $r$, and $q$
delivers $(k,m^{\prime})$ from $r$, then $m=m^{\prime}$.

Integrity:

If a correct process delivers $(k,m)$ from $p$ and $p$ is correct, $p$ must
have broadcast $(k,m)$.

No duplication:

No correct process delivers $(k,*)$ from $p$ twice.

The difference between CTBcast and CBcast lies in their validity property.
Tail-validity implies that a correct process is only obliged to deliver a
message $m$ from $p$ if $m$ is among the last $t$ messages broadcast by $p$.
When $t{=}\infty$, tail-validity reduces to CBcast’s validity.

The infinite tail of CBcast is what prevents it from recycling memory. Indeed,
given that the broadcaster cannot distinguish between network asynchrony and
receiver failures (Delporte-Gallet et al., 2004), it is required to keep re-
transmitting all messages until they are explicitly acknowledged. Thus, in
CBcast, the broadcaster can garbage collect messages only after they have been
acknowledged by all receivers. As a result, once a single process fails,
memory cannot be recycled and any correct implementation of CBcast must block
after running out of memory. By not enforcing the delivery of _old_ messages,
CTBcast’s tail-validity lets processes recycle the memory dedicated to these
messages. This is why CTBcast requires only finite memory while CBcast does
not. In Section 5, we show that despite its weaker semantics, CTBcast is
sufficient for solving consensus.

###  4.2. Algorithm

Algorithm 1 implements CTBcast using finite memory with a fast/slow path
approach that avoids signatures and disaggregated memory in the common case.
For pedagogical reasons, we assume that a designated process is the
broadcaster while the others are receivers. Each receiver owns an array of $t$
Single-Writer Multiple-Reader (SWMR) regular registers. Each register is only
writable by its owner, but is readable by all processes. The regularity of the
registers forces READs that execute concurrently to a WRITE to return either
the value being written or the previous one. Moreover, each process uses a
Tail Broadcast (TBcast) primitive which ensures the delivery by correct
processes of the last $2t$ messages broadcast through it, but does not prevent
equivocation. Formally, TBcast has all properties of CTBcast except agreement.

Implementing TBcast using finite memory is simple. The broadcaster buffers its
last $2t$ messages and retransmits them until it receives acknowledgements
from all receivers. To broadcast a new message when the buffer is full, the
broadcaster makes room for it by evicting the oldest buffered message.

Algorithm 1: Consistent Tail Broadcast

⬇

1# at the broadcaster

2def broadcast(k, m):

3 TBcast-broadcast $\langle$LOCK, k, m$\rangle$

4 TBcast-broadcast $\langle$SIGNED, k, m, sign((k, m))$\rangle$

6# at receivers:

7SWMR[me] = $[(-1,\ \bot,\ \bot),\ \ldots\ ]$ # array of t slots

8delivered = $[-1,\ \ldots\ ]$ # array of t slots

9locks = $[(-1,\ \bot),\ \ldots\ ]$ # array of t slots

10locked = $[[(-1,\ \bot),\ \ldots\ ],\ \ldots\ ]$ # array of t*n slots

12upon TBcast-deliver $\langle$LOCK, k, m$\rangle$ from p:

13 k’, _ = locks[k%t]

14 if k $\rangle$ k’:

15 locks[k%t] = (k, m)

16 TBcast-broadcast $\langle$LOCKED, k, m$\rangle$

18upon TBcast-deliver $\langle$LOCKED, k, m$\rangle$ from q:

19 k’, _ = locked[q][k%t]

20 if k $\rangle$ k’:

21 locked[q][k%t] = (k, m)

22 if locked[r@$_0$@][k%t] == ... == locked[r@$_{n-1}$@][k%t]:

23 deliver_once(k, m)

25upon TBcast-deliver $\langle$SIGNED, k, m, sig$\rangle$ from p:

26 if valid(sig, (k, m), p):

27 k’, m’ = locks[k%t]

28 if k $\rangle$ k’ or k == k’ and m == m’:

29 locks[k%t] = (k, m)

30 SWMR[me][k%t].write((k, sig, m))

31 for each (k’, s’, m’) in SWMR[*][k%t]:

32 if valid(s’, (k’, m’), p):

33 if k’ == k and m’ != m:

34 return # Byzantine broadcaster

35 if k’ $>$ k and k’ $\equiv$ k (mod t):

36 return # out of tail

37 deliver_once(k, m)

39def deliver_once(k, m):

40 if k $\rangle$ delivered[k%t]:

41 delivered[k%t] = k@\label{alg:tcb:update-delivered}

42 trigger deliver(k, m)

As mentioned, Algorithm 1 has a low-latency fast path that avoids signatures
and disaggregated memory. It also incorporates a fall-back slow path for
liveness. For presentation simplicity, it triggers the slow path in parallel
to the fast path (lines 3 and 4), but in reality, uBFT triggers it when
replicas fail to decide on new client requests after some configurable
duration. In addition to the shared SWMR registers, receivers use three
finite-size local arrays for bookkeeping (lines 8-10).

In the fast path, the broadcaster first TBcast-broadcasts its message
alongside its identifier within a LOCK message (line 3). When receivers
deliver this message (line 12), they commit not to deliver any other message
for the given identifier, and tell other receivers about their commitment by
broadcasting a LOCKED message (line 16). Receivers use locks (lines 13-15) to
avoid committing to different messages for the same identifier. Importantly,
receivers store only up to $t$ commitments in this array, by evicting earlier
commitments that alias to the same index $k\%t$ (line 15). When receivers
learn that everyone committed to the same message (lines 18-22), they know
that no correct replica will deliver a different message and thus deliver it
(line 23).

In the slow path, the broadcaster additionally TBcast-broadcasts a signed
version of its message (line 4). After TBcast-delivering a signed message
(line 25), receivers verify its signature (line 26). Then, they check that
they have not committed to a different message for the same $k$ (line 28), and
ensure that they will not do so in the future (line 29).  Subsequently, they
copy the signed message to their SWMR register associated with the message
identifier $k$ (line 30), before reading the associated SWMRs owned by other
receivers (line 31). Receivers ignore messages with invalid signatures (line
32) and abort delivery if they detect a different message for the same
identifier (line 33). In case receivers detect another message with a higher
identifier that is associated with the same SWMR registers (line 35), they
drop their own message as it no longer belongs to the tail. Otherwise, they
deliver it (line 37).

The correctness of the slow path of Algorithm 1 hinges on that all correct
processes will find the message copied by the _fastest_ correct replica when
reading the registers. Thus, they can deliver no message other than the first
copied, hence preserving agreement. The fast and slow paths are linked
together via the locks array (lines 15 and 29), which ensures that whichever
path executes first forces the value of the message for the other path. Note
that when the broadcaster is Byzantine, correct processes are allowed not to
deliver. A more detailed proof of correctness is given in  Appendix A.

##  5\. State Machine Replication

Like all leader-based BFT consensus protocols, uBFT’s protocol has the same
high-level layout as PBFT (Castro and Liskov, 1999): it shares naming
conventions and splits the protocol in similar phases. However, uBFT has
different goals ($2f{+}1$ fault tolerance, finite memory, microsecond
latency), different assumptions (disaggregated memory), and a different non-
equivocation mechanism (Consistent Tail Broadcast (CTBcast)). As a result,
uBFT’s protocol is structurally different from PBFT, as we describe in this
section.

We start by giving an overview of our consensus protocol. Then, we analyse its
slow path and explain how it deals with finite memory and view changes.
Finally, we describe how its fast path leverages unanimous and timely
collaboration of replicas to achieve microsecond-scale latency. For
presentation clarity, this section gives only an informal description of our
protocol. Its pseudocode is given in Appendix B alongside detailed arguments
of its correctness.

###  5.1. Basic Protocol

Figure 3. Communication pattern of uBFT’s slow path. Bold lines represent
messages sent over CTBcast. Thinner lines represent direct messages.

From a high-level point of view, the slow path of our consensus protocol—shown
in Figure 3—has three phases: _Prepare_ , _Certify_ and _Commit_. After the
leader receives a signed request from a client, it _proposes_ it by
broadcasting a Prepare message via CTBcast. When replicas (including the
broadcaster) deliver this message, they proceed to its certification. Each
replica signs the proposal and TBcast-broadcasts its signature in a CERTIFY
message. Then, it waits to aggregate $f{+}1$ signatures on the proposal, which
constitute an unforgeable proof that the proposal was emitted by the leader.
Moving on to the Commit phase, the replicas broadcast via CTBcast a COMMIT
message containing the aforementioned proof. Finally, after delivering $f{+}1$
COMMIT messages, replicas apply the client’s request to their local state
machine and reply to the client. Note that we use TBcast instead of the more
expensive CTBcast when broadcasting CERTIFY messages: equivocation of CERTIFY
messages does not harm correctness as all certificates involve at least one
correct replica, and all correct replicas certify the same proposal due to the
CTBcast in the Prepare phase.

So far, the described protocol replicates a single client request. Similarly
to PBFT, uBFT uses a sliding window to run its consensus protocol on a series
of slots. As the leader receives multiple requests, it proposes each one in a
different slot, handling many slots in parallel. uBFT also uses PBFT’s
application checkpoints to throttle the number of concurrent request
proposals. This mechanism limits the impact of a Byzantine leader, and bounds
the number of relevant messages at any point in time. An application
checkpoint is signed by $f{+}1$ replicas and includes (1) the state of the
application after applying the first $i$ replicated requests to it, and (2) an
implicit authorization to work on slots $[i+1,i+\textit{window}]$.

###  5.2. Non-Equivocation at the Consensus Level

An important aspect of uBFT’s consensus protocol is how it prevents the leader
from sending conflicting proposals. CTBcast only partially solves this issue:
it prevents a Byzantine leader from sending conflicting proposals in a single
message, but it does not prevent it from sending conflicting proposals across
multiple messages. Conceptually, a process can ensure that another process has
not equivocated if the former knows the entire history of messages broadcast
by the latter. For this reason, processes in our protocol interpret messages
of other processes in FIFO order. However, CTBcast does not guarantee the
delivery of all broadcast messages due to its tail-validity property, which
might prevent processes from delivering _all_ the messages from a correct one
in FIFO order. We solve this issue by pairing CTBcast with _CTBcast
summaries_.

A CTBcast summary is an unforgeable synopsis of what has been broadcast by a
process $p$ via CTBcast up to a given CTBcast identifier. Summaries constitute
certificates that are signed by $f{+}1$ replicas, which have witnessed the
messages broadcast by $p$ and assert that $p$ has not equivocated at the
consensus level. When a process receives a summary about $p$ up to a certain
CTBcast identifier $i$, it is able to continue handling $p$’s new messages
above $i$ in FIFO order. Essentially, CTBcast summaries restore FIFO delivery
that may have been broken by the tail-validity of CTBcast.

CTBcast summaries are generated interactively. Every $t$ consecutive CTBcast
messages ($t$ is CTBcast’s tail parameter) that a replica $r$ delivers from
$p$, $r$ participates in creating a summary about the state of $p$. Replica
$p$ knows how many messages it has broadcast and blocks waiting for a summary
of its state every $t$ messages. Using its previous summary, $p$ can bring
correct processes that missed some of its messages up to speed, and help them
deliver the last $t$ messages it broadcast so far. Even if $f$ Byzantine
replicas fail to help building $p$’s next summary, all correct replicas would
eventually collaborate to generate it, thus ensuring the liveness of the
summaries and allowing $p$ to keep broadcasting.

It is important to ensure that CTBcast summaries have finite size. To this
end, a process keeps only a limited number of messages that it CTBcast-
delivers from others, by maintaining a window of consensus slots for every
other broadcasting process. If a process $p$ CTBcast-delivers a message from
another process $q$ out of the window it maintains for $q$, $p$ considers $q$
as being Byzantine. uBFT requires processes to CTBcast-broadcast application
checkpoints in order to slide their window on the receivers’ side. When a
receiver slides a broadcaster’s window forward, it drops messages referring to
slots that fall out of it, since the consensus slots they refer to have been
checkpointed. This way, the entire relevant state of a broadcaster is a
combination of a consensus window range and the collection of CTBcast messages
that fall into it.

###  5.3. View Change

To tolerate faulty leaders, uBFT follows PBFT’s _view change_ approach.
Briefly, every view has a dedicated leader determined in a round-robin manner.
If a replica does not make progress or believes that the leader is censoring
client requests, it moves to the next view by CTBcast-broadcasting a SEAL_VIEW
message. The leader of the new view first transfers any potentially applied
requests to the new view by CTBcast-broadcasting a NEW_VIEW message before
proposing new requests, as detailed below.

The NEW_VIEW message contains the latest application checkpoint, as well as
all COMMIT messages about the open slots following this checkpoint from
$f{+}1$ replicas. More precisely, when a replica $p$ receives a SEAL_VIEW
message from another replica $q$, $p$ proceeds with generating a certificate
share about $q$’s state. In fact, this state includes $q$’s latest application
checkpoint, as well as the latest COMMIT messages sent by $q$ for each one of
$q$’s open slots. The content of the NEW_VIEW message consists of $f{+}1$
matching certificate shares about $f{+}1$ different replicas. The broadcast
NEW_VIEW message constrains the values that the new leader can propose for
open slots. That is, for every open consensus slot, the new leader is required
to propose the value of the COMMIT message with the highest view number (if
any).

The view change mechanism prevents a leader from omitting requests that were
decided in previous views. Intuitively, if a correct replica decided on a
request in some view, it must have received $f{+}1$ matching COMMIT messages.
As the leader collects certificates about $f{+}1$ replicas, it must
necessarily include at least one certificate with a COMMIT message for all
decided requests.

###  5.4. Fast Path

Figure 4. Communication pattern of uBFT’s fast path. Bold lines represent
messages sent over CTBcast. Thinner lines represent direct messages.

To operate at the microsecond scale, uBFT incorporates a fast path—shown in
Figure 4—that moves signatures out of the critical path in times of synchrony
and unanimous collaboration. Similar to the slow path, the fast path has three
phases: Prepare, which is common with the slow path but executes the fast path
of CTBcast, followed by WillCertify and WillCommit. The last two phases
replace the Certify and Commit phases of the slow path with inexpensive rounds
of Tail Broadcast.

The operation of the fast path is simple. For a given consensus slot, after
the end of the Prepare phase, replicas broadcast a WILL_CERTIFY message and
wait to receive the same message from all others. Once received, they proceed
with broadcasting a WILL_COMMIT message and again wait for unanimity before
deciding on the proposed value. Both messages contain solely the view number
and the consensus slot. These messages are essentially promises that their
broadcaster will run the slow path before CTBcast-broadcasting its next
SEAL_VIEW message. By broadcasting WILL_CERTIFY, a replica promises to
participate in certifying the PREPARE message. With WILL_COMMIT, it promises
to CTBcast-broadcast the resulting certificate within a COMMIT message.

The safety of this scheme is intuitive. If a replica receives $2f{+}1$
WILL_CERTIFY messages, it knows that at least $f{+}1$ correct replicas will
certify the PREPARE message in the Certify phase. Similarly, receiving
$2f{+}1$ WILL_COMMIT messages means that at least $f{+}1$ correct replicas
will send a COMMIT message in the Commit phase and thus no other value will be
decided for this slot.

The fast path also takes care of finite memory as it does not keep promises
forever: it drops the promises that refer to consensus slots included in an
application checkpoint. These checkpoints along with the CTBcast summaries
make up the required background signatures of uBFT’s fast path.

Lastly, the fast path eschews signatures between clients and replicas by
having the clients send unsigned requests to all replicas, instead of a signed
request to the leader. A replica endorses a PREPARE message on a client
request only if it also received it from the client. Thus, the fast path
contains an additional communication round (denoted Echo Req) in which the
leader waits for the followers to echo the client request before proposing it.
This way, a Byzantine client cannot cause a leader to get stuck (and thus
incur a view change) by not sending its requests to all correct replicas.

##  6\. Implementation

The design of uBFT relies on disaggregated memory to build the shared
registers used by CTBcast, and on a fast networking fabric to achieve its
microsecond-level latency. This section explains how we use RDMA
(Technologies, 2015) to achieve these goals.

###  6.1. Reliable SWMR Regular Registers

The CTBcast component of uBFT requires reliable SWMR regular registers.
Reliable means that the registers do not fail, i.e., READs and WRITEs always
complete. SWMR means Single-Writer Multiple-Reader: each register has an
owner, which is a replica that is allowed to write to it, while all other
replicas may only read the register. Regular means that, when a READ executes
concurrently to a WRITE, the former should return either the value that is
being written or the previous one. We explain below how to implement each
property using RDMA.

#### SWMR Register.

We implement SWMR registers using RDMA permissions. RDMA splits memory into
regions, each with different access permissions based on a token. We create a
read-write and a read-only region for the same memory range, give the read-
write token to the writer of the register, and the read-only token to the
other replicas.

Figure 5. Reliable SWMR Regular registers using RDMA.

#### Regular Register.

RDMA-exposed memory is atomic (hence regular), but only at an 8-byte
granularity. While RDMA WRITEs have left-to-right ordering, RDMA READs do not.
Thus, an RDMA READ concurrent with a WRITE may return partially written data,
mixing old and new values. To detect this problem, we use checksums, as in
Pilaf (Mitchell et al., 2013). A simple approach, where a reader retries until
the checksum is valid, violates liveness as a Byzantine writer can write bogus
checksums. To avoid such scenario, we follow an evolved double-buffering
strategy, which ensures that a reader is always able to find a complete WRITE
or detect the owner of the register as being Byzantine. As depicted in Figure
5, each register is made of two sub-registers. Each WRITE to a given register
is directed to one of the sub-registers in a round-robin manner. To write a
value, the writer prefixes it with a logical timestamp (denoted ts) and a
checksum. Importantly, the writer waits for $\delta$ (the known communication
bound after GST) between two WRITES to the same register. To perform a READ,
the reader reads both sub-registers at once and, out of the values with a
valid checksum, returns the one with the highest timestamp. 333 The hardware
is allowed to reorder RDMA READs following RDMA WRITEs when issued to
different Queue Pairs (QPs) (Association, 2020). To ensure regularity, i.e.,
that subsequent register READs see the RDMA-written value, a register WRITE
only returns after the PCIe WRITE transaction reaches the last-level cache
(L3). We do so by issuing an RDMA READ after the RDMA WRITE to the same
QP—which acts as a PCIe fence (Gromadzki and Michalski, 2019)—and only
considering that the register WRITE completes when the RDMA READ completes.
If both checksums are invalid and the READ took less than $\delta$, the writer
is Byzantine and a default value is returned. Otherwise, the READ is retried.
The writer is also deemed Byzantine if both sub-registers have the same
timestamp. This scheme works in an eventually synchronous system with bounded-
drift clocks (Guerraoui et al., 2022; Dragojević et al., 2015): when the
writer and a reader are correct, a READ does not overlap with two WRITEs, so
one of the sub-registers will have a valid checksum, and ordering based on
timestamps ensures regular register semantics.

#### Reliable Register.

We replicate each register to $2f_{m}{+}1$ memory nodes, where each memory
node exposes its memory over RDMA (Figure 5). Here, $f_{m}$ is the maximum
number of memory nodes that may crash. While memory nodes add to the total
number of replicas in the system, these nodes do not replicate the
application, and they can be shared among many replicated applications, as
each application takes a small amount of space in the memory nodes (§7.6). Our
register replication scheme is straightforward. WRITEs are issued to all
memory nodes in parallel and return after having completed at $f_{m}{+}1$ of
them. READs are also issued to all nodes in parallel, wait for $f_{m}{+}1$ of
them to complete, and return the value of the regular register with the
highest timestamp. This scheme tolerates Byzantines replicas, as READs and
WRITEs always complete at a majority, and preserves regular semantics. Indeed,
when a READ is not concurrent to any WRITE, intersecting quorums ensure that
the last written value is returned. In case of concurrency, the READ
intersects with the concurrent WRITE in some register and with the last
completed WRITE in some other register. Thus, it will return a value no older
than the value of the last completed WRITE, ensuring regularity.

###  6.2. A Fast Message-Passing Primitive

Figure 6. uBFT’s RDMA-powered message-passing primitive.

To achieve microsecond-scale communication, uBFT implements a fast one-way
messaging primitive between a sender and a receiver, where the receiver is
required to deliver only the last $t$ messages of the sender, similarly to
CTBcast.  This primitive allows an implementation without receiver
acknowledgements, which we found to be important for microsecond-scale
performance.

Figure 6 depicts the implementation of this primitive over RDMA. The receiver
has a circular buffer exposed over RDMA; the buffer is divided into $t$ slots
of equal size large enough for the largest message. Briefly, the sender RDMA-
writes messages to the receiver’s buffer, while the latter scans its local
buffer for new messages. There are no acknowledgments: the sender overwrites
old messages with newer ones, even if they were not yet received.

We now explain this implementation in detail. The sender allocates a mirror
image of the receiver’s buffer in its local memory, and maintains locally a
_write pointer_ to the slot for its next message. Each slot has a header
composed of a checksum, an incarnation number (the number of times it was
written), and a message size. To send a new message, the sender writes it to
the slot pointed by the writer pointer and fills its header. Then, it issues
an RDMA WRITE to the corresponding slot in the receiver’s memory, and marks
the slot as unavailable until it is notified of the completion of the WRITE by
the RDMA NIC. Finally, the sender advances its write pointer. If the pointed
slot is unavailable, the new message is queued in a second (not depicted)
circular buffer. This buffer acts as a staging area: it forwards its messages
for transmission when slots become available, and evicts the oldest queued
message to accommodate a newer one.

The receiver maintains a _read pointer_ to the slot where it will read the
next message. The receiver polls this slot for a particular incarnation
number, which identifies the next message it expects to find. Once this
incarnation number is seen, the receiver copies the entire message to a
private buffer in order to avoid interfering WRITEs on the same slot. Then,
the receiver checks the incarnation number again in the copied message. If the
incarnation number has not changed, the sender verifies the checksum before
delivering the message (rescheduling the polling if the checksum is invalid).
If the receiver finds a higher incarnation number than expected, it concludes
that some older messages may exist in other slots of the buffer that will have
to be delivered first. So, the receiver aborts the delivery and advances its
pointer to the oldest undelivered message. With this strategy, the receiver
guarantees FIFO delivery of the last $t$ messages.

This scheme has two benefits: it uses practically bounded memory and avoids
acknowledgements. The latter—even when batched—increase the application’s tail
latency as scheduling an acknowledgement alone takes $\approx$300 ns (Kalia et
al., 2014), which is time lost handling incoming events. Instead, by the End-
to-End Principle (Saltzer et al., 1984), acknowledgements are piggybacked in
SMR-level messages.

##  7\. Evaluation

We evaluate the various performance traits of uBFT and verify its suitability
as a BFT SMR system for microsecond applications. We aim to answer the
following:

  * •

How much latency does uBFT induce on the replicated applications (§7.1)?

  * •

How does the replication latency of uBFT compare to other SMR systems (§7.2)?

  * •

How do the internal components of uBFT contribute to its end-to-end latency
(§7.3)?

  * •

How does our implementation of CTBcast perform in comparison to SGX-based non-
equivocation mechanisms (§7.4)?

  * •

How does the tail parameter of CTBcast impact uBFT’s tail-latency (§7.5)?

  * •

What is the memory consumption of uBFT (§7.6)?

Table 1. Hardware details of machines. CPU |  2x Intel Xeon Gold 6244 CPU @ 3.60 GHz (8 cores/16 threads per socket)
---|---
NIC |  Mellanox ConnectX-6 MT28908
Switch |  Mellanox MSB7700 EDR 100 Gbps
OS/Kernel |  Ubuntu 20.04.2 / 5.4.0-74-generic
RDMA Driver |  Mellanox OFED 5.3-1.0.0.1

We evaluate uBFT in a 4-node cluster, the details of which are given in Table
1. Our dual-socket machines are NUMA and their RDMA NIC lies on the first
socket. For this reason, we ensure that all threads during our experiments
execute on cores of the first socket. We also exclusively use the memory bank
closest to this socket.

Our implementation (Aguilera et al., 2022) measures time using the
clock_gettime function with the CLOCK_MONOTONIC parameter. The function uses
the TSC clock source of Linux for efficient and accurate timestamping (Red
Hat, 2020).

In all experiments we deploy 1 client and 3 replicas, and take at least 10,000
measurements. Additionally, we set the consensus window to 256 requests
and—unless stated otherwise—the tail parameter of CTBcast to 128 messages.

#### Applications.

We integrate uBFT with MemCached (Kalia et al., 2014), Redis (Sanfilippo,
2022) and Liquibook (Newhuis, 2022). MemCached and Redis are non-replicated
high-performance KV-stores. Liquibook is a data structure that implements a
financial order matching engine. We also integrate all the aforementioned
applications with Mu (Aguilera et al., 2020), the SMR system that has the
lowest replication latency (to our knowledge) but tolerates only crash faults.
In all applications, the client sends messages using uBFT’s RPC mechanism.
Additionally, using a no-op application, we compare uBFT against MinBFT
(Veronese et al., 2013), a state-of-the-art $2f{+}1$ BFT SMR system with a
publicly available implementation which uses Intel’s SGX (Costan and Devadas,
2016). SGX provides a secure CPU enclave for executing arbitrary code, thus
offering a general-purpose trusted computing base.

#### Implementation Effort.

We implemented uBFT on top of a framework (Guerraoui et al., 2022) that
facilitates the use of RDMA. Our prototype spans 11,750 lines of C++, out of
which 2,966 are dedicated to CTBcast. The prototype includes all features on
the critical path of a complete implementation: the only major unimplemented
features are application and replica state transfers. We use Dalek’s
implementation of EdDSA over Curve25519 (Lovecruft et al., 2022) for public-
key cryptography, BLAKE3 (O’Connor et al., 2022) for HMACs and xxHash (Collet,
2022) for checksums.

###  7.1. End-to-End Application Latency

Figure 7. End-to-end latency of different applications when either not
replicated or replicated via Mu and uBFT’s fast path. The printed values are
the 90th %-iles. The whiskers show the 50th and 95th %-iles.

Figure 7 explores the replication overhead that uBFT induces to end
applications. We compare the latency of its fast path against the unreplicated
latency, and the latency when replicating with Mu. We study four applications:
Flip, a toy application that reverses its input, as well as Memcached, Redis,
and Liquibook.

The KV-stores use 16 B keys and 32 B values. Our workload is 30% GETs, out of
which 80% succeed and return a non-empty value. Liquibook’s requests are 32 B.
Its responses range from 32 B to 288 B, depending on how many orders match.
50% of the orders are BUY and 50% SELL. Finally, Flip’s requests and responses
are 32 B long.

From the figure, observe that uBFT is consistently slower than Mu by
approximately 7.5 µs at the 90th percentile. uBFT’s additional induced end-to-
end latency is most significant for ultra fast applications, such as Flip, for
which our system is 3 times slower than Mu. As the application’s unreplicated
latency increases, uBFT’s latency overhead diminishes. For Liquibook, it is
$2\times$ slower than Mu and for the KV-stores, it is only $1.5\times$ slower.
At the same time, uBFT’s replication increases the latency variance (i.e., the
difference between the 50th and 95th percentiles) compared to Mu, which is a
consequence of the complexity of our system. More precisely, uBFT’s RPC
requires one more round of communication than Mu’s to ensure that all correct
replicas have received the client request. Additionally, uBFT’s replication
scheme requires 4 rounds of broadcast before replying to the client instead of
a single majority WRITE in Mu. Overall, uBFT’s fast path has 4 additional
rounds of communication compared to Mu, hence the higher tail latency.
Nevertheless, uBFT does not worsen the variance by more than 3 µs.

In a nutshell, with uBFT, assuming a timely network and the absence of
failures, an unreplicated application that operates at the microsecond-scale
envelope requires at most an extra 10 µs to become Byzantine fault tolerant.

###  7.2. End-to-End Replication Latency

We now explore the impact of the size of requests on the end-to-end latency of
uBFT. Figure 8 shows the median client-side latency for various request sizes
to a no-op application with different replication schemes. The service replies
with responses matching the size of requests.

As expected, the lowest latency is achieved without any replication (denoted
Unrepl.). Here, the end-to-end latency ranges from 2.2 µs to 20 µs, which is
attributed to communicating with the server side using our RPC. The other
lines show the service replicated with: Mu, our BFT SMR solution, and MinBFT,
a $2f{+}1$ BFT alternative.

Figure 8. Median end-to-end latency for different request sizes of an
unreplicated no-op application, as well as its latency when replicated with
Mu, uBFT and MinBFT.

Mu’s replication increases the end-to-end latency by up to 64% for small
requests and by at most 26% for 8 KiB ones. In the absence of failures, Mu’s
leader replicates the requests it receives by just RDMA-writing them to its
followers. uBFT’s fast path exhibits higher latency than Mu due to its 4
additional rounds of communication, yet it only increases the overhead
compared to the latter by at most 175%, even though it offers Byzantine fault
tolerance.

One could expect that uBFT’s fast path would come at the cost of high latency
in the slow path, yet this is not the case. We compare our slow path against
MinBFT, with the latter operating in two configurations. In its vanilla
configuration, MinBFT uses HMACs only between the replicas, however the
clients sign the requests sent to the service using public-key cryptography,
leading to a minimum end-to-end latency of 566 µs. We modify MinBFT to also
use SGX in the clients, thus replacing their expensive cryptography with
HMACs. Since our setup does not offer SGX, we stub it using the latency
results of Section 7.4. Note that MinBFT is not an RDMA-tailored application
and it uses standard TCP in its implementation.

To increase the fairness of our comparison with MinBFT, we use Mellanox’s VMA
library (Technologies, 2022) to replace MinBFT’s TCP stack with a kernel-
bypass alternative that uses RDMA NICs for increased performance. The end
result is that uBFT’s slow path is faster than vanilla MinBFT (up to 109%) and
at most 24% slower than its purely HMAC-based variant, even though our slow
path uses public-key cryptography.

###  7.3. Latency Breakdown

Figure 9. Recursive decomposition of the end-to-end latency of uBFT’s fast and
slow path when replicating Flip with requests of 8 B.

To get a better understanding of uBFT’s end-to-end latency, we analyze the
latency of its internal components.

Figure 9 shows a recursive decomposition of the latency of an 8 B Flip request
into its constituents: remote-procedure call, Consistent Tail Broadcast and
replication (denoted RPC, CTB and SMR respectively). The rightmost columns of
the figure show the client-perceived latency (denoted E2E). Each bar has two
regions: the narrow left one shows the overall latency of the component, while
the wider right one shows its decomposition.

In our decomposition, we identify four primitive sources of latency. First is
the time for communication over our message-passing primitive (denoted P2P).
Next is the time for producing and verifying signatures (denoted Crypto), and
the time for reading and writing to the disaggregated memory registers
(denoted SMWR). Both of these are only relevant in uBFT’slow path. The Crypto
primitive goes beyond pure cryptographic computation, as it includes the
synchronization cost of issuing the operation to a thread pool and getting
back the result. Lastly, there is the time spent in bridging these basic
primitives and connecting the components (denoted Other). This last category
includes copying buffers, delays between the arrival and processing of
asynchronous events, etc.

We can see that, in the fast path, most of the time is spent in communication.
Given the small size of the messages, the potential avenues for improving the
overall latency is to either reduce the number of communication steps or
reduce the latency of the underlying network fabric. In the slow path, public-
key cryptography dominates. Given that signatures are unavoidable in our
setting (Aguilera et al., 2021), achieving better latency requires faster
cryptographic primitives. Also, notice that the cost of accessing
disaggregated memory—which is part of CTB—is negligible, as it accounts for 14
µs (3.5%) of the end-to-end latency.

###  7.4. Latency of Non-Equivocation

Figure 9 demonstrates that CTBcast accounts for a substantial portion of the
end-to-end latency of our system’s fast and slow paths.  By using
disaggregated memory, our implementation of CTBcast has an advantage over
solutions that use CPU enclaves, since disaggregated memory is a much smaller
and simpler trusted computing base. Moreover, the fast/slow path approach of
our implementation allows it to operate fast in the common case by entirely
bypassing signatures and the trusted computing base. This section quantifies
the performance of our implementation of CTBcast against the de facto way of
preventing equivocation in modern systems (Veronese et al., 2013; Behl et al.,
2017; Liu et al., 2019), namely a trusted counter implemented on Intel’s SGX.

Figure 10. Median latency of multiple non-equivocation mechanisms for
different message sizes.

Non-equivocation mechanisms based on trusted counters work by securely binding
a monotonically increasing sequence number to each message broadcast by a
process. All enclaves store a local $counter$ and share a common $secret$.
Before broadcasting a message, a process feeds it to its local enclave and
gets back a proof of non-equivocation of the form
$HMAC_{secret}(msg||counter||process~{}id)$. The recipients of a message use
their own local enclave to verify the authenticity of the HMAC, and thus
prevent equivocation. Note that, as authentication takes place exclusively in
the enclaves, this non-equivocation mechanism avoids the use of expensive
public-key cryptography.

Figure 10 shows the median latency of the two non-equivocation mechanisms
between a sender and two receivers. The lowest latency is achieved by the fast
path of our implementation of CTBcast and ranges from 2.2 µs to 11 µs
depending on the message size. In this mode of operation, CTBcast delivers on
unanimous and timely participation of all processes to avoid signatures and
prevent equivocation using merely two rounds of Tail Broadcast. CTBcast’s slow
path (triggered under failures) relies on public-key cryptography, which
dominates the latency and raises it to approximately 86 µs. The latency of
preventing equivocation using SGX includes accessing the enclave twice, once
in the sender and once in the receiver, as well as broadcasting the message.

Due to the lack of SGX in our RDMA experimental setup, we evaluate the cost of
accessing the SGX on different hardware to get a good approximation. The SGX
hardware is provided by a machine with an Intel i7-7700K CPU running at 4.2
GHz, which is 0.6 GHz higher than the CPU frequency of our RDMA setup.
Accessing the enclave (once) ranges from 7 µs to 12.5 µs, which makes
preventing equivocation using the SGX take at least 16 µs. The resulting
latency is shown in the middle line of Figure 10.

Overall, for both non-equivocation approaches, larger message sizes lead to a
linearly higher latency, due to the hashing and communication latency.
CTBcast’s fast path is up to $6.5\times$ faster than the SGX solution, by
taking advantage of the ultra fast communication.

###  7.5. Impact of CTBcast’s Tail on Tail Latency

Figure 11 shows how the size of the tail in CTBcast (parameter $t$) affects
the client’s tail latency. We focus on uBFT’s fast path and execute Flip with
small 64 B requests and larger 2 KiB ones. For both request sizes, we explore
four tail parameters.

For smaller values of $t$, we see a latency spike indicative of thrashing as
we move to higher percentiles. This spike occurs because CTBcast uses a double
buffering mechanism with cryptographic summaries (§5.2) to switch between
them; if both buffers fill before a summary occurs (due to a small $t$),
CTBcast stalls. The smaller the $t$, the sooner the buffers fill, the more
often CTBcast stalls, and hence the lower the percentile of the spike. For
small requests, a tail $t{=}128$ avoids thrashing up to the 99th percentile.
For larger requests, $t{=}64$ suffices, as filling the buffers takes more
time, giving more time for the summary to occur.

Figure 11. uBFT’s tail latency for different CTBcast tails $t$ for 2 KiB
requests (top) and 64 B requests (bottom).

###  7.6. Memory Consumption

Given the fundamental goal of uBFT to operate using finite memory, we monitor
the consumption of disaggregated memory and the local memory consumption at
the leader replica, while re-running the experiment of Section 7.5.

Table 2. uBFT replica (top) and disaggregated (bottom) memory usage for different CTBcast tails $t$ and request sizes. Request size | t = 16 | t = 32 | t = 64 | t = 128
---|---|---|---|---
64 B | 0.46 GiB | 0.47 GiB | 0.49 GiB | 0.53 GiB
2 KiB | 4.3 GiB | 4.5 GiB | 4.8 GiB | 5.5 GiB
Disag. Mem. | 20 KiB | 40 KiB | 81 KiB | 162 KiB

Table 2 summarizes the results for two different request sizes (64 B and 2
KiB) and four different $tail$ parameters of CTBcast (16, 32, 64 and 128). For
the small 64 B requests, the local memory consumption starts at 0.46 GiB. This
is the entire memory that uBFT preallocates at startup and uses during its
lifetime. When CTBcast’s tail $t$ increases, uBFT’s memory consumption
increases linearly by $\approx$1 MiB for each additional message in the tail.
For the large 2 KiB requests, the memory consumption starts at 4.3 GiB
($t{=}16$) and increases at a rate of $\approx$11 MiB per message.

uBFT consumes little disaggregated memory. The last row of Table 2 shows the
memory used at a single memory node. This amount is independent of the size of
requests and depends only on CTBcast’s tail $t$: messages sent over CTBcast
are transmitted using our fast message-passing primitive; upon receiving a
message, a receiver writes to disaggregated memory only the message’s id and
its fingerprint (a 32 B cryptographic hash); the register implementation
(§6.1) stores two copies, each with an 8 B checksum. To save space, registers
use the identifiers of messages as their timestamps.

##  8\. Related Work

uBFT uses RDMA to instantiate disaggregated memory. Prior work identifies some
benefits and downsides of using RDMA in an adversarial environment. Aguilera
et al. (Aguilera et al., 2019, 2021) propose new RDMA-based techniques to
enhance the resilience and performance of BFT algorithms. That work is
abstract and far from practical solutions: it requires infinite memory and
solves only single-shot consensus, stopping short of a solution for an SMR
system. Rüsch et al. (Rüsch et al., 2018) design a Byzantine fault tolerant
system that uses RDMA to improve performance, but requires $3f{+}1$ processes.

Prior work identifies vulnerabilities in the current generation of RDMA
hardware and proposes ways to mitigate them (Taranov et al., 2020;
Rothenberger et al., 2021). That work is orthogonal to uBFT and could be
applied to it. We expect that these problems will eventually be fixed with
future NICs.

With a black-box mechanism to prevent equivocation, only $2f{+}1$ replicas are
required for BFT (Correia et al., 2004; Clement et al., 2012; Ben-David et
al., 2022; Ben-David and Nayak, 2021). Several BFT systems achieve that using
trusted hardware as the black box: attested append-only memory (A2M) (Chun et
al., 2007) uses a trusted log, TrInc (Levin et al., 2009) and MinBFT (Veronese
et al., 2013) use a trusted counter, Hybster (Behl et al., 2017) uses Intel’s
SGX, CheapBFT (Kapitza et al., 2012) uses FPGAs, and  H-MFT (Zhuo et al.,
2014) uses trusted hypervisors to implement write-once tables.  By separating
execution from agreement (Yin et al., 2003), one can reduce the number of
execution replicas to $2f{+}1$, but $3f{+}1$ replicas are still required for
agreement. Avocado (Bailleu et al., 2021) implements a high-performance
replicated confidential KV-store using CPU enclaves as the trusted computing
base.

Blockchain systems also tolerate Byzantine failures, but their latency is in
the seconds or minutes due to their heavy use of cryptography (Gilad et al.,
2017; Kokoris-Kogias et al., 2016), proof of work (Nakamoto, 2008; Eyal et
al., 2016), and/or batching (Buchman et al., 2018; Yin et al., 2019). The
recent SplitBFT (Messadi et al., 2022) uses SGX and $3f{+}1$ replicas to
strengthen the safety and confidentiality of blockchains in public clouds.

While most of the prior work is not focused on microsecond-scale latency (and
hence came up with different solutions from ours), some recent SMR systems aim
for lower latency. Mu (Aguilera et al., 2020) is highly optimized and provides
microsecond-scale performance, but tolerates only crash failures. SBFT (Golan-
Gueta et al., 2019) tolerates Byzantine failures and uses a fast path to
improve latency, but does not achieve microsecond-scale performance due to its
use of cryptography. BFT SMR systems with $3f{+}1$ replicas can avoid
cryptographic signatures, for example, in PBFT’s optimized implementations
(Castro and Liskov, 1999). However, this is impossible in a system with
$2f{+}1$ replicas (Correia et al., 2004); the key to uBFT’s performance is
thus avoiding signatures on the fast path.

Carbink (Zhou et al., 2022) and Hydra (Lee et al., 2019) build reliable
disaggregated memory to improve memory utilization in a cluster, albeit
without support for concurrent shared access. MIND (Lee et al., 2021), GAM
(Cai et al., 2018) and Clover (Tsai et al., 2020), on the other hand, provide
reliable shared memory, but they do not tolerate Byzantine writers.

##  9\. Discussion

#### Does microsecond 2f+1 BFT require disaggregated memory?

To achieve microsecond-scale BFT SMR, one must avoid the use of expensive
signatures and trusted components in the critical path. uBFT does so via a
fast/slow path design that uses disaggregated memory in the slow path. This
leads to a small trusted computing base, but there may be other ways to
achieve non-equivocation in CTBcast’s slow path without affecting fast-path
performance.

#### Can uBFT work with a Byzantine network?

uBFT assumes network connections are authenticated and tamper-proof, which is
realistic in data centers, where widely deployed protocols such as IPsec and
SSL provide such guarantees at line rate. What if such protocols are not
available? We can implement simple authenticated channels within uBFT without
signatures in the critical path, by augmenting messages with an HMAC. With
BLAKE3, creating or verifying 256-bits HMACs takes $\approx$100 ns. As a
result, we expect less than 2 µs of additional overhead on the fast path of
uBFT.

#### What about uBFT’s throughput?

Any system can provide a throughput that is inverse of its latency. For uBFT,
that amounts to ${\approx}91$ kops for small 32 B requests. uBFT doubles this
figure, by exploiting the slack between the processing of events in a
consensus slot to interleave two requests with minimal latency penalty.
Throughput can be further optimized using well-known techniques, such as
batching (Danezis et al., 2022) and running parallel consensus instances on
multiple cores (Behl et al., 2017), but we have not done so.

##  10\. Conclusion

uBFT is the first BFT SMR system to achieve microsecond-scale latency,
$2f{+}1$ replicas, practically bounded memory, and a small non-tailored
trusted computing base. To do that, uBFT introduces Consistent Tail Broadcast
to prevent equivocation, and a matching consensus algorithm. uBFT uses
disaggregated memory as a trusted computing base, which our prototype
implements using RDMA. We applied uBFT to three applications to show that BFT
can be realistic in data centers even in latency-critical settings.

## Acknowledgments

We thank our anonymous reviewers for their valuable comments, as well as our
anonymous artifact evaluators for reviewing our prototype implementation.
Finally, we thank our colleagues Jovan Komatovic and Pierre-Louis Roman for
their feedback. This work has been supported in part by SNSF Early
Postdoc.Mobility grant P2ELP2_195126.

##  Appendix A Correctness of Consistent Tail Broadcast

In this section, we provide a correctness argument for the implementation of
CTBcast given in Algorithm 1.

###### Observation 1.

A correct broadcaster $p$ TBcast-broadcasts at most one LOCK message and at
most one SIGNED message per sequence number $k$. Moreover, both of these
broadcasts hold the same message $m$.

###### Observation 2.

A correct process $p$ TBcast-broadcasts at most one LOCKED message per
sequence number $k$.

###### Proof.

Correct processes only broadcast LOCKED messages at line 16. Moreover,
locks$[k\%t]$, which is only modified at lines 15 and 29, is updated strictly
monotonically. Thus, once the branch is entered at line 14 (and thus
locks$[k\%t]$ updated at line 15), it cannot be entered for the same $k$,
which ensures that line 16 is executed at most once per $k$ at correct
processes. ∎

###### Lemma A.1 (Tail-Validity).

If a correct process $p$ broadcasts $(k,m)$ and never broadcasts a message
$(k^{\prime},m^{\prime})$ with $k^{\prime}\geq k+t$, then all correct
processes eventually deliver $(k,m)$.

###### Proof.

Let $p,k,m$ be as in the statement of the lemma and let $q$ be a correct
receiver. We will show that $q$ eventually delivers $(k,m)$, which is
sufficient to prove the lemma.

Since $p$ is correct, $p$ TBcast-broadcasts
$\langle\texttt{SIGNED},k,m,sig\rangle$ with a valid signature. Since both $p$
and $q$ are correct, $q$ eventually TBcast-delivers it.

The $\langle\texttt{SIGNED},k,m,sig\rangle$ message of $p$ will trigger at $q$
the event at line 25. Given that $p$’s signature is valid, the check at line
26 succeeds. By the premise, $p$ does not broadcast any message with sequence
number $k^{\prime}\geq k+t$, so locks$[k\%t]$, which is only modified at lines
15 and 29, cannot contain a value greater than $k$. Moreover, since no other
message $m$ is broadcast for $k$ (Observation 1), if locks$[k\%t]$ already
contains $k$, it must also contain the message $m$. Thus, $q$ enters the if
branch at line 28. Since $p$ is correct and no process can forge $p$’s
signature, no validly signed entry $(k,m^{\prime})$ with $m\neq m^{\prime}$
can exist in any process’s SWMR slot, so $q$ does not return by triggering the
check at line 33. Finally, since $p$ does not broadcast any message with
sequence number $k^{\prime}\geq k+t$, no process’s SWMR slot can contain a
validly signed entry $(k^{\prime},\cdot)$ with $k^{\prime}>k$ and
$k^{\prime}\equiv k\ (\textrm{mod}\ t)$, so $q$ does not return by triggering
the check at line 35. Therefore, $q$ must call deliver_once$(k,m)$ at line 37.
If this call does not deliver $(k,m)$, it must have been delivered before.
Thus, $q$ eventually delivers $(k,m)$. ∎

###### Lemma A.2 (Agreement).

If $p$ and $q$ are correct processes, $p$ delivers $(k,m)$ from $r$, and $q$
delivers $(k,m^{\prime})$ from $r$, then $m=m^{\prime}$.

###### Proof.

Assume towards a contradiction that $m\neq m^{\prime}$. We consider two cases:
(1) at least one process delivers via the fast path, and (2) both processes
deliver via the slow path.

In case (1), assume wlog that $p$ delivers via the fast path. Then $p$ must
have TBcast-delivered a LOCKED message from $q$ for $(k,m)$. So $q$ must have
TBcast-broadcast a LOCKED message at line 16. By Observation 2, $q$ cannot
have broadcast a LOCKED message for $(k,m^{\prime})$. Thus, it cannot have
delivered $m^{\prime}$ via the fast path. Moreover, $q$ must have put $m$ in
locks$[k\%t]$ at line 15. Thus $q$ cannot enter the if branch at line 28 and
cannot deliver $(k,m^{\prime})$ via the slow path either, hence a
contradiction.

In case (2), assume wlog that $p$ writes $(k,sig,m)$ to SWMR$[p][k\%t]$ (line
30) before $q$ writes $(k,sig^{\prime},m^{\prime})$ to SWMR$[q][k\%t]$. Thus,
when $q$ reads $p$’s $k\%t$ slot at line 31, $q$ sees either (i) $(k,sig,m)$
or (ii) $(k^{\prime\prime},\cdot,\cdot)$ with $k^{\prime\prime}>k$, and
$k^{\prime\prime}\equiv k\ (\textrm{mod}\ t)$. In case (i), $q$ will return by
triggering the check at line 33, and thus not deliver $(k,m^{\prime})$, a
contradiction. In case (ii), $q$ will return by triggering the check at line
35, and thus not deliver, a contradiction. ∎

###### Lemma A.3 (Integrity).

If a correct process delivers $(k,m)$ from $p$ and $p$ is correct, $p$ must
have broadcast $(k,m)$.

###### Proof.

Let $p$ and $q$ be correct processes and assume $q$ delivers $(k,m)$ from $p$.
There are two possible cases: (1) $q$ delivers using the fast path at line 23,
or (2) $q$ delivers using the slow path at line 37.

In case (1), $q$ must have TBcast-delivered LOCKED messages for $(k,m)$ from
all processes, including itself. Therefore $q$ must have TBcast-broadcast a
LOCKED message for $(k,m)$ at line 16 after TBcast-delivering a LOCK message
for $(k,m)$ from $p$. Thus, $p$ must have TBcast-broadcast a LOCK message,
which $p$ can only do as part of the CTBcast-broadcast call. So $p$ must have
broadcast $(k,m)$.

In case (2), $q$ must have TBcast-delivered a valid SIGNED message from $p$
for $(k,m)$. Since $p$ is correct and no process can forge its signature, $p$
must have broadcast a SIGNED message for $(k,m)$. So $p$ must have broadcast
$(k,m)$. ∎

###### Lemma A.4 (No duplication).

No correct process delivers $(k,*)$ from $p$ twice.

###### Proof.

Correct processes only deliver through `deliver_once`. Lines 40 and
LABEL:alg:tcb:update-delivered ensure that a correct process only triggers
$deliver$ at most once per sequence number $k$. ∎

###### Theorem A.5.

From Lemmas A.1, A.2, A.3 and A.4, Algorithm 1 implements all the properties
of Consistent Tail Broadcast. ∎

##  Appendix B Correctness of Consensus

Algorithm 2: Common Case (stable leader)

⬇

1CTBcasts FIFO-deliver and block upon a Byzantine message

3upon Init:

4 view = 0

5 next_slot = 0

6 checkpoint = (app_state: Initial, open_slots: [0, 99])Σ

7 for each replica:

8 state[replica] = {

9 view = 0, seal_view = $\bot$, new_view = $\bot$,

10 prepares: Map$\langle$slot, PREPARE$\rangle$ = {},

11 commits: Map$\langle$slot, COMMIT$\rangle$ = {},

12 checkpoint = (Initial, [0, 99])Σ }

14def Propose(req):

15 wait (leader(view) == me and next_slot in checkpoint.open_slots and
NEW_VIEW broadcast i@\phantom{}f view$$\rangle$$@ 0)

16 CTBcast-bcast $\langle$PREPARE, view, next_slot++, req$\rangle$

18upon CTBcast-dlvr $\langle$PREPARE, v, s, r$\rangle$ from p as P:

19 state[p].prepares[s] = P

20 if v != view or s $\notin$ checkpoint.open_slots: return

21 TBcast-bcast $\langle$WILL_CERTIFY, v, s$\rangle$ # Fast path

22 TBcast-bcast $\langle$CERTIFY, sign(P)$\rangle$ # Slow path

24# Fast path

25upon TBcast-dlvr $\langle$WILL_CERTIFY, v, s$\rangle$ from 2f+1:

26 if v != view or s $\notin$ checkpoint.open_slots: return

27 TBcast-bcast $\langle$WILL_COMMIT, v, s$\rangle$

29upon TBcast-dlvr $\langle$WILL_COMMIT, v, s$\rangle$ from 2f+1:

30 if v != view or s $\notin$ checkpoint.open_slots: return

31 trigger once Decide(s, state[leader(v)].prepares[s].req)

33# Slow path

34upon TBcast-dlvr $\langle$CERTIFY, $\langle$P., v, s, _$\rangle$σ$\rangle$
from f+1 as P@$_\Sigma$@:

35 if v != view or s $\notin$ checkpoint.open_slots: return

36 CTBcast-bcast $\langle$COMMIT, P@$_\Sigma$@$\rangle$

38upon CTBcast-dlvr $\langle$COMMIT, P@$_\Sigma$@$\rangle$ from p as C:

39 state[p].commits[P<EMAIL_ADDRESS>= C

40 if dlvred f+1 COMMIT with a matching PREPARE:

41 trigger once Decide(P<EMAIL_ADDRESS>P<EMAIL_ADDRESS>
43# Checkpoints

44after having decided on all checkpoint.open_slots:

45 wait fo@\phantom{}r all decided requests to be applied to the App next_cp =
(App.Snapshot(), checkpoint.open_slots + 100) TBcast-bcast
<CERTIFY_CHECKPOINT, sign(next_cp)> upon TBcast-dlvr <CERTIFY_CHECKPOINT,
c$_\sigma$@$\rangle$ from f+1 as C@$_\Sigma$@:

46 MaybeCheckpoint(C@$_\Sigma$@)

48upon CTBcast-dlvr $\langle$CHECKPOINT, C@$_\Sigma$@$\rangle$ from p as CP:

49 state[p].checkpoint = CP

50 forget state[p].commits an@\phantom{}d prepares$\notin$@
C<EMAIL_ADDRESS>
51 MaybeCheckpoint(C@$_\Sigma$@)

53def MaybeCheckpoint(C@$_\Sigma$@):

54 if C@$_\Sigma$@ supersedes checkpoint:

55 checkpoint = C@$_\Sigma$@

56 App.BringUpToSpeed(checkpoint)

57 TBcast-bcast $\langle$CHECKPOINT, checkpoint$\rangle$

Algorithm 3: View Change

⬇

1upon suspicion of leader(view): ChangeView()

3def ChangeView():

4 for each $\langle$WILL_COMMIT, v@$|_{v==view}$@, s$\rangle$ bcast via
TBcast:

5 wait to have broadcast a matching COMMIT o@\phantom{}r CHECKPOINT CTBcast-
bcast <SEAL_VIEW,++\inview@$\rangle$

7upon CTBcast-dlvr $\langle$SEAL_VIEW, v$\rangle$ from p as SV:

8 state[p].seal_view = SV

9 state[p].view = v

10 send@$_{leader(v)}$@ $\langle$CRTFY_VC, v, sign((p,
state[p]\new_view))$\rangle$

12upon dlvr f+1 matching $\langle$CRTFY_VC, v@$|_{v==view}$@,
s@$_\sigma$@$\rangle$ about f+1 replicas as C:

13 if me != leader(view): return

14 CTBcast-bcast $\langle$NEW_VIEW, C$\rangle$

15 MaybeCheckpoint(highest checkpoint in C)

16 for s in checkpoint.open_slots:

17 CTB-bcast $\langle$PREPARE, v, s, MustPropose(s, C)$\rangle$

18 next_slot = checkpoint.open_slots.last + 1

20upon CTBcast-dlvr $\langle$NEW_VIEW, certificates$\rangle$ from p as NV:

21 state[p].new_view = NV

22 while view != NV.view + 1: ChangeView()

24def MustPropose(slot, certificates):

25 if slot $\rangle$ max open slot i@\phantom{}n certificates: return Any
return latest committed req fo\phantom{}r slot i\phantom{}n certificates
or$\bot$@

Algorithm 4: CTBcast Summaries

⬇

1after CTBcast-dlvr the message with id % tail == 0 from p:

2 send@$_p$@ $\langle$CERTIFY_SUMMARY, sign((p, id, state[p]))$\rangle$

4every tail invocations of CTBcast-bcast:

5 block calls to CTBcast-bcast

7upon dlvr $\langle$CERTIFY_SUMMARY, (me, id, _)σ$\rangle$ from f+1 as
S@$_\Sigma$@:

8 TBcast-bcast $\langle$SUMMARY, S@$_\Sigma$@$\rangle$

9 unblock calls to CTBcast-bcast@\label{alg:cons:summary-unblock}upon TBcast-
dlvr <SUMMARY, (p, id, history)$_\Sigma$@$\rangle$:

10 when a gap is detected i@\phantom{}n the dlvry of CTBcast from p: if the
latest message dlvred fro\phantom{}m p is lower than id: dlvr i\phantom{}n
order p’s missed CTBcast messages i\phantom{}n history without running the
Byzantine checks(Alg.~\ref{alg:consensus-byz-checks})continu\phantom{}e
dlvring p’s CTBcast messages afte\phantom{}r id

Algorithm 5: CTBcast’s Byzantine Checks

⬇

1def valid $\langle$PREPARE, v, s, r$\rangle$ from p:

2 state[p].view == v and leader(v) == p and

3 s in state[p].checkpoint.open_slots and

4 p never prepared slot s before i@\phantom{}n v and (v == 0 or
(state[p].new_view !=$\bot$@ and

5 r == MustPropose(s, state[p].new_view)))

7def valid $\langle$COMMIT, P@$_\Sigma$@$\rangle$ from p as C:

8 P<EMAIL_ADDRESS>in state[p].checkpoint.open_slots and

9 P<EMAIL_ADDRESS>== state[p].view and

10 state[p].commits[P<EMAIL_ADDRESS>!= C

12def valid $\langle$CHECKPOINT, C@$_\Sigma$@$\rangle$ from p:

13 C@$_\Sigma$@ supersedes state[p].checkpoint

15def valid $\langle$SEAL_VIEW, v$\rangle$ from p:

16 state[p].view $\langle$ v

18def valid $\langle$NEW_VIEW, certificates$\rangle$ from p:

19 leader(state[p].view) == p and

20 it is p’s first non-CHECKPOINT message i@\phantom{}n this view and each
certificate is about a different replica and each certificate is
s$\phantom{}$@igned by f+1 different replicas and

21 each certificate is about view state[p].view

This section gives the pseudocode of uBFT’s consensus alongside a correctness
argument. Algorithm 2 describes uBFT’s operation under a stable leader.
Algorithm 3 describes view changes. Algorithm 4 describes how summaries let
uBFT handle the gaps caused by CTBcast’s tail-validity. Finally, Algorithm 5
gives the explicit requirements for messages to pass CTBcast’s Byzantine
checks.

###  B.1. Validity

###### Lemma B.1.

For a fixed slot $s$, with no faulty processes, if some process $p$ delivers
and accepts $\langle\texttt{PREPARE},v,s,r\rangle$ in Algorithm 2 at line 18,
then $r$ must have been proposed by some correct process.

###### Proof Sketch.

We will prove the lemma by induction on the view $v$ in which $p$ accepts the
PREPARE message. The base case is $v=0$. Process $p$ must have delivered a
PREPARE message for $r$ from the leader $\ell_{0}$ of view $0$. Since
$\ell_{0}$ is correct, it only sends PREPARE messages for values that are in
its input, or for values that are part of a valid view change certificate from
the previous view. Since there is no previous view in view $0$, it must be
that $r$ was $\ell_{0}$’s input.

Now, for the induction step, assume that the lemma is true up to view $v$, and
examine the case in which $p$ accepts $\langle\texttt{PREPARE},v+1,s,r\rangle$
in view $v+1$. All processes are assumed to be correct, so the PREPARE message
must have been sent by $\ell_{v+1}$, the leader of view $v+1$. Correct
processes only send one PREPARE message per slot per view, so $\ell_{v+1}$
must have sent $\langle\texttt{PREPARE},v+1,s,r\rangle$ either as a new
proposal, or during the view change from $v$ to $v+1$, in Algorithm 3 at line
17. In the first case, $r$ is by definition proposed by a correct process as
part of $\ell_{v+1}$’s input. In the second case, $r$ must be a valid value
(i.e., be returned by MustPropose), given the view change certificates for
view $v$. There are two cases in which $r$ is such a valid value: (1) one of
the certificates contains a COMMIT messages for $r$ in $v^{\prime}$ with
$v^{\prime}\leq$ $v$, or (2) none of the certificates contain a COMMIT message
for $r$, and $r$ is the input of $\ell_{v+1}$. In case (1), a quorum of
processes must have delivered and accepted
$\langle\texttt{PREPARE},v^{\prime},s,r\rangle$ messages in view $v^{\prime}$
with $v^{\prime}\leq v$ and thus, by induction, $r$ must have been proposed by
some correct process. In case (2), $r$ is also proposed by a correct process.
This concludes the induction step and the proof. ∎

###### Theorem B.2 (Weak Validity).

For a fixed slot $s$, with no faulty processes, if some process $p$ decides
value $r$ in $s$, then $r$ must have been proposed by some correct process.

###### Proof Sketch.

Process $p$ may decide $r$ either at (1) line 31 (fast path), or (2) at line
41 (slow path) of Algorithm 2. Let $v$ be the view in which $p$ decides $r$.
In case (1), $p$ must have delivered and accepted a
$\langle\texttt{PREPARE},v,s,r\rangle$ in view $v$, so by Lemma B.1, $r$ must
have been proposed by some correct process. In case (2), $p$ must have
received valid COMMIT messages for $r$ from a quorum. Thus, a quorum of
processes must have delivered and accepted a PREPARE message for $r$, so by
Lemma B.1, $r$ must have been proposed by some correct process. ∎

###  B.2. Agreement

###### Observation 3.

For a fixed slot $s$ and view $v$, two correct processes never deliver and
accept conflicting PREPARE messages.

###### Proof Sketch.

Correct processes deliver and accept PREPARE messages only when coming from
the leader. Furthermore, they deliver and accept at most one PREPARE message
per view per slot. Thus, by the Agreement property of CTBcast, if two correct
processes deliver and accept PREPARE messages in the same view, then those
messages are for the same value and thus do not conflict. ∎

###### Corollary B.3.

For a fixed slot $s$ and view $v$, two processes never broadcast conflicting
valid COMMIT messages.

###### Proof Sketch.

Assume towards a contradiction that two processes $q$ and $p$ broadcast
conflicting valid COMMIT messages. Given that each valid COMMIT message is
made of a quorum of valid CERTIFY messages, $p$ and $q$ must have delivered
two quorums of valid CERTIFY messages about different PREPARE messages. By
definition, each quorum must contain one correct process. Moreover, a correct
process only broadcasts a CERTIFY message about the PREPARE message it
delivered. Thus, two correct processes delivered different PREPARE messages
for the same slot in the same view. This contradicts Observation 3. ∎

###### Corollary B.4.

For a fixed slot $s$, the view change certificates corresponding to two
processes cannot have conflicting COMMIT messages from the same view.

###### Proof Sketch.

Assume not. Then there exist processes $p_{1}$ and $p_{2}$ such that their
view change certificates at the end of view $v$ are conflicting: they contain
different COMMIT messages for values $r_{1}$ and $r_{2}$, respectively, from
the same view. Since each certificate contains an approval from a quorum, each
certificate must have been approved by at least one correct process. Thus, a
correct process must have received a COMMIT from $p_{1}$ for $r_{1}$ and, in
the same view, a correct process (not necessarily the same) must have received
a COMMIT from $p_{2}$ for $r_{2}$. By the Integrity property of CTBcast, this
implies that $p_{1}$ and $p_{2}$ must have sent conflicting commits for the
same slot and view, which is impossible by Corollary B.3. ∎

###### Lemma B.5.

For a fixed slot $s$ and view $v$, if a quorum broadcasts COMMIT messages for
the same value $r$, then no correct process accepts a PREPARE message for any
other value $r^{\prime}\neq r$ in any view $v^{\prime}\geq v$.

###### Proof Sketch.

We proceed by induction on $v^{\prime}$. The base case is $v^{\prime}=v$.
Since a quorum broadcasts COMMIT messages for $r$ in view $v$, at least one
correct process $p$ must have broadcast a COMMIT for $r$. Thus, some correct
process must have delivered and accepted a PREPARE message for $r$. Thus, by
Observation 3, no correct process may accept a PREPARE for a different value
$r^{\prime}\neq r$ in the same view.

Now, for the induction step, assume the lemma is true up to view $v^{\prime}$,
and assume that in view $v^{\prime}+1$, some correct process $p$ accepts a
PREPARE message for some other value $r^{\prime}\neq r$. For this to happen,
$r^{\prime}$ must be a valid value according to the view change certificates
provided by the leader $\ell_{v^{\prime}+1}$ of view $v^{\prime}+1$. Thus, at
least one process $q$ must have sent a COMMIT message $C$ for $r^{\prime}$ in
a view $v^{\prime\prime}\leq v^{\prime}$. Furthermore, $C$ must have been
accepted by at least one correct process $w$, in order for $q$’s state to have
been certified by a quorum. In order for $w$ to accept $C$, $C$’s
corresponding PREPARE message must have been certified, and thus accepted, by
at least one correct process in view $v^{\prime\prime}$. This contradicts our
induction hypothesis. So it is impossible for any correct process to accept a
PREPARE message for $r^{\prime}$ in view $v^{\prime}+1$. This completes the
induction step and the proof. ∎

###### Theorem B.6 (Agreement).

For a given slot $s$, correct processes cannot decide different values.

###### Proof Sketch.

Assume by contradiction that there exist two correct processes $p_{1}$ and
$p_{2}$, such that $p_{1}$ decides $r_{1}$ in view $v_{1}$ and $p_{2}$ decides
$r_{2}\neq r_{1}$ in view $v_{2}$. Assume further wlog that $v_{1}\leq v_{2}$.
We consider four cases, based on whether $p_{1}$ and $p_{2}$ decide on the
fast path or the slow path.

#### Case 1: Fast-fast.

Both $p_{1}$ and $p_{2}$ decide their respective values on the fast path. If
$v_{1}=v_{2}$, then $p_{1}$ and $p_{2}$ must have accepted conflicting
PREPAREs in the same view, which is impossible by Observation 3. Otherwise, if
$v_{1}<v_{2}$, then at least $f{+}1$ correct processes (a quorum) must have
broadcast COMMIT messages for $r_{1}$ before sealing view $v_{1}$. Thus, by
Lemma B.5, no correct process can accept a PREPARE for $r_{2}$ in $v_{2}$, so
$p_{2}$ cannot decide $r_{2}$ on the fast path in $v_{2}$.

#### Case 2: Fast-slow.

$p_{1}$ decides on the fast path and $p_{2}$ decides on the slow path. Then,
$p_{1}$ must have accepted a PREPARE for $r_{1}$ in view $v_{1}$ (call this
Fact 1). Moreover, $p_{2}$ must have accepted COMMIT messages for $r_{2}$ from
a quorum. This implies that a quorum broadcast COMMIT messages for $r_{2}$ in
some view $v_{2}^{\prime}\leq v_{2}$ (call this Fact 2). If
$v_{2}^{\prime}\leq v_{1}$, then we reach a contradiction with Fact 1 by Lemma
B.5. If $v_{2}^{\prime}>v_{1}$, then a quorum of correct processes must have
broadcast COMMIT messages for $r_{1}$ before sealing $v_{1}$; thus, by Lemma
B.5, we reach a contradiction with Fact 2, since no correct process could have
accepted a PREPARE for $r_{2}$ in $v_{2}$.

#### Case 3: Slow-fast.

This case is symmetric with Case 2 above.

#### Case 4: Slow-slow.

If both $p_{1}$ and $p_{2}$ decide on the slow path, then both processes must
have accepted COMMIT messages from a quorum. Let $v_{1}^{\prime}$ and
$v_{2}^{\prime}$ be the views in which the COMMIT messages accepted by $p_{1}$
and $p_{2}$, respectively, were sent. Assume wlog that $v_{1}^{\prime}\leq
v_{2}^{\prime}$. Then, by Lemma B.5, no correct process could have accepted a
PREPARE for $r_{2}$ in view $v_{2}$. Thus, no correct process could have sent
a COMMIT message for $r_{2}$ in $v_{2}$, and thus it is impossible for a
quorum to have sent COMMIT messages for for $r_{2}$ in $v_{2}$.

We have reached a contradiction in all four cases. This completes the proof of
the theorem. ∎

###  B.3. Liveness

In this section, we provide informal arguments for the liveness of our
protocol. We assume that the system is eventually synchronous and that correct
processes propose values infinitely often. Intuitively, liveness is ensured by
three mechanisms: (1) the view change mechanism, (2) checkpoints and (3)
CTBcast summaries. First, we assume that CTBcast messages are not dropped and
explain why liveness is ensured by the first two mechanisms. Then, we complete
our explanation with the way CTBcast summaries help overcome the problem of
dropped messages.

The view change mechanism ensures that at least one correct process is able to
decide forever. Assume towards a contradiction that all correct processes stop
deciding. Then, as long as they do not make progress, correct processes will
change view thanks to the view change protocol in Algorithm 3. Eventually,
after the global stabilization time (GST), all correct processes are
guaranteed to (1) reach a view $v$ in which the leader is correct, and (2)
communicate with each other in a timely manner. Thus, given that the timely
collaboration of $f{+}1$ processes is enough for the common path described in
Algorithm 2 to be live, the correct replicas decide, hence a contradiction.

However, having a single correct process deciding infinitely often is not
enough for the overall system to make progress as clients need to obtain a
response from $f{+}1$ processes. The checkpoint mechanism guarantees that, if
a correct process $p$ decides on slots infinitely often, then all correct
processes also make progress. This is because, in order to keep on making
progress (and thus maintain correct processes under its control), the leader
of a view is mandated to broadcast a CHECKPOINT message periodically. This
message is then re-broadcast by the potentially single correct process in the
view and, after GST, delivered by all correct processes. Because checkpoints
are transferable, when another correct process receives a checkpoint, it is
able to decide on the slots contained in the checkpoint and bring its
application state up to speed with the latest decided requests.

Lastly, CTBcast summaries ensure that, if the system were to be reduced to
only $f{+}1$ correct processes, they would be able to continue making progress
in spite of CTBcast’s delivery gaps. The worst scenario is arguably the one in
which a correct process $p$ used to make progress with $f$ faulty processes
before being let down by them, and the other $f$ correct processes ending up
with a gap in their CTBcast delivery of $p$’s messages due to asynchrony. In
this case, Algorithm 4 ensures that $p$ will not risk creating a gap before
having obtained a summary to help overcoming it. Using this summary, $p$ can
let correct processes continue delivering its messages by convincing them that
they will not violate the safety of the protocol due to missed messages.
Moreover, $p$ will always obtain a new summary: either it will be helped by
Byzantine processes, or, after GST, it will get help from correct processes by
combining the previous summary with the last $t$ messages it broadcast.

## References

  * (1)
  * Abd-El-Malek et al. (2005) Michael Abd-El-Malek, Gregory R. Ganger, Garth R. Goodson, Michael K. Reiter, and Jay J. Wylie. 2005\.  Fault-Scalable Byzantine Fault-Tolerant Services.  _SIGOPS Oper. Syst. Rev._ 39, 5 (Oct 2005), 59–74.  https://doi.org/10.1145/1095809.1095817
  * Aguilera et al. (2019) Marcos K. Aguilera, Naama Ben-David, Rachid Guerraoui, Virendra Marathe, and Igor Zablotchi. 2019\.  The Impact of RDMA on Agreement. 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, 409–418.  https://doi.org/10.1145/3293611.3331601
  * Aguilera et al. (2020) Marcos K. Aguilera, Naama Ben-David, Rachid Guerraoui, Virendra J. Marathe, Athanasios Xygkis, and Igor Zablotchi. 2020.  Microsecond Consensus for Microsecond Applications. In _Proceedings of the 14th USENIX Conference on Operating Systems Design and Implementation_ _(OSDI ’20)_. USENIX Association, Berkeley, CA, USA, Article 34, 18 pages.  https://www.usenix.org/conference/osdi20/presentation/aguilera
  * Aguilera et al. (2022) Marcos K. Aguilera, Naama Ben-David, Rachid Guerraoui, Antoine Murat, Athanasios Xygkis, and Igor Zablotchi. 2022.  Source code for uBFT: Microsecond-scale BFT using Disaggregated Memory.  https://doi.org/10.5281/zenodo.7330354
  * Aguilera et al. (2021) Marcos K. Aguilera, Naama Ben-David, Rachid Guerraoui, Dalia Papuc, Athanasios Xygkis, and Igor Zablotchi. 2021.  Frugal Byzantine Computing. In _35th International Symposium on Distributed Computing (DISC ’21)_ _(Leibniz International Proceedings in Informatics (LIPIcs), Vol. 209)_ , Seth Gilbert (Ed.). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 3:1–3:19.  https://doi.org/10.4230/LIPIcs.DISC.2021.3
  * Aguilera and Walfish (2009) Marcos K. Aguilera and Michael Walfish. 2009.  No Time for Asynchrony. In _Proceedings of the 12th Conference on Hot Topics in Operating Systems_ (Monte Verità, Switzerland) _(HotOS ’09)_. USENIX Association, Berkeley, CA, USA, 3.  https://www.usenix.org/conference/hotos-xii/no-time-asynchrony
  * Aiyer et al. (2008) Amitanand S. Aiyer, Lorenzo Alvisi, Rida A. Bazzi, and Allen Clement. 2008.  Matrix Signatures: From MACs to Digital Signatures in Distributed Systems. In _Proceedings of the 22nd International Symposium on Distributed Computing_ (Arcachon, France) _(DISC ’08)_. Springer-Verlag, Berlin, Heidelberg, 16–31.  https://doi.org/10.1007/978-3-540-87779-0_2
  * Androulaki et al. (2018) 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.  https://doi.org/10.1145/3190508.3190538
  * Arzani et al. (2020) Behnaz Arzani, Selim Ciraci, Stefan Saroiu, Alec Wolman, Jack W. Stokes, Geoff Outhred, and Lechao Diwu. 2020.  PrivateEye: Scalable and Privacy-Preserving Compromise Detection in the Cloud. In _Proceedings of the 17th Usenix Conference on Networked Systems Design and Implementation_ (Santa Clara, CA, USA) _(NSDI ’20)_. USENIX Association, Berkeley, CA, USA, 797–816.  https://www.usenix.org/conference/nsdi20/presentation/arzani
  * Association (2020) InfiniBand Trade Association. 2020\.  InfiniBand Architecture, General Specifications, Memory Placement Extensions.  Retrieved November 11, 2022 from https://cw.infinibandta.org/document/dl/8594
  * Aublin et al. (2013) Pierre-Louis Aublin, Sonia Ben Mokhtar, and Vivien Quéma. 2013.  RBFT: Redundant Byzantine Fault Tolerance. In _Proceedings of the 2013 IEEE 33rd International Conference on Distributed Computing Systems_ _(ICDCS ’13)_. IEEE Computer Society, USA, 297–306.  https://doi.org/10.1109/ICDCS.2013.53
  * Bailleu et al. (2021) Maurice Bailleu, Dimitra Giantsidi, Vasilis Gavrielatos, Do Le Quoc, Vijay Nagarajan, and Pramod Bhatotia. 2021.  Avocado: A Secure In-Memory Distributed Storage System. In _2021 USENIX Annual Technical Conference (USENIX ATC ’21)_ (Virtual Event). USENIX Association, Berkeley, CA, USA, 65–79.  https://www.usenix.org/conference/atc21/presentation/bailleu
  * Barroso et al. (2017) Luiz Barroso, Mike Marty, David Patterson, and Parthasarathy Ranganathan. 2017.  Attack of the Killer Microseconds.  _Commun. ACM_ 60, 4 (Mar 2017), 48–54.  https://doi.org/10.1145/3015146
  * Beck and Kagan (2011) Motti Beck and Michael Kagan. 2011.  Performance Evaluation of the RDMA over Ethernet (RoCE) Standard in Enterprise Data Centers Infrastructure. In _Proceedings of the 3rd Workshop on Data Center - Converged and Virtual Ethernet Switching_ (San Francisco, CA, USA) _(DC-CaVES ’11)_. International Teletraffic Congress, San Francisco, CA, USA, 9–15.  https://dl.acm.org/doi/10.5555/2043535.2043537
  * Behl et al. (2017) Johannes Behl, Tobias Distler, and Rüdiger Kapitza. 2017\.  Hybrids on Steroids: SGX-Based High Performance BFT. In _Proceedings of the Twelfth European Conference on Computer Systems_ (Belgrade, Serbia) _(EuroSys ’17)_. Association for Computing Machinery, New York, NY, USA, 222–237.  https://doi.org/10.1145/3064176.3064213
  * Ben-David et al. (2022) Naama Ben-David, Benjamin Y. Chan, and Elaine Shi. 2022\.  Revisiting the Power of Non-Equivocation in Distributed Protocols. In _Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing_ (Salerno, Italy) _(PODC ’22)_. Association for Computing Machinery, New York, NY, USA, 450–459.  https://doi.org/10.1145/3519270.3538427
  * Ben-David and Nayak (2021) Naama Ben-David and Kartik Nayak. 2021.  Brief Announcement: Classifying Trusted Hardware via Unidirectional Communication. In _Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing_ (Virtual Event) _(PODC ’21)_. Association for Computing Machinery, New York, NY, USA, 191–194.  https://doi.org/10.1145/3465084.3467948
  * Bessani et al. (2014) Alysson Bessani, João Sousa, and Eduardo E. P. Alchieri. 2014\.  State Machine Replication for the Masses with BFT-SMART. In _Proceedings of the 2014 44th Annual IEEE/IFIP International Conference on Dependable Systems and Networks_ (Atlanta, GA, USA) _(DSN ’14)_. IEEE Computer Society, USA, 355–362.  https://doi.org/10.1109/DSN.2014.43
  * Boucher et al. (2018) Sol Boucher, Anuj Kalia, David G. Andersen, and Michael Kaminsky. 2018.  Putting the ”Micro” Back in Microservice. In _Proceedings of the 2018 USENIX Conference on Usenix Annual Technical Conference_ (Boston, MA, USA) _(USENIX ATC ’18)_. USENIX Association, Berkeley, CA, USA, 645–650.  https://www.usenix.org/conference/atc18/presentation/boucher
  * Buchman et al. (2018) Ethan Buchman, Jae Kwon, and Zarko Milosevic. 2018.  The latest gossip on BFT consensus.  https://doi.org/10.48550/ARXIV.1807.04938
  * Cachin et al. (2011) Christian Cachin, Rachid Guerraoui, and Lus Rodrigues. 2011\.  _Introduction to Reliable and Secure Distributed Programming_ (2nd ed.).  Springer Publishing Company, New York, NY, USA.  https://doi.org/10.1007/978-3-642-15260-3
  * Cai et al. (2018) Qingchao Cai, Wentian Guo, Hao Zhang, Divyakant Agrawal, Gang Chen, Beng Chin Ooi, Kian-Lee Tan, Yong Meng Teo, and Sheng Wang. 2018.  Efficient Distributed Memory Management with RDMA and Caching.  _Proc. VLDB Endow._ 11, 11 (Jul 2018), 1604–1617.  https://doi.org/10.14778/3236187.3236209
  * Castro and Liskov (1999) Miguel Castro and Barbara Liskov. 1999.  Practical Byzantine Fault Tolerance. In _Proceedings of the Third Symposium on Operating Systems Design and Implementation_ (New Orleans, LA, USA) _(OSDI ’99)_. USENIX Association, Berkeley, CA, USA, 173–186.  https://www.usenix.org/legacy/publications/library/proceedings/osdi99/castro.html
  * Chun et al. (2007) Byung-Gon Chun, Petros Maniatis, Scott Shenker, and John Kubiatowicz. 2007.  Attested Append-Only Memory: Making Adversaries Stick to Their Word. In _Proceedings of Twenty-First ACM SIGOPS Symposium on Operating Systems Principles_ (Stevenson, WA, USA) _(SOSP ’07)_. Association for Computing Machinery, New York, NY, USA, 189–204.  https://doi.org/10.1145/1294261.1294280
  * Clement et al. (2012) Allen Clement, Flavio Junqueira, Aniket Kate, and Rodrigo Rodrigues. 2012.  On the (Limited) Power of Non-Equivocation. In _Proceedings of the 2012 ACM Symposium on Principles of Distributed Computing_ (Madeira, Portugal) _(PODC ’12)_. Association for Computing Machinery, New York, NY, USA, 301–308.  https://doi.org/10.1145/2332432.2332490
  * Collet (2022) Yann Collet. 2022\.  xxHash: Extremely fast non-cryptographic hash algorithm.  https://github.com/Cyan4973/xxHash
  * Correia et al. (2004) Miguel Correia, Nuno Ferreira Neves, and Paulo Verissimo. 2004.  How to Tolerate Half Less One Byzantine Nodes in Practical Distributed Systems. In _Proceedings of the 23rd IEEE International Symposium on Reliable Distributed Systems_ (Florianpolis, Brazil) _(SRDS ’04)_. IEEE Computer Society, NW Washington, DC, USA, 174–183.  https://doi.org/10.1109/RELDIS.2004.1353018
  * Costan and Devadas (2016) Victor Costan and Srinivas Devadas. 2016.  Intel SGX Explained.  https://eprint.iacr.org/2016/086
  * Cui et al. (2021) Jinhua Cui, Jason Zhijingcheng Yu, Shweta Shinde, Prateek Saxena, and Zhiping Cai. 2021\.  SmashEx: Smashing SGX Enclaves Using Exceptions. In _Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security_ (Virtual Event) _(CCS ’21)_. Association for Computing Machinery, New York, NY, USA, 779–793.  https://doi.org/10.1145/3460120.3484821
  * Cutress (2019) Ian Cutress. 2019\.  CXL Specification 1.0 Released: New Industry High-Speed Interconnect From Intel.  Retrieved May 25, 2022 from https://www.anandtech.com/show/14068/cxl-specification-1-released-new-industry-high-speed-interconnect-from-intel
  * Danezis et al. (2022) 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.  https://doi.org/10.1145/3492321.3519594
  * Delporte-Gallet et al. (2004) Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui, Vassos Hadzilacos, Petr Kouznetsov, and Sam Toueg. 2004.  The Weakest Failure Detectors to Solve Certain Fundamental Problems in Distributed Computing. In _Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing_ (St. John’s, NL, Canada) _(PODC ’04)_. Association for Computing Machinery, New York, NY, USA, 338–346.  https://doi.org/10.1145/1011767.1011818
  * Dixit et al. (2022) Harish Dattatraya Dixit, Laura Boyle, Gautham Vunnam, Sneha Pendharkar, Matt Beadon, and Sriram Sankar. 2022.  Detecting silent data corruptions in the wild.  https://doi.org/10.48550/ARXIV.2203.08989
  * Dragojević et al. (2015) Aleksandar Dragojević, Dushyanth Narayanan, Edmund B. Nightingale, Matthew Renzelmann, Alex Shamis, Anirudh Badam, and Miguel Castro. 2015.  No Compromises: Distributed Transactions with Consistency, Availability, and Performance. In _Proceedings of the 25th Symposium on Operating Systems Principles_ (Monterey, CA, USA) _(SOSP ’15)_. Association for Computing Machinery, New York, NY, USA, 54–70.  https://doi.org/10.1145/2815400.2815425
  * Eyal et al. (2016) Ittay Eyal, Adem Efe Gencer, Emin Gün Sirer, and Robbert Van Renesse. 2016.  Bitcoin-NG: A Scalable Blockchain Protocol. In _Proceedings of the 13th Usenix Conference on Networked Systems Design and Implementation_ (Santa Clara, CA, USA) _(NSDI ’16)_. USENIX Association, Berkeley, CA, USA, 45–59.  https://www.usenix.org/conference/nsdi16/technical-sessions/presentation/eyal
  * Fei et al. (2021) Shufan Fei, Zheng Yan, Wenxiu Ding, and Haomeng Xie. 2021\.  Security Vulnerabilities of SGX and Countermeasures: A Survey.  _ACM Comput. Surv._ 54, 6, Article 126 (Jul 2021), 36 pages.  https://doi.org/10.1145/3456631
  * Gilad et al. (2017) Yossi Gilad, Rotem Hemo, Silvio Micali, Georgios Vlachos, and Nickolai Zeldovich. 2017.  Algorand: Scaling Byzantine Agreements for Cryptocurrencies. In _Proceedings of the 26th Symposium on Operating Systems Principles_ (Shanghai, China) _(SOSP ’17)_. Association for Computing Machinery, New York, NY, USA, 51–68.  https://doi.org/10.1145/3132747.3132757
  * Golan-Gueta et al. (2019) Guy Golan-Gueta, Ittai Abraham, Shelly Grossman, Dahlia Malkhi, Benny Pinkas, Michael K. Reiter, Dragos-Adrian Seredinschi, Orr Tamir, and Alin Tomescu. 2019.  SBFT: A Scalable and Decentralized Trust Infrastructure. In _49th Annual IEEE/IFIP International Conference on Dependable Systems and Networks_ (Portland, OR, USA) _(DSN ’19)_. IEEE Computer Society, USA, 568–580.  https://doi.org/10.1109/DSN.2019.00063
  * Gouk et al. (2022) Donghyun Gouk, Sangwon Lee, Miryeong Kwon, and Myoungsoo Jung. 2022.  Direct Access, High-Performance Memory Disaggregation with DirectCXL. In _2022 USENIX Annual Technical Conference (USENIX ATC ’22)_ (Carlsbad, CA, USA). USENIX Association, Berkeley, CA, USA, 287–294.  https://www.usenix.org/conference/atc22/presentation/gouk
  * Gromadzki and Michalski (2019) Tomasz Gromadzki and Jan Marian Michalski. 2019.  Persistent Memory Replication Over Traditional RDMA Part 1: Understanding Remote Persistent Memory.  Retrieved November 11, 2022 from https://www.intel.com/content/www/us/en/developer/articles/technical/persistent-memory-replication-over-traditional-rdma-part-1-understanding-remote-persistent.html
  * Guerraoui et al. (2022) Rachid Guerraoui, Antoine Murat, Javier Picorel, Athanasios Xygkis, Huabing Yan, and Pengfei Zuo. 2022\.  uKharon: A Membership Service for Microsecond Applications. In _2022 USENIX Annual Technical Conference (USENIX ATC ’22)_ (Carlsbad, CA, USA). USENIX Association, Berkeley, CA, USA, 101–120.  https://www.usenix.org/conference/atc22/presentation/guerraoui
  * Gunawi et al. (2018) Haryadi S. Gunawi, Riza O. Suminto, Russell Sears, Casey Golliher, Swaminathan Sundararaman, Xing Lin, Tim Emami, Weiguang Sheng, Nematollah Bidokhti, Caitie McCaffrey, Deepthi Srinivasan, Biswaranjan Panda, Andrew Baptist, Gary Grider, Parks M. Fields, Kevin Harms, Robert B. Ross, Andree Jacobson, Robert Ricci, Kirk Webb, Peter Alvaro, H. Birali Runesha, Mingzhe Hao, and Huaicheng Li. 2018\.  Fail-Slow at Scale: Evidence of Hardware Performance Faults in Large Production Systems.  _ACM Trans. Storage_ 14, 3, Article 23 (Oct 2018), 26 pages.  https://doi.org/10.1145/3242086
  * Gupta et al. (2016) Divya Gupta, Lucas Perronne, and Sara Bouchenak. 2016\.  BFT-Bench: A Framework to Evaluate BFT Protocols. In _Proceedings of the 7th ACM/SPEC on International Conference on Performance Engineering_ (Delft, The Netherlands) _(ICPE ’16)_. Association for Computing Machinery, New York, NY, USA, 109–112.  https://doi.org/10.1145/2851553.2858667
  * Hochschild et al. (2021) Peter H. Hochschild, Paul Turner, Jeffrey C. Mogul, Rama Govindaraju, Parthasarathy Ranganathan, David E. Culler, and Amin Vahdat. 2021\.  Cores That Don’t Count. In _Proceedings of the Workshop on Hot Topics in Operating Systems_ (Ann Arbor, MI, USA) _(HotOS ’21)_. Association for Computing Machinery, New York, NY, USA, 9–16.  https://doi.org/10.1145/3458336.3465297
  * Huang et al. (2017) Peng Huang, Chuanxiong Guo, Lidong Zhou, Jacob R. Lorch, Yingnong Dang, Murali Chintalapati, and Randolph Yao. 2017.  Gray Failure: The Achilles’ Heel of Cloud-Scale Systems. In _Proceedings of the 16th Workshop on Hot Topics in Operating Systems_ (Whistler, BC, Canada) _(HotOS ’17)_. Association for Computing Machinery, New York, NY, USA, 150–155.  https://doi.org/10.1145/3102980.3103005
  * Hunt et al. (2010) Patrick Hunt, Mahadev Konar, Flavio P. Junqueira, and Benjamin Reed. 2010.  ZooKeeper: Wait-Free Coordination for Internet-Scale Systems. In _Proceedings of the 2010 USENIX Conference on USENIX Annual Technical Conference_ (Boston, MA, USA) _(USENIX ATC ’10)_. USENIX Association, Berkeley, CA, USA, 11 pages.  https://www.usenix.org/conference/usenix-atc-10/zookeeper-wait-free-coordination-internet-scale-systems
  * Ibanez et al. (2021) Stephen Ibanez, Alex Mallery, Serhat Arslan, Theo Jepsen, Muhammad Shahbaz, Changhoon Kim, and Nick McKeown. 2021.  The nanoPU: A Nanosecond Network Stack for Datacenters. In _15th USENIX Symposium on Operating Systems Design and Implementation (OSDI ’21)_. USENIX Association, Virtual Event, 239–256.  https://www.usenix.org/conference/osdi21/presentation/ibanez
  * Interactive (2022) Danga Interactive. 2022\.  Memcached.  https://memcached.org/
  * Jin et al. (2002) Hai Jin, Rajkumar Buyya, and Toni Cortes. 2002.  An Introduction to the InfiniBand Architecture. In _High Performance Mass Storage and Parallel I/O: Technologies and Applications_ (1st ed.). John Wiley and Sons, Inc., Hoboken, NJ, USA, 616–632.  https://doi.org/10.1109/9780470544839
  * Kalia et al. (2014) Anuj Kalia, Michael Kaminsky, and David G. Andersen. 2014\.  Using RDMA Efficiently for Key-Value Services. In _Proceedings of the 2014 ACM Conference on SIGCOMM_ (Chicago, IL, USA) _(SIGCOMM ’14)_. Association for Computing Machinery, New York, NY, USA, 295–306.  https://doi.org/10.1145/2619239.2626299
  * Kapitza et al. (2012) Rüdiger Kapitza, Johannes Behl, Christian Cachin, Tobias Distler, Simon Kuhnle, Seyed Vahid Mohammadi, Wolfgang Schröder-Preikschat, and Klaus Stengel. 2012\.  CheapBFT: Resource-Efficient Byzantine Fault Tolerance. In _Proceedings of the 7th ACM European Conference on Computer Systems_ (Bern, Switzerland) _(EuroSys ’12)_. Association for Computing Machinery, New York, NY, USA, 295–308.  https://doi.org/10.1145/2168836.2168866
  * Kokoris-Kogias et al. (2016) 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, Berkeley, CA, USA, 279–296.  https://www.usenix.org/conference/usenixsecurity16/technical-sessions/presentation/kogias
  * Kotla et al. (2010) 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.  https://doi.org/10.1145/1658357.1658358
  * Lamport et al. (1982) Leslie Lamport, Robert Shostak, and Marshall Pease. 1982\.  The Byzantine Generals Problem.  _ACM Trans. Program. Lang. Syst._ 4, 3 (Jul 1982), 382–401.  https://doi.org/10.1145/357172.357176
  * Lee et al. (2021) Seung-seob Lee, Yanpeng Yu, Yupeng Tang, Anurag Khandelwal, Lin Zhong, and Abhishek Bhattacharjee. 2021\.  MIND: In-Network Memory Management for Disaggregated Data Centers. In _Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles_ (Virtual Event) _(SOSP ’21)_. Association for Computing Machinery, New York, NY, USA, 488–504.  https://doi.org/10.1145/3477132.3483561
  * Lee et al. (2019) Youngmoon Lee, Hasan Al Maruf, Mosharaf Chowdhury, Asaf Cidon, and Kang G. Shin. 2019.  Mitigating the Performance-Efficiency Tradeoff in Resilient Memory Disaggregation.  https://doi.org/10.48550/ARXIV.1910.09727
  * Leesatapornwongsa et al. (2016) Tanakorn Leesatapornwongsa, Jeffrey F. Lukman, Shan Lu, and Haryadi S. Gunawi. 2016.  TaxDC: A Taxonomy of Non-Deterministic Concurrency Bugs in Datacenter Distributed Systems. In _Proceedings of the Twenty-First International Conference on Architectural Support for Programming Languages and Operating Systems_ (Atlanta, GA, USA) _(ASPLOS ’16)_. Association for Computing Machinery, New York, NY, USA, 517–530.  https://doi.org/10.1145/2872362.2872374
  * Leners et al. (2011) Joshua B. Leners, Hao Wu, Wei-Lun Hung, Marcos K. Aguilera, and Michael Walfish. 2011.  Detecting Failures in Distributed Systems with the FALCON Spy Network. In _Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles_ (Cascais, Portugal) _(SOSP ’11)_. Association for Computing Machinery, New York, NY, USA, 279–294.  https://doi.org/10.1145/2043556.2043583
  * Levin et al. (2009) Dave Levin, John R. Douceur, Jacob R. Lorch, and Thomas Moscibroda. 2009.  TrInc: Small Trusted Hardware for Large Distributed Systems. In _Proceedings of the 6th USENIX Symposium on Networked Systems Design and Implementation_ (Boston, MA, USA) _(NSDI ’09)_. USENIX Association, Berkeley, CA, USA, 14 pages.  https://www.usenix.org/conference/nsdi-09/trinc-small-trusted-hardware-large-distributed-systems
  * Liu et al. (2019) Jian Liu, Wenting Li, Ghassan O. Karame, and N. Asokan. 2019\.  Scalable Byzantine Consensus via Hardware-Assisted Secret Sharing.  _IEEE Trans. Comput._ 68, 1 (Jan 2019), 139–151.  https://doi.org/10.1109/TC.2018.2860009
  * Lovecruft et al. (2022) Isis Agora Lovecruft, Henry De Valence, and Aumasson. 2022\.  ed25519-dalek: Fast and efficient Rust implementation of ed25519 key generation, signing, and verification in Rust.  https://github.com/dalek-cryptography/ed25519-dalek
  * Madsen and Debois (2020) Mads Frederik Madsen and Søren Debois. 2020.  On the Subject of Non-Equivocation: Defining Non-Equivocation in Synchronous Agreement Systems. In _Proceedings of the 39th Symposium on Principles of Distributed Computing_ (Virtual Event) _(PODC ’20)_. Association for Computing Machinery, New York, NY, USA, 159–168.  https://doi.org/10.1145/3382734.3405731
  * Mao et al. (2008) Yanhua Mao, Flavio P. Junqueira, and Keith Marzullo. 2008\.  Mencius: Building Efficient Replicated State Machines for WANs. In _Proceedings of the 8th USENIX Conference on Operating Systems Design and Implementation_ (San Diego, CA, USA) _(OSDI ’08)_. USENIX Association, Berkeley, CA, USA, 369–384.  https://www.usenix.org/conference/osdi-08/mencius-building-efficient-replicated-state-machines-wans
  * Martin and Alvisi (2006) Jean-Philippe Martin and Lorenzo Alvisi. 2006.  Fast Byzantine Consensus.  _IEEE Trans. Dependable Secur. Comput._ 3, 3 (Jul 2006), 202–215.  https://doi.org/10.1109/TDSC.2006.35
  * Messadi et al. (2022) Ines Messadi, Markus Horst Becker, Kai Bleeke, Leander Jehl, Sonia Ben Mokhtar, and Rüdiger Kapitza. 2022.  SplitBFT: Improving Byzantine Fault Tolerance Safety Using Trusted Compartments. In _Proceedings of the 23rd ACM/IFIP International Middleware Conference_ (Quebec, QC, Canada) _(Middleware ’22)_. Association for Computing Machinery, New York, NY, USA, 56–68.  https://doi.org/10.1145/3528535.3531516
  * Meza et al. (2015) Justin Meza, Qiang Wu, Sanjev Kumar, and Onur Mutlu. 2015\.  A Large-Scale Study of Flash Memory Failures in the Field. In _Proceedings of the 2015 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems_ (Portland, OR, USA) _(SIGMETRICS ’15)_. Association for Computing Machinery, New York, NY, USA, 177–190.  https://doi.org/10.1145/2745844.2745848
  * Meza et al. (2018) Justin Meza, Tianyin Xu, Kaushik Veeraraghavan, and Onur Mutlu. 2018\.  A Large Scale Study of Data Center Network Reliability. In _Proceedings of the Internet Measurement Conference 2018_ (Boston, MA, USA) _(IMC ’18)_. Association for Computing Machinery, New York, NY, USA, 393–407.  https://doi.org/10.1145/3278532.3278566
  * Miller et al. (2016) Andrew Miller, Yu Xia, Kyle Croman, Elaine Shi, and Dawn Song. 2016.  The Honey Badger of BFT Protocols. In _Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security_ (Vienna, Austria) _(CCS ’16)_. Association for Computing Machinery, New York, NY, USA, 31–42.  https://doi.org/10.1145/2976749.2978399
  * Mitchell et al. (2013) Christopher Mitchell, Yifeng Geng, and Jinyang Li. 2013\.  Using One-Sided RDMA Reads to Build a Fast, CPU-Efficient Key-Value Store. In _Proceedings of the 2013 USENIX Conference on Annual Technical Conference_ (San Jose, CA, USA) _(USENIX ATC ’13)_. USENIX Association, Berkeley, CA, USA, 103–114.  https://www.usenix.org/conference/atc13/technical-sessions/presentation/mitchell
  * Moraru et al. (2013) Iulian Moraru, David G. Andersen, and Michael Kaminsky. 2013\.  There is More Consensus in Egalitarian Parliaments. In _Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles_ (Farminton, PA, USA) _(SOSP ’13)_. Association for Computing Machinery, New York, NY, USA, 358–372.  https://doi.org/10.1145/2517349.2517350
  * Nakamoto (2008) Satoshi Nakamoto. 2008\.  Bitcoin: A Peer-to-Peer Electronic Cash System.  Retrieved October 28, 2022 from https://bitcoin.org/bitcoin.pdf
  * Narayanan et al. (2016) Iyswarya Narayanan, Di Wang, Myeongjae Jeon, Bikash Sharma, Laura Caulfield, Anand Sivasubramaniam, Ben Cutler, Jie Liu, Badriddine Khessib, and Kushagra Vaid. 2016\.  SSD Failures in Datacenters: What, When and Why?. In _Proceedings of the 2016 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Science_ (Antibes Juan-les-Pins, France) _(SIGMETRICS ’16)_. Association for Computing Machinery, New York, NY, USA, 407–408.  https://doi.org/10.1145/2896377.2901489
  * Newhuis (2022) Eric Newhuis. 2022\.  Liquibook: Open source order matching engine.  https://github.com/enewhuis/liquibook
  * O’Connor et al. (2022) Jack O’Connor, Jean-Philippe Aumasson, Samuel Neves, and Zooko Wilcox-O’Hearn. 2022\.  BLAKE3.  https://github.com/BLAKE3-team/BLAKE3
  * Oppenheimer et al. (2003) David Oppenheimer, Archana Ganapathi, and David A. Patterson. 2003\.  Why Do Internet Services Fail, and What Can Be Done about It?. In _Proceedings of the 4th Conference on USENIX Symposium on Internet Technologies and Systems - Volume 4_ (Seattle, WA, USA) _(USITS ’03)_. USENIX Association, Berkeley, CA, USA, 15 pages.  https://www.usenix.org/conference/usits-03/why-do-internet-services-fail-and-what-can-be-done-about-it
  * Red Hat (2020) Red Hat. 2020\.  RHEL for Real Time Timestamping.  Retrieved May 25, 2022 from https://access.redhat.com/documentation/en-us/red_hat_enterprise_linux_for_real_time/7/html/reference_guide/chap-timestamping
  * Rothenberger et al. (2021) Benjamin Rothenberger, Konstantin Taranov, Adrian Perrig, and Torsten Hoefler. 2021.  ReDMArk: Bypassing RDMA Security Mechanisms. In _30th USENIX Security Symposium (USENIX Security ’21)_ (Virtual Event). USENIX Association, Berkeley, CA, USA, 4277–4292.  https://www.usenix.org/conference/usenixsecurity21/presentation/rothenberger
  * Rüsch et al. (2018) Signe Rüsch, Ines Messadi, and Rüdiger Kapitza. 2018\.  Towards Low-Latency Byzantine Agreement Protocols Using RDMA. In _2018 48th Annual IEEE/IFIP International Conference on Dependable Systems and Networks Workshops (DSN-W)_. IEEE Computer Society, Los Alamitos, CA, USA, 146–151.  https://doi.org/10.1109/DSN-W.2018.00054
  * Saltzer et al. (1984) J. H. Saltzer, D. P. Reed, and D. D. Clark. 1984.  End-to-End Arguments in System Design.  _ACM Trans. Comput. Syst._ 2, 4 (Nov 1984), 277–288.  https://doi.org/10.1145/357401.357402
  * Sanfilippo (2022) Salvatore Sanfilippo. 2022\.  Redis.  https://github.com/redis/redis
  * Schneider (2012) David Schneider. 2012\.  The microsecond market.  _IEEE Spectrum_ 49, 6 (2012), 66–81.  https://doi.org/10.1109/MSPEC.2012.6203974
  * Shahmirzadi et al. (2009) Omid Shahmirzadi, Sergio Mena, and Andre Schiper. 2009\.  Relaxed Atomic Broadcast: State-Machine Replication Using Bounded Memory. In _Proceedings of the 2009 28th IEEE International Symposium on Reliable Distributed Systems_ (Niagara Falls, NY, USA) _(SRDS ’09)_. IEEE Computer Society, NW Washington, DC, USA, 3–11.  https://doi.org/10.1109/SRDS.2009.25
  * Shieh et al. (2011) Alan Shieh, Srikanth Kandula, Albert Greenberg, Changhoon Kim, and Bikas Saha. 2011.  Sharing the Data Center Network. In _Proceedings of the 8th USENIX Conference on Networked Systems Design and Implementation_ (Boston, MA, USA) _(NSDI ’11)_. USENIX Association, Berkeley, CA, USA, 309–322.  https://www.usenix.org/conference/nsdi11/sharing-data-center-network
  * Taranov et al. (2020) Konstantin Taranov, Benjamin Rothenberger, Adrian Perrig, and Torsten Hoefler. 2020.  sRDMA: Efficient NIC-Based Authentication and Encryption for Remote Direct Memory Access. In _Proceedings of the 2020 USENIX Conference on Usenix Annual Technical Conference_ (Virtual Event) _(USENIX ATC ’20)_. USENIX Association, Berkeley, CA, USA, Article 47, 14 pages.  https://www.usenix.org/conference/atc20/presentation/taranov
  * Technologies (2015) Mellanox Technologies. 2015\.  RDMA Aware Networks Programming User Manual. Rev 1.7.  Retrieved May 25, 2022 from https://docs.nvidia.com/networking/spaces/viewspace.action?key=RDMAAwareProgrammingv17
  * Technologies (2022) Mellanox Technologies. 2022\.  VMA: Linux user space library for network socket acceleration based on RDMA compatible network adaptors.  https://github.com/Mellanox/libvma
  * Tsai et al. (2020) Shin-Yeh Tsai, Yizhou Shan, and Yiying Zhang. 2020\.  Disaggregating Persistent Memory and Controlling Them Remotely: An Exploration of Passive Disaggregated Key-Value Stores. In _Proceedings of the 2020 USENIX Conference on Usenix Annual Technical Conference_ (Virtual Event) _(USENIX ATC ’20)_. USENIX Association, Berkeley, CA, USA, Article 3, 16 pages.  https://www.usenix.org/conference/atc20/presentation/tsai
  * Veronese et al. (2013) Giuliana Santos Veronese, Miguel Correia, Alysson Neves Bessani, Lau Cheuk Lung, and Paulo Verissimo. 2013\.  Efficient Byzantine Fault-Tolerance.  _IEEE Trans. Comput._ 62, 1 (Jan 2013), 16–30.  https://doi.org/10.1109/TC.2011.221
  * Wang et al. (2022) Ruihong Wang, Jianguo Wang, Stratos Idreos, M. Tamer Özsu, and Walid G. Aref. 2022.  The Case for Distributed Shared-Memory Databases with RDMA-Enabled Memory Disaggregation.  https://doi.org/10.48550/ARXIV.2207.03027
  * Yang et al. (2019) Tian Yang, Robert Gifford, Andreas Haeberlen, and Linh Thi Xuan Phan. 2019.  The Synchronous Data Center. In _Proceedings of the Workshop on Hot Topics in Operating Systems_ (Bertinoro, Italy) _(HotOS ’19)_. Association for Computing Machinery, New York, NY, USA, 142–148.  https://doi.org/10.1145/3317550.3321442
  * Yin et al. (2003) Jian Yin, Jean-Philippe Martin, Arun Venkataramani, Lorenzo Alvisi, and Mike Dahlin. 2003\.  Separating Agreement from Execution for Byzantine Fault Tolerant Services. In _Proceedings of the Nineteenth ACM Symposium on Operating Systems Principles_ (Bolton Landing, NY, USA) _(SOSP ’03)_. Association for Computing Machinery, New York, NY, USA, 253–267.  https://doi.org/10.1145/945445.945470
  * Yin et al. (2019) 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.  https://doi.org/10.1145/3293611.3331591
  * Zhou et al. (2022) Yang Zhou, Hassan M. G. Wassel, Sihang Liu, Jiaqi Gao, James Mickens, Minlan Yu, Chris Kennelly, Paul Turner, David E. Culler, Henry M. Levy, and Amin Vahdat. 2022.  Carbink: Fault-Tolerant Far Memory. In _16th USENIX Symposium on Operating Systems Design and Implementation (OSDI ’22)_ (Carlsbad, CA, USA). USENIX Association, Berkeley, CA, USA, 55–71.  https://www.usenix.org/conference/osdi22/presentation/zhou-yang
  * Zhuo et al. (2014) Danyang Zhuo, Qiao Zhang, Dan R. K. Ports, Arvind Krishnamurthy, and Thomas Anderson. 2014.  Machine Fault Tolerance for Reliable Datacenter Systems. In _Proceedings of 5th Asia-Pacific Workshop on Systems_ (Beijing, China) _(APSys ’14)_. Association for Computing Machinery, New York, NY, USA, Article 3, 7 pages.  https://doi.org/10.1145/2637166.2637235