11institutetext:  Computer Science and Technology, Nanjing University, China
11email<EMAIL_ADDRESS>
22institutetext: State Key Laboratory for Novel Software Technology, Nanjing
University, China 22email: {hfwei<EMAIL_ADDRESS>
33institutetext: Software Institute, Nanjing University, China
44institutetext: Tencent Inc., China
44email: {blueseali<EMAIL_ADDRESS>
# Byz-GentleRain: An Efficient Byzantine-tolerant Causal Consistency Protocol

Kaile Huang 11 Hengfeng Wei Corresponding Author2233 Yu Huang 22 Haixiang Li
44 Anqun Pan 44

###### Abstract

Causal consistency is a widely used weak consistency model that allows high
availability despite network partitions. There are plenty of research
prototypes and industrial deployments of causally consistent distributed
systems. However, as far as we know, none of them consider Byzantine faults,
except Byz-RCM proposed by Tseng et al. Byz-RCM achieves causal consistency in
the client-server model with $3f+1$ servers where up to $f$ servers may suffer
Byzantine faults, but assumes that clients are non-Byzantine. In this work, we
present Byz-Gentlerain, the first causal consistency protocol which tolerates
up to $f$ Byzantine servers among $3f+1$ servers in each partition and any
number of Byzantine clients. Byz-GentleRain is inspired by the stabilization
mechanism of GentleRain for causal consistency. To prevent causal violations
due to Byzantine faults, Byz-GentleRain relies on PBFT to reach agreement on a
sequence of global stable times and updates among servers, and only updates
with timestamps less than or equal to such common global stable times are
visible to clients. We prove that Byz-GentleRain achieves Byz-CC, the causal
consistency variant in the presence of Byzantine faults. We evaluate Byz-
GentleRain on Aliyun. The preliminary results show that Byz-GentleRain is
efficient on typical workloads.

###### Keywords:

Causal consistency Byzantine faults PBFT GentleRain Byz-GentleRain.

##  1 Introduction

For high availability and low latency even under network partitions,
distributed systems often partition and replicate data among multiple nodes
[7]. Due to the CAP theorem [6] many distributed systems choose to sacrifice
strong consistency and to implement weak ones.

Causal consistency [1] is one of the most widely used consistency model in
distributed systems. There are several variants of causal consistency in the
literature [1, 18, 4, 11]. They all guarantee that _an update does not become
visible until all its causality are visible._ We informally explain it in the
“Lost-Ring” example [13]. Alice first posts that she has lost her ring. After
a while, she posts that she has found it. Bob sees Alice’s two posts, and
comments that “Glad to hear it”. We say that there is a _read-from_ dependency
from Alice’s second post to Bob’s get operation, and a _session_ dependency
from Bob’s get operation to his own comment. By _transitivity_ , Bob’s comment
causally depend on Alice’s second post. Thus, when Carol, a friend of Alice
and Bob, sees Bob’s comment, she should also see Alice’s second post. If she
saw only Alice’s first post, she would mistakenly think that Bob is glad to
hear that Alice has lost her ring.

There are plenty of research prototypes and industrial deployments of causally
consistent distributed systems (e.g., COPS [16], Eiger [17], GentleRain [9],
Cure [2], MongoDB [20], and Byz-RCM [19]). GentleRain uses a stabilization
mechanism to make updates visible while respecting causal consistency. It
timestamps all updates with the physical clock value of the server where they
originate. Each server $\mathit{s}$ periodically computes a global stable time
${\sf gst}$, which is a lower bound on the physical clocks of all servers.
This ensures that no updates with timestamps $\leq{\sf gst}$ will be
generated. Thus, it is safe to make the updates with timestamps $\leq{\sf
gst}$ at $\mathit{s}$ visible to clients. A get operation with dependency time
$\mathit{dt}$ issued to $\mathit{s}$ will wait until ${\sf
gst}\geq\mathit{dt}$ and then obtain the latest version before ${\sf gst}$.

However, none of these causal consistency protocols/systems consider Byzantine
faults, except Byz-RCM (Byzantine Resilient Causal Memory) in [19]. Byz-RCM
achieves causal consistency in the client-server model with $3f+1$ servers
where up to $f$ servers may suffer Byzantine faults, and any number of clients
may crash. Byz-RCM has also been shown optimal in terms of failure resilience.
However, Byz-RCM did not tolerate Byzantine clients, and thus it could rely on
clients’ requests to identify bogus requests from Byzantine servers [19].

In this work, we present Byz-GentleRain, the first Byzantine-tolerant causal
consistency protocol which tolerates up to $f$ Byzantine servers among $3f+1$
servers in each partition _and_ any number of Byzantine clients. It uses PBFT
[8] to reach agreement among servers on a total order of client requests. The
major challenge Byz-GentleRain faces is to ensure that the agreement is
consistent with the causal order. To this end, Byz-GentleRain should prevent
causality violations caused by Byzantine clients or servers: Byzantine clients
may violate the session order by fooling some servers that a request happened
before another that was issued earlier. Byzantine servers may forge causal
dependencies by attaching arbitrary metadata for causality tracking to the
forward messages. To migrate the potential damages of Byzantine servers, we
let clients assign totally ordered timestamps to updates in Byz-GentleRain.
Utilizing the digital signatures mechanism, Byzantine servers cannot forge
causal dependencies.

Figure 1: Why the servers in Byz-GentleRain need to synchronize global stable
times.

To preserve causality, Byz-GentleRain uses the stabilization mechanism of
GentleRain. As explained above, the timestamps in Byz-GentleRain are generated
by clients. However, it is unrealistic to compute a lower bound on physical
clock values of an arbitrary number of clients. Therefore, each server
$\mathit{s}$ in Byz-GentleRain maintains and periodically computes a global
stable time ${\sf gst}$ which is a lower bound on physical clock values of the
clients it is aware of. In the following, we argue that simply refusing any
updates with timestamps $\leq{\sf gst}$ on each server as GentleRain does may
lead to causality violations. Consider a system of four servers which are
replicas all maintaining a single key $\mathit{k}$, as shown in Figure 1. Due
to asynchrony, these four servers may have different values of ${\sf gst}$.
Without loss of generality, we assume that ${\sf gst}_{1}<{\sf gst}_{2}={\sf
gst}_{3}<{\sf gst}_{4}$, as indicated by vertical lines. Now suppose that a
new update $\mathit{u}:\mathit{k}\leftarrow 5$ with timestamp between ${\sf
gst}_{3}$ and ${\sf gst}_{4}$ arrives, and we want to install it on $\geq 3$
servers, using quorum mechanism. In this scenario, if each server refuses any
updates with timestamps smaller than or equal to its ${\sf gst}$, the update
$\mathit{u}$ can only be accepted by the first 3 servers, indicated by dashed
boxes. Suppose that server 3 is a Byzantine server, which may expose or hide
the update $\mathit{u}$ as it will. Consequently, later read operations which
read from $\geq 3$ servers may or may not see this update $\mathit{u}$. That
is, the Byzantine server $3$ may cause causality violations.

To cope with this problem, we need to synchronize the global stable times of
servers. When a server periodically computes its ${\sf gst}$, it checks
whether no larger global stable time has been or is being synchronized. If so,
the server will try to synchronize its ${\sf gst}$ among all servers, by
running PBFT independently in each partition. For each partition, the PBFT
leader is also responsible for collecting updates with timestamps $\leq{\sf
gst}$ from $2f+1$ servers, and synchronizing them on all servers. Once
successfully synchronized, a global stable time becomes a _common_ global
stable time, denoted ${\sf cgst}$, and in each partition the updates with
timestamps $\leq{\sf cgst}$ on all correct servers are the same. Therefore,
each server can safely refuse any updates with timestamps smaller than or
equal to its ${\sf cgst}$.

Still, the classic PBFT is insufficient to guarantee causality, since a
Byzantine leader of each partition may propose an arbitrary set of updates. To
avoid this, in Byz-GentleRain the PBFT leader will also include the sets of
updates it collects from $2f+1$ servers in its propose message. A server will
reject the propose message if it finds the contents of this message have been
manipulated by checking hash and signatures.

Thus, we make the following contributions:

  * •

We define Byzantine Causal Consistency (Byz-CC), which is a causal consistency
variant in the presence of Byzantine faults (Section 3).

  * •

We present Byz-GentleRain, the first Byzantine-tolerant causal consistency
protocol. It tolerates up to $f$ Byzantine servers among $3f+1$ ones and any
number of Byzantine clients (Section 4). All reads and updates complete in one
round-trip.

  * •

We evaluate Byz-GentleRain on Aliyun. The preliminary results show that Byz-
GentleRain is efficient on typical workloads (Section 5).

Section 2 describes the system model and failure model. Section 6 discusses
related work. Section 7 concludes the paper. The proofs can be found in
Appendix 0.A.

##  2 Model

Table 1: Notations. Notations | Meaning
---|---
$D$ | number of data centers
$P$ | number of partitions
$\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{d}}}$ | the replica of partition $\mathit{p}$ in data center $\mathit{d}$
$\textsc{partition}(\mathit{k})$ | the partition that holds key $\mathit{k}$
$\textsc{replicas}(\mathit{p})$ | the set of replicas of partition $\mathit{p}$
$\textsc{datacenter}(\mathit{d})$ | the set of servers in data center $\mathit{d}$
$\mathcal{S}$ | the set of all $D\times P$ servers in the key-value store
${\sf clock}_{\mathit{c}}$ | clock at client $\mathit{c}$
${\sf dt}_{\mathit{c}}$ | dependency time at client $\mathit{c}$
${\sf cgst}_{\mathit{c}}$ | the maximum common global stable time known by client $\mathit{c}$
${\sf clock}^{\mathit{p}}_{\mathit{d}}$ | clock at replica $\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{d}}}$
${\sf lst}^{\mathit{p}}_{\mathit{d}}$ | local stable time at replica $\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{d}}}$
${\sf gst}^{\mathit{p}}_{\mathit{d}}$ | global stable time at replica $\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{d}}}$
${\sf cgst}^{\mathit{p}}_{\mathit{d}}$ | common global stable time at replica $\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{d}}}$
${\sf curr\\_cgst}^{\mathit{p}}_{\mathit{d}}$ | temporary common global stable time at replica $\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{d}}}$ during PBFT
${\sf VV}^{\mathit{p}}_{\mathit{d}}$ | version vector at replica $\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{d}}}$
${\sf LV}^{\mathit{p}}_{\mathit{d}}$ | local stable time vector at replica $\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{d}}}$
${\sf Key}$ | the set of keys, ranged over by $\mathit{k}$
${\sf Val}$ | the set of values, ranged over by $\mathit{v}$
${\sf VVal}$ | the set of versioned values, ranged over by $\mathit{vv}$
${\sf store}^{\mathit{p}}_{\mathit{d}}\subseteq{\sf VVal}$ | store maintained at replica $\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{d}}}$
Store | the union of stores at all replicas, that is, $\textsc{Store}\triangleq\bigcup_{1\leq i\leq D,1\leq j\leq P}{\sf store}^{\mathit{j}}_{\mathit{i}}$

We adopt the client/server architecture [15, 19], in which each client or
server has its unique id. Table 1 summarizes the notations used in this paper.

###  2.1 System Model

We consider a distributed multi-version key-value store, which maintains keys
in the set ${\sf Key}$ (ranged over by $\mathit{k}$) with values in the set
${\sf Val}$ (ranged over by $\mathit{v}$). Each value is associated with a
unique version, consisting of the timestamp of the update which creates this
version and the id of the client which issues this update. We denote by ${\sf
VVal}$ (ranged over by $\mathit{vv}$) the set of versioned values.

The distributed key-value store runs at $D$ data centers, each of which has a
full copy of data. In each data center, the full data is sharded into $P$
partitions. For a key $\mathit{k}\in{\sf Key}$, we use
$\textsc{partition}(\mathit{k})$ to denote the partition that holds
$\mathit{k}$. Each partition is replicated across $D$ data centers. For a
partition $\mathit{p}$, we use $\textsc{replicas}(\mathit{p})$ to denote the
set of replicas of $\mathit{p}$. For a data center $\mathit{d}$, we use
$\textsc{datacenter}(\mathit{d})$ to denote the set of servers in
$\mathit{d}$. We denote by
$\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{d}}}$ the replica of
partition $\mathit{p}$ at data center $\mathit{d}$. We denote by $\mathcal{S}$
the set of all $D\times P$ servers in the key-value store. For each individual
partition $\mathit{p}$, we call a set $Q$ of $2f+1$ replicas in
$\textsc{replicas}(\mathit{p})$ a quorum and denote it by ${\sf quorum}(Q)$.

For convenience, we model the key-value store at replica
$\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{d}}}$, denoted ${\sf
store}^{\mathit{p}}_{\mathit{d}}$, by a set of (unique) versioned values. That
is, ${\sf store}^{\mathit{p}}_{\mathit{d}}\subseteq{\sf VVal}$. We denote by
Store the union of stores at all replicas. That is,
$\textsc{Store}\triangleq\bigcup_{1\leq i\leq D,1\leq j\leq P}{\sf
store}^{\mathit{j}}_{\mathit{i}}$. The distributed key-value store offers two
operations to clients:

  * •

$\textsc{get}(\mathit{k})$. A get operation which returns the value of some
version of key $\mathit{k}$.

  * •

$\textsc{put}(\mathit{k},\mathit{v})$. A put operation which updates key
$\mathit{k}$ with value $\mathit{v}$. This creates a new version of
$\mathit{k}$.

We assume that each client or server is equipped with a physical clock, which
is monotonically increasing. Clocks at different clients are loosely
synchronized by a protocol such as NTP 111NTP: The Network Time Protocol.
http://www.ntp.org/.. The correctness of Byz-GentleRain does not depend on the
precision of clock synchronization, but large clock drifts may negatively
impact its performance.

###  2.2 Failure Model

Clients and servers are either correct or faulty. Correct clients and servers
obey their protocols, while faulty ones may exhibit Byzantine behaviors [8],
by deviating arbitrarily from their protocols.

We assume asynchronous point-to-point communication channels among clients and
servers. Messages may be delayed, duplicated, corrupted, or delivered out of
order. We do not assume known bounds on message delays. The communication
network is fully connected. We require that if the two ends of a channel are
both correct and the sender keeps retransmitting a message, then the message
can eventually be delivered.

We also assume the channels are authenticated. Clients and servers can sign
messages using digital signatures when needed. A message $\mathit{m}$ signed
by a client $\mathit{c}$ or a replica
$\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{d}}}$ is denoted by
$\langle\mathit{m}\rangle_{\mathit{c}}$ or
$\langle\mathit{m}\rangle^{\mathit{p}}_{\mathit{d}}$, respectively. We denote
by ${\sf valid}(\mathit{m})$ that $m$ is valid in signatures. We also use a
cryptographic hash function ${\sf hash}()$, which is assumed to be collision-
resistant: the probability of an adversary producing inputs $\mathit{m}$ and
$\mathit{m}^{\prime}$ such that ${\sf hash}(\mathit{m})={\sf
hash}(\mathit{m}^{\prime})$ is negligible [8, 5].

##  3 Byzantine Causal Consistency

Causal consistency variants in the literature [1, 18, 4, 11] are defined based
on the _happens-before_ relation among events [12]. However, they are not
applicable to systems that allows Byzantine nodes, particularly Byzantine
clients. We now adapt the happens-before relation in Byzantine-tolerant
systems, and define Byzantine Causal Consistency (Byz-CC) as follows. For two
events $e$ and $f$, we say that $e$ happens before $f$, denoted $e\leadsto f$,
if and only if one of the following three rules holds:

  * •

_Session-order_. Events $e$ and $f$ are two operation requests issued by the
same _correct_ client, and $e$ is issued before $f$. We denote it by
$e\xrightarrow{{\sf so}}f$. We do _not_ require session order among operations
issued by Byzantine clients.

  * •

_Read-from relation_. Event $e$ is a put request issued by some client and $f$
is a get request issued by a _correct_ client, and $f$ reads the value updated
by $e$. We denote it by $e\xrightarrow{{\sf rf}}f$. Since a get of Byzantine
clients may return an arbitrary value, we do _not_ require read-from relation
induced by it.

  * •

_Transitivity_. There is another operation request $g$ such that $e\leadsto g$
and $g\leadsto f$.

If $e\leadsto f$, we also say that $f$ causally depends on $e$ and $e$ is a
causal dependency of $f$. A version $\mathit{vv}$ of a key $\mathit{k}$
causally depends on version $\mathit{vv}^{\prime}$ of key
$\mathit{k}^{\prime}$, if the update of $\mathit{vv}$ causally depends on that
of $\mathit{vv}^{\prime}$. A key-value store satisfies Byz-CC if, when a
certain version of a key is visible to a client, then so are all of its causal
dependencies.

##  4 The Byz-GentleRain Protocol

As discussed in Section 1, it is the clients in Byz-GentleRain that are
responsible for generating totally ordered timestamps for updates.
Specifically, when a client issues an update, it assigns to the update a
timestamp consisting of its current clock and identifier.

As in GentleRain, we also distinguish between the updates that have been
received by a server and those that have been made visible to clients. Byz-
GentleRain guarantees that an update can be made visible to clients only if so
are all its causal dependencies. The pseudocode in Algorithms 1–3 dealing with
Byzantine faults is underlined.

###  4.1 Key Designs

In Byz-GentleRain, both clients and servers maintain a _common global stable
time_ ${\sf cgst}$. We denote the ${\sf cgst}$ at client $\mathit{c}$ by ${\sf
cgst}_{\mathit{c}}$ and that at replica
$\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{d}}}$ by ${\sf
cgst}^{\mathit{p}}_{\mathit{d}}$. We maintain the following invariants that
are key to the correctness of Byz-GentleRain:

  1. Inv (I):

Consider ${\sf cgst}_{\mathit{c}}$ at any time $\sigma$. All updates issued by
correct client $\mathit{c}$ after time $\sigma$ have a timestamp $>{\sf
cgst}_{\mathit{c}}$.

  2. Inv (II):

Consider ${\sf cgst}^{\mathit{p}}_{\mathit{d}}$ at any time $\sigma$. No
updates with timestamps $\leq{\sf cgst}^{\mathit{p}}_{\mathit{d}}$ will be
successfully executed at $>f$ correct replicas in
$\textsc{replicas}(\mathit{p})$ after time $\sigma$.

  3. Inv (III):

Consider a $\mathit{cgst}$ value. For any two correct replicas
$\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{d}}}$ and
$\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{i}}}$ (where $i\neq d$) of
partition $\mathit{p}$, if ${\sf
cgst}^{\mathit{p}}_{\mathit{d}}\geq\mathit{cgst}$ and ${\sf
cgst}^{\mathit{p}}_{\mathit{i}}\geq\mathit{cgst}$, then the updates with
timestamps $\leq\mathit{cgst}$ in ${\sf store}^{\mathit{p}}_{\mathit{d}}$ and
${\sf store}^{\mathit{p}}_{\mathit{i}}$ are the same.

Byz-GentleRain further enforces the following rules for reads and updates:

  1. Rule (I):

For a correct replica
$\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{d}}}$, any updates with
timestamps $>{\sf cgst}^{\mathit{p}}_{\mathit{d}}$ in ${\sf
store}^{\mathit{p}}_{\mathit{d}}$ are invisible to any clients.

  2. Rule (II):

Any correct replica $\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{d}}}$
will reject any updates with timestamps $\leq{\sf
cgst}^{\mathit{p}}_{\mathit{d}}$.

  3. Rule (III):

For a read operation with timestamp $\mathit{ts}$ issued by client
$\mathit{c}$, any correct replica
$\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{d}}}$ that receives this
operation must wait until ${\sf
cgst}^{\mathit{p}}_{\mathit{d}}\geq\mathit{ts}$ before it returns a value to
client $\mathit{c}$.

In the following sections, we explain how these invariants and rules are
implemented and why they are important to the correctness.

###  4.2 Client Operations

Algorithm 1 Operations at client $\mathit{c}$

1:procedure get($\mathit{k}$)

2: var $\mathit{ts}\leftarrow\max\\{{\sf dt},{\sf cgst}\\}$

3: var $\mathit{p}\leftarrow\textsc{partition}(\mathit{k})$

4: ${\bf send}\;\textsc{{get\\_req}}(\mathit{k},\mathit{ts})\;{\bf
to}\;\textsc{{replicas}}(\mathit{p})$ l

5: wait receive
$\\{\langle\textsc{{get\\_ack}}(\mathit{v}_{i},\mathit{cgst}_{i})\rangle^{\mathit{p}}_{i}\mid\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{i}}}\in
Q\\}=M$ for a quorum $Q$

6: ${\sf cgst}\leftarrow\max\\{{\sf
cgst},\min\limits_{\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{i}}}\in
Q}\mathit{cgst}_{i}\\}$

7: $\mathit{v}\leftarrow$ the majority $\mathit{v}_{i}$ in $M$

8: return $\mathit{v}$

9:

10:procedure put($\mathit{k},\mathit{v}$)

11: var $p\leftarrow\textsc{partition}(\mathit{k})$

12: wait ${\sf clock}>{\sf cgst}$

13: ${\bf send}\;\langle\textsc{{put\\_req}}(\langle\mathit{k},\mathit{v},{\sf
clock},\mathit{c}\rangle_{\mathit{c}})\rangle_{\mathit{c}}\;{\bf
to}\;\textsc{{replicas}}(\mathit{p})$

14: wait receive
$\\{\langle\textsc{{put\\_ack}}(\mathit{cgst}_{i})\rangle^{\mathit{p}}_{i}\mid\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{i}}}\in
Q\\}=M$ for a quorum $Q$

15: ${\sf cgst}\leftarrow\max\\{{\sf
cgst},\min\limits_{\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{i}}}\in
Q}\mathit{cgst}_{i}\\}$

16: ${\sf dt}\leftarrow{\sf clock}$

17: return ok

To capture the session order, each client maintains a dependency time ${\sf
dt}$, which is the clock value of its last put operation. When a client
$\mathit{c}$ issues a get operation on key $\mathit{k}$, it first takes as
$\mathit{ts}$ the minimum of its dependency time ${\sf dt}_{\mathit{c}}$ and
common global stable time ${\sf cgst}_{\mathit{c}}$ (line 1:2). Then it sends
a get_req request with $\mathit{ts}$ to $\textsc{replicas}(\mathit{p})$ (line
1:4), where $\mathit{p}$ is the partition holding $\mathit{k}$ (line 1:3).
Next, the client waits to receive a set $M$ of get_ack responses from a quorum
$Q$ of $\textsc{replicas}(\mathit{p})$ (line 1:5). For each replica
$\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{i}}}\in Q$, the get_ack
response from $\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{i}}}$ carries
a value $\mathit{v}_{i}$ of key $\mathit{k}$ and its common global stable time
$\mathit{cgst}_{i}$ when
$\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{i}}}$ computes the value
$\mathit{v}_{i}$ to return (line 2:3, discussed in Section 4.3). The client
takes the minimum $\mathit{cgst}_{i}$ for
$\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{i}}}\in Q$, and uses it to
update ${\sf cgst}_{\mathit{c}}$ if the latter is smaller (line 1:6).

Since there are at most $f$ Byzantine replicas in a partition, at least $f+1$
get_ack responses are from correct replicas. By Rule (III) and Inv (III),
these responses from correct replicas contain the same value, denoted
$\mathit{v}$. Hence, $\mathit{v}$ is the majority $\mathit{v}_{i}$ in $M$
(line 1:7). Finally, the client returns $\mathit{v}$ (line 1:8).

When a client $\mathit{c}$ issues a put operation on key $\mathit{k}$ with
value $\mathit{v}$, it sends a put_req request carrying its ${\sf
clock}_{\mathit{c}}$ and id $\mathit{c}$ to $\textsc{replicas}(\mathit{p})$
(line 1:13), where $\mathit{p}$ is the partition holding $\mathit{k}$ (line
1:11). Next the client waits to receive a set $M$ of put_ack responses from a
quorum $Q$ of $\textsc{replicas}(\mathit{p})$ (line 1:14). For each replica
$\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{i}}}\in Q$, the put_ack
response from $\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{i}}}$ carries
its common global stable time $\mathit{cgst}_{i}$. Then, the client takes the
minimum $\mathit{cgst}_{i}$ for
$\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{i}}}\in Q$, and uses it to
update ${\sf cgst}$ if the latter is smaller (line 1:15). Finally, ${\sf
dt}_{\mathit{c}}$ is set to the current ${\sf clock}_{\mathit{c}}$ (line
1:16).

###  4.3 Operation Executions at Replicas

Algorithm 2 Operation execution at
$\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{d}}}$

1:when received $\textsc{{get\\_req}}(\mathit{k},\mathit{ts})\;{\bf
from}\;{\bf client}\;\mathit{c}$

2: wait until ${\sf cgst}\geq\mathit{ts}$

3: $\mathit{v}\leftarrow\text{the value of key $k$ with the largest
timestamp}\leq\mathit{ts}\text{ in }{\sf store}$

4: ${\bf send}\;\langle\textsc{{get\\_ack}}(\mathit{v},{\sf
cgst})\rangle^{\mathit{p}}_{\mathit{d}}\;{\bf to}\;{\bf client}\;\mathit{c}$

5:

6:when received
$\langle\textsc{{put\\_req}}(\langle\mathit{k},\mathit{v},\mathit{cl},\mathit{c}\rangle_{\mathit{c}})\rangle_{\mathit{c}}\;{\bf
from}\;{\bf client}\;\mathit{c}$

7: pre: $\mathit{cl}\geq{\sf lst}$

8: wait $clock\geq\mathit{cl}$

9: var
$\mathit{vv}\leftarrow\langle\mathit{k},\mathit{v},\mathit{cl},\mathit{c}\rangle_{\mathit{c}}$

10: ${\sf store}\leftarrow{\sf store}\cup\\{\mathit{vv}\\}$

11: ${\bf send}\;\langle\textsc{{put\\_ack}}({\sf
cgst})\rangle^{\mathit{p}}_{\mathit{d}}\;{\bf to}\;{\bf client}\;\mathit{c}$

12: ${\bf
send}\;\langle\textsc{{replicate}}(\mathit{vv})\rangle^{\mathit{p}}_{\mathit{d}}\;{\bf
to}\;\textsc{replicas}(\mathit{p})\setminus\\{\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{d}}}\\}$

When a replica $\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{d}}}$
receives a $\textsc{get\\_req}(\mathit{k},\mathit{ts})$ request from some
client $\mathit{c}$, it first waits until ${\sf cgst}\geq\mathit{ts}$ (line
2:2) where $\mathit{ts}\triangleq\max\\{{\sf dt}_{\mathit{c}},{\sf
cgst}_{\mathit{c}}\\}$ (line 1:2). This implements Rule III, and is used to
ensure the session guarantee on client $\mathit{c}$ and eventual visibility of
updates to $\mathit{c}$. Then the replica obtains the value $\mathit{v}$ of
key $\mathit{k}$ in ${\sf store}$ which has the largest timestamp before
$\mathit{ts}$, breaking ties with client ids (line 2:3). Finally, it sends a
signed get_ack response, along with the value $\mathit{v}$ and its current
${\sf cgst}$, to client $\mathit{c}$ (line 2:4).

When a replica $\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{d}}}$
receives a $\textsc{put\\_req}(\mathit{k},\mathit{v},\mathit{cl},\mathit{c})$
request from client $\mathit{c}$, it first checks the precondition
$\mathit{cl}\geq{\sf curr\\_cgst}^{\mathit{p}}_{\mathit{d}}$ (line 2:7). This
enforces Rule II, and prevents fabricated updates with timestamps $\leq{\sf
cgst}$ at ${\sf store}^{\mathit{p}}_{\mathit{d}}$ from now on. If the
precondition holds, the replica adds the new versioned version
$\mathit{vv}\triangleq\langle\mathit{k},\mathit{v},\mathit{cl},\mathit{c}\rangle_{\mathit{c}}$
signed by $\mathit{c}$ (line 2:9) to ${\sf store}^{\mathit{p}}_{\mathit{d}}$
(line 2:10). Then, the replica sends a signed put_ack response, with its ${\sf
cgst}^{\mathit{p}}_{\mathit{d}}$, to client $\mathit{c}$ (line 2:11). Finally,
it broadcasts a signed replicate message with $\mathit{vv}$ to other replicas
in partition $\mathit{p}$ (line 2:12).

###  4.4 Metadata

####  4.4.1 Replica States

Each replica $\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{d}}}$
maintains a _version vector_ ${\sf VV}^{\mathit{p}}_{\mathit{d}}$ of size $D$,
with each entry per data center. For data center $\mathit{d}$, ${\sf
VV}^{\mathit{p}}_{\mathit{d}}[\mathit{d}]$ is the timestamp of the last update
that happens at $\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{d}}}$. For
data center $\mathit{i}\neq\mathit{d}$, ${\sf
VV}^{\mathit{p}}_{\mathit{d}}[\mathit{i}]$ is the largest timestamp of the
updates that happened at replica
$\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{i}}}$ and have been
propagated to $\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{d}}}$. For
fault-tolerance, we compute the _local stable time_ ${\sf
lst}^{\mathit{p}}_{\mathit{d}}$ at replica
$\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{d}}}$ as the _$(f+1)$ -st
minimum_ element of its ${\sf VV}^{\mathit{p}}_{\mathit{d}}$.

Each replica $\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{d}}}$ also
maintains a _lst vector_ ${\sf LV}^{\mathit{p}}_{\mathit{d}}$ of size $P$,
with each entry per partition. For partition $1\leq\mathit{j}\leq P$, ${\sf
LV}^{\mathit{p}}_{\mathit{d}}[\mathit{j}]$ is the largest $\mathit{lst}$ of
replica $\mathit{r}^{\mathit{\mathit{j}}}_{\mathit{\mathit{d}}}$ of which
$\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{d}}}$ is aware. We compute
the _global stable time_ ${\sf gst}^{\mathit{p}}_{\mathit{d}}$ at replica
$\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{d}}}$ as the minimum
element of its ${\sf LV}^{\mathit{p}}_{\mathit{d}}$. That is, ${\sf
gst}^{\mathit{p}}_{\mathit{d}}\triangleq\min_{1\leq\mathit{j}\leq P}{\sf
LV}^{\mathit{p}}_{\mathit{d}}[\mathit{j}]$.

Each replica $\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{d}}}$
periodically synchronizes their $\mathit{gst}^{\mathit{p}}_{\mathit{d}}$ with
others via PBFT, and maintains a _common global stable time_ ${\sf
cgst}^{\mathit{p}}_{\mathit{d}}$. We discuss it in Section 4.5.

####  4.4.2 Propagation

Algorithm 3 Updating metadata at replica
$\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{d}}}$

1:when received
$\langle\textsc{{replicate}}(\mathit{vv})\rangle^{\mathit{p}}_{i}$

2: ${\sf store}\leftarrow{\sf store}\cup\\{\mathit{vv}\\}$

3: ${\sf VV}[i]\leftarrow\max\\{{\sf VV}[i],\mathit{vv}.\mathit{cl}\\}$

4:

5:procedure broadcast() $\triangleright$ Run periodically

6: ${\sf lst}\leftarrow\max\\{{\sf lst},\text{the $(f+1)$-st minimum element
of }{\sf VV}[i]\\}$

7: ${\bf send}\;\langle\textsc{{bc}}({\sf
lst})\rangle^{\mathit{p}}_{\mathit{d}}\;{\bf
to}\;\textsc{datacenter}(\mathit{d})$

8:

9:when received $\langle\textsc{{bc}}(\mathit{lst})\rangle^{j}_{\mathit{d}}$

10: ${\sf LV}[j]\leftarrow\max\\{{\sf LV}[j],\mathit{lst}\\}$

11: ${\sf gst}\leftarrow\max\\{{\sf gst},\min\limits_{1\leq j\leq P}{\sf
LV}[j]\\}$

12: if ${\sf gst}>{\sf cgst}$ then

13: ${\bf send}\;\langle\textsc{{new\\_cgst}}({\sf
gst})\rangle^{\mathit{p}}_{\mathit{d}}\;{\bf to}\;\mathcal{S}$

14:

15:procedure heartbeat() $\triangleright$ Run periodically

16: pre: ${\sf clock}\geq{\sf VV}[\mathit{d}]+\Delta$

17: ${\bf send}\;\langle\textsc{{hb}}({\sf
clock})\rangle^{\mathit{p}}_{\mathit{d}}\;{\bf to}\;\textsc{replicas}(p)$

18:

19:when received
$\langle\textsc{{hb}}(\mathit{clock})\rangle^{\mathit{p}}_{\mathit{i}}$

20: ${\sf VV}[\mathit{i}]\leftarrow\max\\{{\sf
VV}[\mathit{i}],\mathit{clock}\\}$

As in GentleRain, Byz-GentleRain propagates and updates metadata in the
background. Once a new version $\mathit{vv}$ is created at replica
$\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{d}}}$, the replica sends a
signed $\textsc{replicate}(\mathit{vv})$ message to other replicas of
partition $\mathit{p}$ (line 2:12).

When replica $\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{d}}}$ receives
a $\textsc{replicate}(\mathit{vv})$ message from another replica
$\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{i}}$ in data center $i\neq d$, it
stores $\mathit{vv}$ in its ${\sf store}^{\mathit{p}}_{\mathit{d}}$ (line
3:2), and updates ${\sf VV}^{\mathit{p}}_{\mathit{d}}[\mathit{i}]$ to
$\mathit{vv}.\mathit{cl}$ if the latter is larger (line 3:3).

Each replica $\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{d}}}$
periodically computes its ${\sf lst}^{\mathit{p}}_{\mathit{d}}$ (line 3:6) and
sends a signed $\textsc{broadcast}({\sf lst}^{\mathit{p}}_{\mathit{d}})$
message to $\textsc{datacenter}(\mathit{d})$, all the servers in data center
$\mathit{d}$ (line 3:7).

When replica $\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{d}}}$ receives
a $\textsc{broadcast}(\mathit{lst})$ message from another replica
$\mathit{r}^{\mathit{\mathit{j}}}_{\mathit{\mathit{d}}}$ in data center $d$,
it updates ${\sf LV}^{\mathit{p}}_{\mathit{d}}$ and ${\sf
gst}^{\mathit{p}}_{\mathit{d}}$ accordingly (lines 3:10 and 3:11). If the new
${\sf gst}^{\mathit{p}}_{\mathit{d}}$ is larger than ${\sf
cgst}^{\mathit{p}}_{\mathit{d}}$ (line 3:12), the replica
$\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{d}}}$ sends a signed
$\textsc{new\\_cgst}({\sf gst}^{\mathit{p}}_{\mathit{d}})$ message to all
servers $\mathcal{S}$ of the key-value store (line 3:13).

To ensure liveness, a replica
$\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{d}}}$ periodically (e.g.,
at time interval $\Delta$; line 3:16) sends a signed $\textsc{hb}({\sf
clock}^{\mathit{p}}_{\mathit{d}})$ heartbeat to
$\textsc{replicas}(\mathit{p})$ (line 3:17). When replica
$\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{d}}}$ receives a heartbeat
$\textsc{hb}(\mathit{clock})$ message from replica
$\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{i}}}$, it updates its ${\sf
VV}^{\mathit{p}}_{\mathit{d}}[\mathit{i}]$ to $\mathit{clock}$ if the latter
is larger (line 3:20).

###  4.5 Synchronization of Global Stable Time

Algorithm 4 Updating ${\sf cgst}$ at replica
$\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{d}}}$ (see Table A1 in
Appendix 0.A for the definitions of ${\sf ValidNewLeader}$ and ${\sf
safe\\_propose}$ that are adapted from [5].)

1:$\begin{aligned} &{\sf
safe\\_collect}(\mathit{store})\triangleq\forall\textsc{{collect\\_ack}}(\\_,\mathit{st}_{\mathit{i}})\in\mathit{store},\forall\langle\\_,\\_,\\_,\\_\rangle_{\mathit{c}}=\mathit{u}\in\mathit{st}_{\mathit{i}}.\;{\sf
valid}(\mathit{u})\end{aligned}$

2:when received
$\langle\textsc{{new\\_cgst}}(\mathit{gst})\rangle^{\mathit{j}}_{\mathit{i}}=\mathit{m}$

3: pre: $\mathit{gst}\leq{\sf lst}\land\mathit{gst}>{\sf curr\\_cgst}$

4: ${\sf curr\\_cgst}\leftarrow\mathit{gst}$

5: $\textsc{{newview}}(\mathit{view})$ with $\mathit{view}>{\sf curr\\_view}$

6:

7:upon $\textsc{{newview}}(\mathit{view})$

8: pre: $\mathit{view}>{\sf curr\\_view}$

9: ${\sf curr\\_view}\leftarrow\mathit{view}$

10: ${\sf voted}\leftarrow{\sf false}$

11: ${\bf send}\;\langle\textsc{{newleader}}({\sf curr\\_view},{\sf
prepared\\_view},\underline{{\sf curr\\_cgst},{\sf prepared\\_store}},{\sf
cert})\rangle^{\mathit{p}}_{\mathit{d}}$

12: $\;{\bf to}\;{\sf leader}({\sf curr\\_view})$

13:

14:when received
$\\{\langle\textsc{{newleader}}(\mathit{view},\mathit{view}_{\mathit{i}},\underline{\mathit{cgst}_{\mathit{i}},\mathit{store}_{\mathit{i}}},\mathit{cert}_{\mathit{i}})\rangle^{\mathit{p}}_{\mathit{i}}\mid\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{i}}}\in
Q\\}=M$

15: from a quorum $Q$

16: pre: ${\sf curr\\_view}=\mathit{view}\land{\sf
leader}(\mathit{view})=\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{d}}}\land(\forall\mathit{m}\in
M.\;{\sf ValidNewLeader}(\mathit{m}))$

17: if
$\exists\mathit{j}.\;\mathit{view}_{\mathit{j}}=\max\\{\mathit{view}_{\mathit{i}}\mid\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{i}}}\in
Q\\}\neq 0$ then

18: ${\bf
send}\;\langle\textsc{{propose}}(\mathit{view},\underline{\mathit{store}_{\mathit{j}}},M)\rangle^{\mathit{p}}_{\mathit{d}}\;{\bf
to}\;\textsc{replicas}(\mathit{p})$

19: else

20: ${\sf
curr\\_cgst}\leftarrow\max\\{\mathit{cgst}_{\mathit{i}}\mid\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{i}}}\in
Q\land\mathit{cgst}_{\mathit{i}}\leq{\sf lst}^{\mathit{p}}_{\mathit{d}}\\}$

21: ${\bf send}\;\langle\textsc{{collect}}({\sf
curr\\_cgst})\rangle^{\mathit{p}}_{\mathit{d}}\;{\bf
to}\;\textsc{{replicas}}(\mathit{p})$

22: wait receive $\\{\langle\textsc{{collect\\_ack}}({\sf
curr\\_cgst},\mathit{st}_{\mathit{i}})\rangle^{\mathit{p}}_{\mathit{i}}\mid\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{i}}}\in
Q^{\prime}\\}=\mathit{store}$

23: from a quorum $Q^{\prime}$ satisfying ${\sf
safe\\_collect}(\mathit{store})$

24: ${\bf
send}\;\langle\textsc{{propose}}(\mathit{view},\underline{\mathit{store}},M)\rangle^{\mathit{p}}_{\mathit{d}}\;{\bf
to}\;\textsc{replicas}(\mathit{p})$

25:

26:when received
$\langle\textsc{{propose}}(\mathit{view},\mathit{store},M)\rangle^{\mathit{p}}_{\mathit{i}}=\mathit{m}$

27: pre: ${\sf curr\\_view}=\mathit{view}\land{\sf voted}={\sf false}\land{\sf
safe\\_propose}(\mathit{m})\land\underline{{\sf
safe\\_collect}(\mathit{store})}$

28: ${\sf curr\\_store}\leftarrow\mathit{store}$

29: ${\sf voted}\leftarrow{\sf true}$

30: ${\bf send}\;\langle\textsc{{prepared}}(\mathit{view},\underline{{\sf
hash}({\sf curr\\_store})})\rangle^{\mathit{p}}_{\mathit{d}}\;{\bf
to}\;\textsc{replicas}(\mathit{p})$

31:

32:when received
$\\{\langle\textsc{{prepared}}(\mathit{view},\mathit{h})\rangle^{\mathit{p}}_{\mathit{i}}\mid\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{i}}}\in
Q\\}=C$ from a quorum $Q$

33: pre: ${\sf curr\\_view}=\mathit{view}\land{\sf voted}={\sf
true}\land\underline{{\sf hash}({\sf curr\\_store})=\mathit{h}}$

34: ${\sf prepared\\_view}\leftarrow{\sf curr\\_view}$

35: ${\sf prepared\\_store}\leftarrow{\sf curr\\_store}$

36: ${\sf cert}\leftarrow C$

37: ${\bf
send}\;\langle\textsc{{commit}}(\mathit{view},\mathit{h})\rangle^{\mathit{p}}_{\mathit{d}}\;{\bf
to}\;\textsc{replicas}(\mathit{p})$

38:

39:when received
$\\{\langle\textsc{{commit}}(\mathit{view},\mathit{h})\rangle^{\mathit{p}}_{\mathit{i}}\mid\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{i}}}\in
Q\\}$ from a quorum $Q$

40: pre: ${\sf curr\\_view}={\sf
prepared\\_view}=\mathit{view}\land\underline{{\sf hash}({\sf
curr\\_store})=\mathit{h}}$

41:
$\mathit{store}\leftarrow\bigcup\big{\\{}\mathit{st}_{\mathit{i}}\mid\langle\textsc{{collect\\_ack}}(\mathit{cgst},\mathit{st}_{\mathit{i}})\rangle^{\mathit{p}}_{\mathit{i}}\in{\sf
curr\\_store}\big{\\}}$

42: if ${\sf cgst}<\mathit{cgst}$ then

43: ${\sf cgst}\leftarrow\mathit{cgst}$

44: ${\sf
store}\leftarrow\mathit{store}\cup\\{\langle\\_,\\_,\mathit{cl},\mathit{c}\rangle_{\mathit{c}}\in{\sf
store}\mid\mathit{cl}>{\sf curr\\_cgst}\\}$

45:

46:when received
$\langle\textsc{{collect}}(\mathit{cgst})\rangle^{\mathit{p}}_{\mathit{i}}=\mathit{m}$

47: pre: $\mathit{cgst}\leq{\sf lst}\land\mathit{cgst}\geq{\sf curr\\_cgst}$

48: ${\sf curr\\_cgst}\leftarrow\mathit{cgst}$

49:
$\mathit{st}\leftarrow\\{\langle\\_,\\_,\mathit{cl},\mathit{c}\rangle_{\mathit{c}}\in{\sf
store}\mid\mathit{cl}\leq{\sf curr\\_cgst}\\}$

50: ${\bf
send}\;\langle\textsc{{collect\\_ack}}(\mathit{cgst},\mathit{st})\rangle^{\mathit{p}}_{\mathit{d}}\;{\bf
to}\;\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{i}}}$

Each individual partition $\mathit{p}$ independently runs PBFT [8] to reach
agreement on a common global stable time $\mathit{cgst}$ _and_ the same set of
updates before $\mathit{cgst}$ across $\textsc{replicas}(\mathit{p})$
(Algorithm 4). We follow the pseudocode of single-shot PBFT described in [5],
and refer its detailed description and correctness proof to [5]. In the
following, we elaborate the parts specific to synchronization of global stable
time; see the pseudocode underlined in Algorithm 4.

When replica $\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{d}}}$ receives
a $\textsc{new\\_cgst}(\mathit{gst})$ message, it first checks whether
$\mathit{gst}\leq{\sf lst}^{\mathit{p}}_{\mathit{d}}$ as expected and
$\mathit{gst}>{\sf curr\\_cgst}^{\mathit{p}}_{\mathit{d}}$ which means that no
smaller global stable time has been or is being synchronized (line 4:3). If
so, it sets ${\sf curr\\_cgst}$ to $\mathit{gst}$ (line 4:4). Now the replica
stops accepting updates with timestamps $<{\sf
curr\\_cgst}^{\mathit{p}}_{\mathit{d}}$ (line 2:7). Then it triggers a newview
action with a $\mathit{view}$ larger than ${\sf
curr\\_view}^{\mathit{p}}_{\mathit{d}}$ (line 4:5).

As in classic PBFT [8, 5], the $\textsc{newview}(\mathit{view})$ action can
also be triggered spontaneously, due to timeout, or by failure detectors. When
it is triggered at a replica
$\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{d}}}$, the replica will
send a signed newleader message to the leader ${\sf leader}(\mathit{view})$ of
$\mathit{view}$ in $\textsc{replicas}(\mathit{p})$ (line 4:12). The newleader
message carries both ${\sf curr\\_cgst}^{\mathit{p}}_{\mathit{d}}$ and ${\sf
prepared\\_store}^{\mathit{p}}_{\mathit{d}}$ which is the set of updates
collected in ${\sf prepared\\_view}^{\mathit{p}}_{\mathit{d}}$.

When replica $\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{d}}}$ receives
a set $M$ of newleader messages from a quorum $Q$ of
$\textsc{replicas}(\mathit{p})$, it selects as its proposal from $M$ the set
$\mathit{store}_{\mathit{j}}$ of collected updates that is prepared in the
highest view, say $\mathit{view}_{\mathit{i}}$ (line 4:18), or, if there are
no such $\mathit{store}_{\mathit{j}}$, its own proposal. In the latter case,
the replica sets its ${\sf curr\\_cgst}^{\mathit{p}}_{\mathit{d}}$ to the
maximum of $\mathit{cgst}_{\mathit{i}}$ in $Q$ that are $\leq{\sf
lst}^{\mathit{p}}_{\mathit{d}}$ (line 4:20). Then, it sends a signed
$\textsc{collect}({\sf curr\\_cgst}^{\mathit{p}}_{\mathit{d}})$ message to
$\textsc{replicas}(\mathit{p})$ (line 3:21), and waits to receive enough
collect_ack messages.

When replica $\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{d}}}$ receives
a $\textsc{collect}(\mathit{cgst})$ message from replica
$\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{i}}}$ and $\mathit{cgst}$
passes the precondition (line 4:47), it first sets its ${\sf
curr\\_cgst}^{\mathit{p}}_{\mathit{d}}$ to $\mathit{cgst}$ (line 4:48). Now
the replica stops accepting updates with timestamps $<{\sf
curr\\_cgst}^{\mathit{p}}_{\mathit{d}}$ (line 2:7). Then it sends a signed
$\textsc{collect\\_ack}(\mathit{cgst},\mathit{st})$ message back to
$\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{i}}}$ (line 4:50), where
$\mathit{st}$ is the set of updates with timestamps $\leq{\sf
curr\\_cgst}^{\mathit{p}}_{\mathit{d}}$ in its ${\sf
store}^{\mathit{p}}_{\mathit{d}}$ (line 4:49).

The replica $\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{d}}}$ waits to
receive a set, denoted $\mathit{store}$, of collect_ack messages from a quorum
$Q^{\prime}$ of $\textsc{replicas}(\mathit{p})$. We require the messages in
$\mathit{store}$ carry the same ${\sf curr\\_cgst}$ as in the corresponding
collect message and the signatures of all the collected updates be valid
(i.e., ${\sf safe\\_collect}(\mathit{store})$ holds). Then, it sends a signed
propose message with $\mathit{store}$ as its proposal to
$\textsc{replicas}(\mathit{p})$ (line 4:24).

When replica $\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{d}}}$ receives
a propose message from replica
$\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{i}}}$, it also checks the
predicate ${\sf safe\\_collect}(\mathit{store})$ (line 4:27). After setting
${\sf curr\\_cgst}^{\mathit{p}}_{\mathit{d}}$ to $\mathit{store}$, it sends a
signed prepared message to $\textsc{replicas}(\mathit{p})$. When replica
$\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{d}}}$ receives a set $C$ of
prepared messages from a quorum $Q$ of $\textsc{replicas}(\mathit{p})$, both
its ${\sf curr\\_view}^{\mathit{p}}_{\mathit{d}}$ and ${\sf
curr\\_store}^{\mathit{p}}_{\mathit{d}}$ are prepared (lines 4:34 and 4:35).
The certification $C$ is also remembered in ${\sf
cert}^{\mathit{p}}_{\mathit{d}}$ (line 4:36). They will be sent to new leaders
in view changes to ensure agreement across views (line 4:12). Then the replica
sends a signed commit message to $\textsc{replicas}(\mathit{p})$ (line 4:37).

When replica $\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{d}}}$ receives
a set of commit message from a quorum $Q$ of $\textsc{replicas}(\mathit{p})$,
it computes $\mathit{store}$ as the union of the sets of updates
$\mathit{st}_{i}$ collected from each
$\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{i}}}$ in ${\sf
curr\\_store}^{\mathit{p}}_{\mathit{d}}$ (line 4:41). If ${\sf
cgst}^{\mathit{p}}_{\mathit{d}}$ is smaller than the $\mathit{cgst}$ in ${\sf
curr\\_store}^{\mathit{p}}_{\mathit{d}}$, the replica sets ${\sf
cgst}^{\mathit{p}}_{\mathit{d}}$ to this $\mathit{cgst}$ (line 4:42), and
replaces the set of updates with timestamps $\leq{\sf
curr\\_cgst}^{\mathit{p}}_{\mathit{d}}$ in ${\sf
store}^{\mathit{p}}_{\mathit{d}}$ with the new $\mathit{store}$ (line 4:44).

##  5 Evaluation

We evaluate Byz-GentleRain in terms of performance, throughput, and latency of
remote update visibility. We also compare Byz-GentleRain to Byz-RCM.

###  5.1 Implementation and Setup

We implement both Byz-GentleRain and Byz-RCM in Java and use Google’s Protocol
Buffers 222 Protocol Buffers: https://developers.google.com/protocol-buffers.
for message serialization. We implement the key-value stores as HashMap, where
each key is associated with a linked list of versioned values. The key-value
stores hold 300 keys in main memory, with each key of size 8 bytes and each
value of size 64 bytes.

We run all experiments on 4 Aliyun 333 Alibaba Cloud:
https://www.alibabacloud.com/. instances running Ubuntu 16.04. Each instance
is configured as a data center, with 1 virtual CPU core, 300 MB memory, and 1G
SSD storage. All keys are shared into 3 partitions within each data center,
according to their hash values.

###  5.2 Evaluation Results

(a) Throughput

(b) get latency

(c) put latency

(d) put visibility

Figure 2: Evaluation of Byz-GentleRain and Byz-RCM in failure-free scenarios.

Figure 2 shows the system throughput and the latency of get and put operations
of both Byz-GentleRain and Byz-RCM in failure-free scenarios. We vary the
$\textsc{get}:\textsc{put}$ ratios of workloads. First, Byz-RCM performs
better than Byz-GentleRain, especially with low $\textsc{get}:\textsc{put}$
ratios. This is because Byz-RCM assumes Byzantine fault-free clients and is
_signature-free_. In contrast, Byz-GentleRain requires clients sign each
put_req request. Second, it demonstrates that Byz-GentleRain is quite
efficient on typical workloads, especially for read-heavy workloads. Third,
the performance of Byz-GentleRain is closely comparable to that of Byz-RCM, if
digital signatures are omitted deliberately from Byz-GentleRain; see Figures
2(b) and 2(c). Finally, Figure 2(d) shows the latency of put visibility, which
gets higher and higher with more and more put operations.

(a)

(b)

Figure 3: Evaluation of Byz-GentleRain in Byzantine scenarios.

We also evaluate Byz-GentleRain in several typical Byzantine scenarios.
Generally, both Byzantine clients and replicas may fail by crash or send
arbitrary messages. Particularly, we consider  (1) Byzantine clients that may
send get_req and/or put_req requests with incorrect timestamps (line 1:4 and
line 1:13), and  (2) Byzantine replicas that may broadcast different global
stable time $\mathit{cgst}$ to replicas in different partitions (line 3:13).

Figure 3 demonstrates the impacts of various Byzantine failures on the system
throughput of Byz-GentleRain. On the one hand, the Byzantine failures of types
(1) and (2) above has little impact on throughput. On the other hand,
frequently sending arbitrary messages, such as new_cgst or propose messages,
does hurt throughput. This is probably due to the signatures carried by these
messages.

##  6 Related Work

As far as we know, Byz-RCM [19] is the only causal consistency protocol that
considers Byzantine faults. It achieves causal consistency in the client-
server model with $3f+1$ servers where up to $f$ servers may suffer Byzantine
faults, and any number of clients may crash. Byz-RCM has also been shown
optimal in terms of failure resilience. However, Byz-RCM did not tolerate
_Byzantine clients_ , and thus it could rely on clients’ requests to identify
bogus requests from Byzantine servers [19].

Linde _et. al._ [14] consider _peer-to-peer_ architecture. A centralized
server maintains the application data, while clients replicate a subset of
data and can directly communicate with each other. They analyze the possible
attacks of clients to causal consistency (the centralized server is assumed
correct), derive a secure form of causal consistency, and propose practical
protocols for implementing it.

Liskov and Rodrigues extend the notion of linearizability [10] and define BFT-
linearizability in the presence of Byzantine servers and clients [15]. They
also design protocols that achieve BFT-linearizability despite Byzantine
clients. The protocols require $3f+1$ replicas of which up to $f$ replicas may
be Byzantine. They are quite efficient for linearizable systems: Writes
complete in two or three phases, while reads complete in one or two phases.

Auvolat _et. al._ [3] defines a Byzantine-tolerant Causal Order broadcast
(BCO-broadcast) abstraction and proposes an implementation for it. However, as
a communication primitive for replicas, BCO-broadcast does not capture the
get/put semantics from the perspective of clients. Thus, it does not prevent
Byzantine clients from violating causality.

##  7 Conclusion

We present Byz-GentleRain, the first causal consistency protocol which
tolerates up to $f$ Byzantine servers among $3f+1$ servers in each partition
_and_ any number of Byzantine clients. The preliminary experiments show that
Byz-GentleRain is quite efficient on typical workloads. Yet, more extensive
large-scale experiments on more benchmarks are needed. We will also explore
optimizations of our synchronization protocol in Algorithm 4 in future work.

##  8 Acknowledgements

This work was partially supported by the CCF-Tencent Open Fund (CCF-Tencent
RAGR20200124) and the National Natural Science Foundation of China (No.
61772258).

## References

  * [1] Ahamad, M., Neiger, G., Burns, J.E., Kohli, P., Hutto, P.W.: Causal memory: Definitions, implementation, and programming. Distributed Computing 9(1), 37–49 (1995)
  * [2] Akkoorath, D.D., Tomsic, A.Z., Bravo, M., Li, Z., Crain, T., Bieniusa, A., Preguiça, N., Shapiro, M.: Cure: Strong semantics meets high availability and low latency. In: IEEE 36th International Conference on Distributed Computing Systems (ICDCS). pp. 405–414 (2016)
  * [3] Auvolat, A., Frey, D., Raynal, M., Taïani, F.: Byzantine-tolerant causal broadcast. Theoretical Computer Science (2021)
  * [4] Bouajjani, A., Enea, C., Guerraoui, R., Hamza, J.: On verifying causal consistency. In: Proceedings of the 44th ACM Symposium on Principles of Programming Languages. p. 626–638. POPL 2017 (2017)
  * [5] Bravo, M., Chockler, G.V., Gotsman, A.: Making byzantine consensus live. In: 34th International Symposium on Distributed Computing, DISC 2020. pp. 23:1–23:17 (2020). https://doi.org/10.4230/LIPIcs.DISC.2020.23
  * [6] Brewer, E.A.: Towards robust distributed systems (abstract). In: Proceedings of the 19th Annual ACM Symposium on Principles of Distributed Computing. pp. 7–. PODC’00 (2000)
  * [7] Burckhardt, S., Gotsman, A., Yang, H., Zawirski, M.: Replicated data types: Specification, verification, optimality. In: Proceedings of the 41st ACM Symposium on Principles of Programming Languages. pp. 271–284. POPL ’14 (2014)
  * [8] de Castro, M.O.T.: Practical Byzantine fault tolerance. Ph.D. thesis, Massachusetts Institute of Technology, Cambridge, MA, USA (2000)
  * [9] Du, J., Iorgulescu, C., Roy, A., Zwaenepoel, W.: Gentlerain: Cheap and scalable causal consistency with physical clocks. In: Proceedings of the ACM Symposium on Cloud Computing. p. 1–13. SoCC ’14 (2014)
  * [10] Herlihy, M.P., Wing, J.M.: Linearizability: A correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst. 12(3), 463–492 (Jul 1990). https://doi.org/10.1145/78969.78972
  * [11] Jiang, X., Wei, H., Huang, Y.: A generic specification framework for weakly consistent replicated data types. In: International Symposium on Reliable Distributed Systems (SRDS). pp. 143–154 (2020)
  * [12] Lamport, L.: Time, clocks, and the ordering of events in a distributed system. Commun. ACM 21(7), 558–565 (Jul 1978)
  * [13] Lesani, M., Bell, C.J., Chlipala, A.: Chapar: Certified causally consistent distributed key-value stores. In: Proceedings of the 43rd Annual ACM Symposium on Principles of Programming Languages. p. 357–370. POPL ’16 (2016)
  * [14] van der Linde, A., Leitão, J.a., Preguiça, N.: Practical client-side replication: Weak consistency semantics for insecure settings. Proc. VLDB Endow. 13(12), 2590–2605 (Jul 2020). https://doi.org/10.14778/3407790.3407847
  * [15] Liskov, B., Rodrigues, R.: Tolerating byzantine faulty clients in a quorum system. In: 26th IEEE International Conference on Distributed Computing Systems (ICDCS’06). pp. 34–34 (July 2006). https://doi.org/10.1109/ICDCS.2006.83
  * [16] Lloyd, W., Freedman, M.J., Kaminsky, M., Andersen, D.G.: Don’t settle for eventual: Scalable causal consistency for wide-area storage with cops. In: Proceedings of the 23rd ACM Symposium on Operating Systems Principles. pp. 401–416. SOSP ’11 (2011)
  * [17] Lloyd, W., Freedman, M.J., Kaminsky, M., Andersen, D.G.: Stronger semantics for low-latency geo-replicated storage. In: Proceedings of the 10th USENIX Conference on Networked Systems Design and Implementation. pp. 313–328. NSDI’13 (2013)
  * [18] Perrin, M., Mostefaoui, A., Jard, C.: Causal consistency: Beyond memory. In: Proceedings of the 21st ACM Symposium on Principles and Practice of Parallel Programming. PPoPP ’16 (2016)
  * [19] Tseng, L., Wang, Z., Zhao, Y., Pan, H.: Distributed causal memory in the presence of byzantine servers. In: 18th IEEE International Symposium on Network Computing and Applications, NCA 2019. pp. 1–8 (2019)
  * [20] Tyulenev, M., Schwerin, A., Kamsky, A., Tan, R., Cabral, A., Mulrow, J.: Implementation of cluster-wide logical clock and causal consistency in mongodb. In: Proceedings of the 2019 International Conference on Management of Data. pp. 636–650. SIGMOD ’19 (2019)

Table A1: Predicates in Algorithm 4 (adapted from [5]). $\begin{aligned} &{\sf
prepared}(\mathit{view},\mathit{h},M)\triangleq\\\ &\quad\exists Q.\;{\sf
quorum}(Q)\land
M=\\{\langle\textsc{{prepared}}(\mathit{view},\mathit{h},M)\rangle^{\mathit{p}}_{\mathit{i}}\mid\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{i}}}\in
Q\\}\end{aligned}$
---
$\begin{aligned} &{\sf
ValidNewLeader}(\langle\textsc{{newleader}}(\mathit{view},\mathit{view}_{\mathit{i}},\mathit{cgst}_{\mathit{i}},\mathit{cert}_{\mathit{i}})\rangle^{\mathit{p}}_{\mathit{i}})\triangleq\\\
&\quad\mathit{view}_{\mathit{i}}<\mathit{view}\land(\mathit{view}_{\mathit{i}}\neq
0\implies{\sf prepared}(\mathit{view}_{\mathit{i}},{\sf
hash}(\mathit{store}),M))\end{aligned}$
$\begin{aligned} &{\sf
safe\\_propose}(\langle\textsc{{propose}}(\mathit{view},\mathit{store},M)\rangle^{\mathit{p}}_{\mathit{j}})\triangleq\\\
&\qquad\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{j}}}={\sf
leader}(\mathit{view})\\\ &\quad\land\exists
Q,\mathit{view},\mathit{store},M.\;{\sf quorum}(Q)\\\ &\quad\land
M=\\{\langle\textsc{{newleader}}(\mathit{view},\mathit{view}_{\mathit{i}},\underline{\mathit{cgst}_{\mathit{i}},\mathit{store}_{\mathit{i}}},\mathit{cert}_{\mathit{i}})\rangle^{\mathit{p}}_{\mathit{i}}\mid\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{i}}}\in
Q\\}\\\ &\quad\land(\forall\mathit{m}\in M.\;{\sf
ValidNewLeader}(\mathit{m}))\\\
&\quad\land((\exists\mathit{j}.\;\mathit{view}_{\mathit{j}}\neq
0)\implies(\exists\mathit{j}.\;\mathit{view}_{\mathit{j}}=\max\\{\mathit{view}_{\mathit{i}}\mid\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{i}}}\in
Q\\}\land\mathit{store}=\mathit{store}_{\mathit{j}}))\end{aligned}$

##  Appendix 0.A Correctness of Byz-GentleRain

We show that Byz-GentleRain satisfies Byz-CC. We assume that single-shot PBFT
is correct and refer its detailed correctness proof to [5]. Table A1 gives the
definitions of the predicates ${\sf ValidNewLeader}$ and ${\sf
safe\\_propose}$ used in Algorithm 4, which are also adapted from [5].

###### Remark 1

In the following, we use $R$ and $W$ to denote the set of get and put
operations, respectively. We also define $O\triangleq R\cup W$ to denote the
set of all operations.

For a variable, e.g., ${\sf clock}_{\mathit{c}}$ at client $\mathit{c}$, we
refer to its value at time $\sigma$ by, e.g., $({\sf
clock}_{\mathit{c}})_{\sigma}$.

According to the description of Algorithms 1 and 2,

###### Lemma 1

_Rule I–Rule III_ are maintained by _Byz-GentleRain_.

###### Lemma 2

_Inv I–Inv III_ are maintained by _Byz-GentleRain_.

###### Proof

Inv I holds due to line 1:12. Inv II holds due to the read rule at line 2:7.
By the correctness of single-shot PBFT [5], Inv III holds.

######  Definition 1 (Timestamps)

We use $\textsl{ts}(\mathit{o})$ to denote the timestamp of operation
$\mathit{o}$, which is defined as follows:

  * •

For a get operation $\mathit{o}$, $\textsl{ts}(\mathit{o})$ refers to the
value of “$\mathit{ts}$” at line 1:2.

  * •

For a put operation $\mathit{o}$, $\textsl{ts}(\mathit{o})$ refers to the
value of “$\mathit{cl}$” at line 1:13.

###### Lemma 3

$(\mathit{w}\xrightarrow{{\sf so}}\mathit{w}^{\prime}\land\mathit{w}\in
W\land\mathit{w}^{\prime}\in
W)\implies\textsl{ts}(\mathit{w}^{\prime})>\textsl{ts}(\mathit{w}).$

###### Proof

Suppose that $\mathit{w}^{\prime}$ is issued by client $\mathit{c}$ at time
$\sigma^{\prime}$.

$\textsl{ts}(\mathit{w})\leq({\sf dt}_{c})_{\sigma^{\prime}}<({\sf
clock}_{\mathit{c}})_{\sigma^{\prime}}=\textsl{ts}(\mathit{w}^{\prime}).$

###### Lemma 4

$(\mathit{r}\xrightarrow{{\sf so}}\mathit{w}\land\mathit{r}\in
R\land\mathit{w}\in
W)\implies\textsl{ts}(\mathit{w})>\textsl{ts}(\mathit{r}).$

###### Proof

Suppose that $\mathit{r}$ and $\mathit{w}$ are issued by correct client
$\mathit{c}$ at time $\sigma_{\mathit{r}}$ and $\sigma_{\mathit{w}}$,
respectively. By line 1:2,

$\textsl{ts}(\mathit{r})=\max\\{({\sf
cgst}_{\mathit{c}})_{\sigma_{\mathit{r}}},({\sf
dt}_{\mathit{c}})_{\sigma_{\mathit{r}}}\\}.$

By Inv I,

$\textsl{ts}(\mathit{w})>({\sf cgst}_{\mathit{c}})_{\sigma_{\mathit{w}}}>({\sf
cgst}_{\mathit{c}})_{\sigma_{\mathit{r}}}.$

Moreover,

$\textsl{ts}(\mathit{w})>({\sf
dt}_{\mathit{c}})_{\sigma_{\mathit{w}}}\geq({\sf
dt}_{\mathit{c}})_{\sigma_{\mathit{r}}}.$

Putting it together yields

$\textsl{ts}(\mathit{w})>\textsl{ts}(\mathit{r}).$

###### Lemma 5

$(\mathit{w}\xrightarrow{{\sf so}}\mathit{r}\land\mathit{w}\in
W\land\mathit{r}\in
R)\implies\textsl{ts}(\mathit{r})\geq\textsl{ts}(\mathit{w}).$

###### Proof

Suppose that $\mathit{r}$ are issued by correct client $\mathit{c}$ at time
$\sigma$. By line 1:2,

$\textsl{ts}(\mathit{r})=\max\\{({\sf cgst}_{\mathit{c}})_{\sigma},({\sf
dt}_{\mathit{c}})_{\sigma}\\}\geq({\sf dt}_{\mathit{c}})_{\sigma}.$

By line 1:16,

$({\sf dt}_{\mathit{c}})_{\sigma}\geq\textsl{ts}(\mathit{w}).$

Thus,

$\textsl{ts}(\mathit{r})\geq\textsl{ts}(\mathit{w}).$

###### Lemma 6

$(\mathit{r}\xrightarrow{{\sf so}}\mathit{r}^{\prime}\land\mathit{r}\in
R\land\mathit{r}^{\prime}\in
R)\implies\textsl{ts}(\mathit{r}^{\prime})\geq\textsl{ts}(\mathit{r}).$

###### Proof

Suppose that $\mathit{r}$ and $\mathit{r}^{\prime}$ are issued by correct
client $\mathit{c}$ at time $\sigma$ and $\sigma^{\prime}$, respectively. By
line 1:2,

$\textsl{ts}(\mathit{r})=\max\\{({\sf cgst}_{\mathit{c}})_{\sigma},({\sf
dt}_{\mathit{c}})_{\sigma}\\},$

and

$\textsl{ts}(\mathit{r}^{\prime})=\max\\{({\sf
cgst}_{\mathit{c}})_{\sigma^{\prime}},({\sf
dt}_{\mathit{c}})_{\sigma^{\prime}}\\}.$

Moreover,

$({\sf cgst}_{\mathit{c}})_{\sigma^{\prime}}\geq({\sf
cgst}_{\mathit{c}})_{\sigma}\land({\sf
dt}_{\mathit{c}})_{\sigma^{\prime}}\geq({\sf dt}_{\mathit{c}})_{\sigma}.$

Thus,

$\textsl{ts}(\mathit{r}^{\prime})\geq\textsl{ts}(\mathit{r}).$

###### Lemma 7

$\mathit{o}\xrightarrow{{\sf so}}\mathit{o}^{\prime}\land\mathit{o}\in
O\land\mathit{o}^{\prime}\in
O\implies\textsl{ts}(\mathit{o}^{\prime})\geq\textsl{ts}(\mathit{o}).$

###### Proof

By Lemmas 3–6.

###### Lemma 8

$\mathit{w}\xrightarrow{{\sf rf}}\mathit{r}\land\mathit{w}\in
W\land\mathit{r}\in
R\implies\textsl{ts}(\mathit{r})\geq\textsl{ts}(\mathit{w}).$

###### Proof

By the read rule at line 2:7.

###### Lemma 9

$\mathit{o}\leadsto\mathit{o}^{\prime}\land o\in O\land o^{\prime}\in
O\implies\textsl{ts}(\mathit{o}^{\prime})\geq\textsl{ts}(\mathit{o}).$

###### Proof

By Lemmas 7 and 8.

###### Lemma 10

Consider $\mathit{r}\in R$ and $\mathit{w}\in W$. Suppose $\mathit{r}$ reads
from some value at a correct replica
$\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{d}}}$ at time $\sigma$
(line 2:3). If $\mathit{w}$ would be added to ${\sf
store}^{\mathit{p}}_{\mathit{d}}$ at a later time than $\sigma$ (line 2:10)
then $\textsl{ts}(\mathit{w})>\textsl{ts}(\mathit{r})$.

###### Proof

By Rule I,

$({\sf cgst}^{\mathit{p}}_{\mathit{d}})_{\sigma}\geq\textsl{ts}(\mathit{r}).$

By Inv II,

$\textsl{ts}(\mathit{w})>({\sf cgst}^{\mathit{p}}_{\mathit{d}})_{\sigma}.$

Thus,

$\textsl{ts}(\mathit{w})>\textsl{ts}(\mathit{r}).$

###### Lemma 11

Consider $\mathit{r}\in R$ and $\mathit{w}\in W$. Suppose the successful
$\mathit{r}$ returns at time $\sigma$ (line 2:3) and the successful
$\mathit{w}$ starts at a later time than $\sigma$ in partition $\mathit{p}$.
Then $\lnot(\mathit{w}\leadsto\mathit{r}$).

###### Proof

By lines 15 and 114, there is a _correct_ replica at which $\mathit{r}$
obtains its value (line 2:3) _before_ $\mathit{w}$ is added to the store (line
2:10). By Lemma 10,

$\textsl{ts}(\mathit{w})>\textsl{ts}(\mathit{r}).$

By Lemma 9,

$\lnot(\mathit{w}\leadsto\mathit{r}).$

###### Theorem 0.A.1

_Byz-GentleRain_ satisfies Byz-CC. That is, when a certain put operation is
visible to a client, then so are all of its causal dependencies.

###### Proof

By Lemmas 11 and 15.

###### Lemma 12

Suppose a put operation $\mathit{w}$ successfully returns in partition
$\mathit{p}$ at time $\sigma$ (line 1:14). Then, it will eventually be in
${\sf store}^{\mathit{p}}_{\mathit{i}}$ for each correct data center
$\mathit{i}$.

###### Proof

By line 1:14 and line 4:23, there is a _correct_ replica in partition
$\mathit{p}$ at which $\mathit{w}$ is added to the store (line 2:10) before it
is sent to the PBFT leader in the collect_ack message (line 4:50). By the
correctness of single-shot PBFT [5], it will eventually be in ${\sf
store}^{\mathit{p}}_{\mathit{i}}$ for each correct data center $\mathit{i}$.

###### Lemma 13

Let $\mathit{w}$ be a successful put operation. Then, eventually for each
correct replica $\mathit{r}^{\mathit{\mathit{j}}}_{\mathit{\mathit{i}}}$
($1\leq\mathit{i}\leq D,1\leq\mathit{j}\leq P$), ${\sf
cgst}^{\mathit{j}}_{\mathit{i}}\geq\textsl{ts}(\mathit{w})$.

###### Proof

Suppose $\mathit{w}$ successfully returns in partition $\mathit{p}$. Then it
is added to the stores of at least $f+1$ _correct_ replicas in
$\textsc{replicas}(\mathit{p})$. By Algorithm 3, eventually for each correct
replica $\mathit{r}^{\mathit{\mathit{j}}}_{\mathit{\mathit{i}}}$, ${\sf
lst}^{\mathit{j}}_{\mathit{i}}\geq\textsl{ts}(\mathit{w})$ and ${\sf
gst}^{\mathit{j}}_{\mathit{i}}\geq\textsl{ts}(\mathit{w})$. By Algorithm 4,
${\sf cgst}^{\mathit{j}}_{\mathit{i}}\geq\textsl{ts}(\mathit{w})$.

###### Lemma 14

Suppose a correct replica sends a $\textsc{new\\_cgst}(\mathit{gst})$ message
(line 3:13). Then, there is a $\mathit{cgst}\geq\mathit{gst}$ such that
eventually for each correct replica
$\mathit{r}^{\mathit{\mathit{j}}}_{\mathit{\mathit{i}}}$ ($1\leq\mathit{i}\leq
D,1\leq\mathit{j}\leq P$), ${\sf
cgst}^{\mathit{j}}_{\mathit{i}}\geq\mathit{cgst}$.

###### Proof

A byzantine replica can propose $gst^{\mathit{p}}_{\mathit{d}}$ to replica
$\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{d}}}$, but it will take
effect only when $gst^{\mathit{p}}_{\mathit{d}}<lst^{\mathit{p}}_{\mathit{d}}$
maintained by $\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{d}}}$. If
$gst^{\mathit{p}}_{\mathit{d}}$ is smaller than a $gst^{\prime}$ broadcast by
a correct replica, then it will be overwritten at
$\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{d}}}$. And eventually,
there must be a $gst$ version
$\geq\mathit{r}^{\mathit{\mathit{p}}}_{\mathit{\mathit{d}}}$ broadcast by a
correct replica. Thus it will eventually by overwritten by a correct $gst$
version.

###### Lemma 15

Consider $\mathit{r}\in R$ and $\mathit{w}\in W$. Suppose the successful
$\mathit{r}$ returns at time $\sigma$ (line 2:3) and the successful
$\mathit{w}$ starts at a later time than $\sigma$ in any partition
$\mathit{j}\neq\mathit{p}$. Then $\lnot(\mathit{w}\leadsto\mathit{r}$).

###### Proof

By Algorithm 27, $\textsl{ts}{\mathit{w}}>{\sf lst}$ at each replca who accept
$\mathit{w}$. By Algorithm 22, $\textsl{ts}{\mathit{r}}\leq{\sf cgst}$ at each
replica who reply it. Since ${\sf lst}$ at any correct correct server is an
upbound of all the ${\sf cgst}$ at all correct replicas,
$tsof(\mathit{w})>{\sf lst}>{\sf cgst}>\textsl{ts}(\mathit{r})$. So
$\lnot(\mathit{w}\leadsto\mathit{r})$.