# Construction of a Byzantine Linearizable SWMR Atomic Register from SWSR
Atomic Registers

Ajay D. Kshemkalyani111University of Illinois Chicago, USA. Email:
<EMAIL_ADDRESS>Manaswini Piduguralla222Indian Institute of Technology
Hyderabad, India. Email<EMAIL_ADDRESS>Sathya Peri333Indian
Institute of Technology Hyderabad, India. Email<EMAIL_ADDRESS>Anshuman Misra444University of Illinois Chicago, USA. Email<EMAIL_ADDRESS>
###### Abstract

The SWMR atomic register is a fundamental building block in shared memory
distributed systems and implementing it from SWSR atomic registers is an
important problem. While this problem has been solved in crash-prone systems,
it has received less attention in Byzantine systems. Recently, Hu and Toueg
gave such an implementation of the SWMR register from SWSR registers. While
their definition of register linearizability is consistent with the definition
of Byzantine linearizability of a concurrent history of Cohen and Keidar, it
has these drawbacks. (1) If the writer is Byzantine, the register is
linearizable no matter what values the correct readers return. (2) It ignores
values written consistently by a Byzantine writer. We need a stronger notion
of a correct write operation. (3) It allows a value written to just one or a
few readers’ SWSR registers to be returned, thereby not validating the
intention of the writer to write that value honestly. (4) Its notion of a
“current” value returned by a correct reader is not related to the most recent
value written by a correct write operation of a Byzantine writer. We need a
more up to date version of the value that can be returned by a correct reader.
In this paper, we give a stronger definition of a Byzantine linearizable
register that overcomes the above drawbacks. Then we give a construction of a
Byzantine linearizable SWMR atomic register from SWSR registers that meets our
stronger definition. The construction is correct when $n>3f$, where $n$ is the
number of readers, $f$ is the maximum number of Byzantine readers, and the
writer can also be Byzantine. The construction relies on a public-key
infrastructure.

Keywords: Byzantine fault tolerance, SWMR atomic register, Linearizability,
SWSR register

##  1 Introduction

Implementing shared registers from weaker types of registers is a fundamental
problem in distributed systems and has been extensively studied [2, 3, 5, 11,
6, 8, 12, 13, 18, 19, 21, 17, 22, 23, 24]. We consider the problem of
implementing a single-writer multi-reader register (SWMR) from single-writer
single-reader (SWSR) registers in a system with Byzantine processes. This SWMR
register in a Byzantine setting is of great importance in recent research. For
example, Mostefaoui et al. [16] prove that in message-passing systems with
Byzantine failures, there is a $f$-resilient implementation of a SWMR register
if and only if $f<n/3$ processes are faulty, where $f$ is the number of
Byzantine processes and $n$ is the total number of processes. It was the first
to give the definition of a linearizable SWMR register in the presence of
Byzantine processes and [4] generalized it to objects of any type. Aguilera et
al. [1] use atomic SWMR registers to solve some agreement problems in hybrid
systems subject to Byzantine process failures. Cohen and Keidar [4] give
$f$-resilient implementations of three objects – asset transfer, reliable
broadcast, atomic snapshots – using atomic SWMR registers in systems with
Byzantine failures where at most $f<n/2$ processes are faulty. Their
implementations were based on their definition of Byzantine linearizability of
a concurrent history.

In other related work, a SWMR register was built above a message-passing
system where processes communicate using send/receive primitives with the
constraint that $f<n/3$ [10, 16]. These works do not use signatures. Unbounded
history registers were required in [10] whereas [16] used $O(n^{2})$ messages
per write operation. Although building SWMR registers over SWSR registers or
over message-passing systems is equivalent as SWSR registers can be emulated
over send/receive and vice versa, this is a round-about and expensive
solution. A similar problem for the client-server paradigm in message-passing
systems was solved in [14] using cryptography.

###  1.1 Motivation

The SWMR atomic register is seen to be a basic building block in shared memory
distributed systems and implementing it from SWSR atomic registers is an
important problem. While this problem has been solved in crash-prone systems,
it has received recent attention in Byzantine systems. Recently, Hu and Toueg
gave such an implementation of the SWMR register from SWSR registers [9].
While their definition of register linearizability is consistent with the
definition of Byzantine linearizability of a concurrent history of Cohen and
Keidar [4], both [9, 4] as well as [10, 16] have the following drawbacks.

  1. 1.

If the writer is Byzantine, the register is vacuously linearizable no matter
what values the correct readers return. Reads by correct processes can return
any value whatsoever including the initial value while the register meets
their definition of linearizability. In particular, there is no view
consistency. For example, in the Hu-Toueg algorithm, consider a scenario where
a Byzantine writer writes a different data value associated with the same
counter value to the various readers’ SWSR registers. The correct readers will
return different data values associated with the same counter value, thus
having inconsistent views. An example application where this is a problem is
collaborative editing for a document hosted on a single server. Another reason
why this is problematic is that it violates the agreement clause of the well-
known consensus/Byzantine agreement problem, which requires that all non-
faulty processes must agree on the same value even if the source is Byzantine.
We require view consistency.

  2. 2.

Their definition of register linearizability does not factor in, or ignores,
those values written by a Byzantine writer, by honestly following the writer
protocol for those values. We need a stronger notion of a correct write
operation that factors in such values as being written correctly. Also, note
that the Byzantine writer is in control of the execution both above and below
the SWMR register interface and hence the value that it writes in a correct
write operation can be assumed to be the value intended to be written
(correctly) and not altered by Byzantine behavior.

  3. 3.

Their definition of register linearizability allows a value written by a
Byzantine writer to just a single reader’s SWSR register to be returned by a
correct process. In order to validate that the writer intended to write that
value honestly, we would like a minimum threshold number of readers’ SWSR
registers to be written that same value to enable that value to become
eligible for being returned to a correct reader. This validates the intention
of the Byzantine writer to write that particular value.

  4. 4.

In their definition of register linearizability, their notion of a “current”
value returned by a correct reader is not related to the most recent value
written by a correct write operation of a Byzantine writer. We need a more up
to date version of the value that can be returned by a correct reader. This
helps give a stronger guarantee of progress from the readers’ perspective.

Our definition of a Byzantine linearizable register is stronger than not just
that of [4, 9] but also that of [10, 16, 14] and overcomes the above
drawbacks. Further, we are interested in implementing the SWMR register over
SWSR registers directly in the shared memory model.

###  1.2 Contributions

  1. 1.

In this paper, we give a stronger definition of a Byzantine linearizable
register that overcomes all the above drawbacks of [4, 9] and [10, 16, 14]. We
introduce the concept of a correct write operation by a Byzantine writer as
one that conforms to the write protocol. We also introduce the notion of a
pseudo-correct write operation by a Byzantine writer, which has the effect of
a correct write operation. Only correct and pseudo-correct writes may be
returned by correct readers. The correct and pseudo-correct writes are totally
ordered and this order is the total order in logical time [15, 20] in which
the writes are performed.

  2. 2.

Then we give a construction of a Byzantine linearizable SWMR atomic register
from SWSR atomic registers that meets our stronger definition. The
construction is correct when $n>3f$, where $n$ is the number of readers, $f$
is the maximum number of Byzantine readers, and the writer can also be
Byzantine. The construction relies on a public-key infrastructure (PKI).

The construction develops the idea of the readers issuing logical read
timestamps to the values set aside for them by the writer. Logical global
states on the readers’ SWSR registers, akin to consistent cuts in message-
passing systems [15], are then constructed. The algorithm logic ensures that
values read at/along such global states form a total order, thereby helping to
ensure Byzantine register linearizability.

As compared to the algorithm in [9] which can tolerate any number of Byzantine
readers, our algorithm requires $f<n/3$. Also, in the algorithm in [9], a
reader that stops reading also stops taking implementation steps whereas our
algorithm requires a reader helper thread to take infinitely many steps even
if it has no read operation to apply. The algorithm in [9] as well as our
algorithm use a PKI.

Outline: Section 2 gives the system model and preliminaries. Section 3 gives
our characterization of a Byzantine linearizable register based on logical
time and culminates in the definition of such a register. Section 4 gives our
construction of the SWMR Byzantine linearizable register using SWSR registers.
Section 5 gives the correctness proof. Section 6 concludes.

##  2 Model and Preliminaries

###  2.1 Model Basics

We consider the shared memory model of a distributed system. The system
contains a set $P$ of asynchronous processes. These processes access some
shared memory objects. All inter-process communication is done through an API
exposed by the objects. Processes invoke operations that return some response
to the invoking process. We assume reliable shared memory but allow for an
adversary to corrupt up to $f$ processes in the course of a run. A corrupted
process is defined as being Byzantine and such a process may deviate
arbitrarily from the protocol. A non-Byzantine process is correct and such a
process follows the protocol and takes infinitely many steps.

We also assume a PKI. Using this, each process has a public-private key pair
used to sign data and verify signatures of other processes. A values $v$
signed by process $p$ is denoted $\langle v\rangle_{p}$.

We give an algorithm that emulates an object $O$, viz., a SWMR register from
SWSR registers. We assume that there is adequate access control such that a
SWSR register can be accessed only by the single writer and the single reader
between whom the register is set up, and that another (Byzantine) process
cannot access it. The algorithm is organized as methods of $O$. A method
execution is a sequence of steps. It begins with the invoke step, goes through
steps that access lower-level objects, viz., SWSR registers, and ends with a
return step. The invocation and response delineate the method’s execution
interval. In an execution $\sigma$, each correct process invokes methods
sequentially, and steps of different processes are interleaved. Byzantine
processes take arbitrary steps irrespective of the protocol. The history $H$
of an execution $\sigma$ is the sequence of high-level invocation and response
events of the emulated SWMR register in $\sigma$. A history $H$ defines a
partial order $\prec_{H}$ on operations. $op_{1}\prec_{H}op_{2}$ if the
response event of $op_{1}$ precedes the invocation event of $op_{2}$ in $H$.
$op_{1}$ is concurrent with $op_{2}$ if neither precedes the other.

In our algorithm, we assume that each reader process has a helper thread that
takes infinitely many steps even if the reader stops reading the implemented
register. These steps are outside the invocation-response intervals of the
readers’ own operations. Also, the linearization point of a pseudo-correct
write operation may fall after the invocation-response interval. These are
non-standard features of our shared memory model.

###  2.2 Linearizability of a Concurrent History

Linearizability, a popular correctness condition for concurrent objects, is
defined using an object’s sequential specification.

######  Definition 1.

(Linearization of a concurrent history:) A linearization of a concurrent
history $H$ of object $o$ is a sequential history $H^{\prime}$ such that:

  1. 1.

After removing some pending operations from $H$ and completing others by
adding matching responses, it contains the same invocations and responses as
$H^{\prime}$,

  2. 2.

$H^{\prime}$ preserves the partial order $\prec_{H}$, and

  3. 3.

$H^{\prime}$ satisfies $o$’s sequential specification.

A SWMR register as well as a SWSR register expose the read and write
operations. The sequential specification of a SWMR and a SWSR register states
that a read operation from register $Reg$ returns the value last written to
$Reg$. Following Cohen and Keidar [4], we manage Byzantine behavior in a way
that provides consistency to correct processes. This is achieved by
linearizing correct processes’ operations and offering a degree of freedom to
embed additional operations by Byzantine processes.

Let $H|_{correct}$ denote the projection of history $H$ to all correct
processes. History $H$ is Byzantine linearizable if $H|_{correct}$ can be
augmented by (some) operations of Byzantine processes such that the completed
history is linearizable. Thus, there is another history with the same
operations by correct processes as in $H$, and additional operations by at
most $f$ Byzantine processes.

######  Definition 2.

(Byzantine linearization of a concurrent history [4]:) A history $H$ is
Byzantine linearizable if there exists a history $H^{\prime}$ such that
$H^{\prime}|_{correct}=H|_{correct}$ and $H^{\prime}$ is linearizable.

An object supports Byzantine linearizable executions if all of its executions
are Byzantine linearizable. SWMR registers support Byzantine linearizable
executions because before every read from such a register, invoked by a
correct process, one can add a corresponding Byzantine write.

###  2.3 Linearizability of Register Implementations

Hu and Toueg defined register linearizability in a system with Byzantine
processes as follows [9]. They let $v_{0}$ be the initial value of the
implemented register and $v_{k}$ be the value written by the $k$th write
operation by the writer $w$ of the implemented register.

######  Definition 3.

(Register Linearizability [9]:) In a system with Byzantine process failures,
an implementation of a SWMR register is linearizable if and only if the
following holds. If the writer is not malicious, then:

  * •

(Reading a “current” value) If a read operation R by a process that is not
malicious returns the value $v$ then:

    * –

there is a write $v$ operation that immediately precedes R or is concurrent
with R, or

    * –

$v=v_{0}$ (the initial value) and no write operation precedes R.

  * •

(No “new-old” inversion) If two read operations R and R’ by processes that are
not malicious return values $v_{k}$ and $v_{k^{\prime}}$, respectively, and R
precedes R’, then $k\leq k^{\prime}$.

While this definition of register linearizability is consistent with the
definition of a Byzantine linearization of a concurrent history (Definition
2), in the sense that both are concerned only with correct processes’ views,
it is not ideal for the reasons given in Section 1.1. Therefore the register
should meet stronger criteria of a linearizable register, in the face of
Byzantine processes, to accommodate the behavior of the Byzantine writer when
it is behaving (writing) correctly. We term such a register as a Byzantine
linearizable register. In this paper, we first define a Byzantine linearizable
register, and then solve the problem of constructing a Byzantine linearizable
SWMR register from SWSR registers.

##  3 Characterization of Byzantine Register Linearizability

The object SWMR register supports Byzantine linearizable executions [4].
However, we need to construct a SWMR register from SWSR registers. We assume
wlog that there are $n$ SWSR registers $R\\_init_{wi}$ writable by the single
writer $w$ and readable by reader $i\in[i,n]$. Here we characterize the
requirements for such a construction, culminating in Definition 13 of
Byzantine Register Linearizability.

The writer as well as the reader processes can be Byzantine. As a Byzantine
reader can return any value whatsoever, the linearizability specification is
based on values that correct readers return. The Byzantine writer can behave
anyhow and can write different values to the SR registers, or write different
values to different subsets of SR registers while not writing to some of them
at all, or write multiple different values over time to the same some or all
SR registers, as part of the same write operation. We assume that $t$ of the
$n$ readers are Byzantine. In our characterization, we seek recourse to
logical time but present the final definition of the Byzantine linearizable
register using physical time.

We refer to a write operation $o(v)$ by a timestamp vector $T$ of size $n$,
where $T[i]$ is the logical timestamp assigned to a value of $v$ written into
$R\\_init_{wi}$. This vector gives the logical time vector of the write
operation $o(v)$. As $T[i]$ is a logical timestamp, it can equivalently be
assigned by reader $i$. Thus, correct readers assign monotonically increasing
timestamp values whereas a timestamp that violates this must have been
assigned by a Byzantine reader and can be rejected/ignored by correct readers.
We define the relations $\leq$, $<$, and $||$ (concurrent) on the set of
timestamp vectors ${\cal T}$ in the standard way as follows.

  * •

$T_{1}\leq T_{2}=_{def}\forall i\in[1,n],T_{1}[i]\leq T_{2}[i]$

  * •

$T_{1}<T_{2}=_{def}T_{1}\leq T_{2}\wedge\exists i\,|\,T_{1}[i]<T_{2}[i]$

  * •

$T_{1}\,||\,T_{2}=_{def}\exists i\,|T_{1}[i]<T_{2}[i]\wedge\exists
j\,|\,T_{1}[j]>T_{2}[j]$

$({\cal T},<)$ forms a lattice.

In general, when an object $O_{1}$, denoted a high-level object (HLO) is
simulated or constructed using objects of another type $O_{2}$, denoted a low-
level object (LLO), there are two interfaces. A process interacts with the HLO
through a high-level interface (HLI) through alternating invocations and
matching responses. Between such a pair of matching invocation and response,
the process interacts with the LLO through a low-level interface (LLI) using
alternating invocations and responses. Such interactions are in software.

For our problem, the HLO is the Byzantine-tolerant SWMR atomic register and
the HLI is the read and write operation. The LLO is the SWSR atomic register
and the LLI is also the read and write operation. We term the program code
executed below the HLI and above the LLI for a single invocation of a
write/read at the HLI as the code or protocol for the (HLI) write
operation/read operation, respectively.

In the face of Byzantine readers as well as a Byzantine writer, we need to
define a correct write operation. In the sequel, we use $u$ or $v$ to refer to
the actual data value written. A $write(v)$ invocation at the HLI may be
converted at a Byzantine writer into possibly multiple operation invocations
for different $write(v^{\prime})$ at the LLI to all or some subset of the
various instances of the LLO. If a $write(v)$ invocation at the HLI is
converted by a Byzantine writer into an invocation of $write(v^{\prime})$ and
it executes the protocol exactly for this value $v^{\prime}$, it is considered
as a correct write operation because that can be taken to be the value the
writer writes or intended to write. Likewise if the $write(v)$ at the HLI is
converted into multiple serial invocations of $write(v^{\prime})$ (for
different values of $v^{\prime}$) and the protocol for each of these
$v^{\prime}$ is correctly followed, these various $write(v^{\prime})$ are
considered correct write operations because that sequence of write operations
can be taken to be the values the writer writes or intended to write. This is
because the invocation/response at the HLI is at a Byzantine process which
controls the execution of code above the LLI and above the HLI. In a correct
write operation, the code between the HLI and the LLI is followed correctly by
the Byzantine process.

######  Definition 4.

A correct write operation is a write operation that follows the write
protocol.

So far in the literature [4, 9], any behavior of a Byzantine writer is
allowable in the linearizability definition. We accommodate a Byzantine writer
differently and introduce the concept of a pseudo-correct write operation
(Definition 7), which is a Byzantine write operation that has the effect of a
correct write operation. This is first informally motivated as follows. A
Byzantine write operation can, for example,

  1. 1.

write multiple values to the various $R\\_init_{wi}$ (possibly resulting in
multiple pseudo-correct write operations) or

  2. 2.

together with earlier write operations write a single value (possibly
resulting in a pseudo-correct write operation), or

  3. 3.

together with earlier write operations that wrote different values write those
values (possibly resulting in multiple pseudo-correct write operations).

Thus, there is no longer a one-one mapping from write operations issued to the
HLI object interface to values written to the object; it is a many-many
mapping. If a pseudo-correct write operation is a result of values written
across multiple HLO write operations, we define that pseudo-correct write
operation to occur in the latest of those HLO write operations. Its invocation
and response are those of that latest HLO operation. Its linearization point
occurs when the write takes effect for correct readers and this can happen
even after the HLO write response to the HLO write invocation in which the
pseudo-correct write occurred. Due to the many-many mapping, one HLO write
invocation-response can result in different values being written by the
pseudo-correct operations and read/returned by correct readers. This does not
pose any ambiguity because the different values that are returned to the
correct readers have different logical timestamp vectors.

######  Definition 5.

A potential pseudo-correct write operation of value $v$ is a write operation,
timestamped $T(v)$, that may not follow the write protocol but

  1. 1.

$T$ is such that there does not exist any correct write operation timestamp
$T^{\prime}$ where $\exists i\,|\,T[i]<T^{\prime}[i]\wedge\exists
j\,|\,T[j]>T^{\prime}[j]$, and

  2. 2.

there is a quorum of size $\geq n-t$ indices $i$ such that $v$ was written to
$R\\_init_{wi}$ and logically timestamped $T(v)[i]$ (equivalently and in
practice by reader $i$).

######  Definition 6.

A write operation stabilizes if its value is returnable, meaning eligible for
being returned, by a correct reader.

A correct write operation always stabilizes whereas a potential pseudo-correct
write may stabilize, depending on run-time dynamic data races, steps of
Byzantine readers, and the algorithm. Only all write operations that stabilize
have a linearization point.

######  Definition 7.

A pseudo-correct write operation is a potential pseudo-correct write operation
that stabilizes.

######  Definition 8.

(Monotonicity/Total Order of stabilized write operation vector timestamps
Property:) The set of write operation timestamps that stabilize is totally
ordered.555This definition is not about the monotonicity of vector timestamp
values as a function of the physical time order in which their operations
stabilize, but about the set of such vector timestamps which is totally
ordered.

If the Monotonicity/Total Order Property is satisfied, of any two potential
pseudo-correct writes whose vector timestamps are concurrent, at most one can
stabilize.

######  Definition 9.

(Genuine Advance of Timestamp Property:) For vector timestamps $T_{1}(v_{1})$
and $T_{2}(v_{2})$ of correct and pseudo-correct write operations such that
$T_{1}<T_{2}$, there is index $i$ of a correct reader process such that
$T_{1}[i]<T_{2}[i]$.

In conjunction with the Monotonicity/Total Order Property, the Genuine Advance
of Timestamp Property guarantees that there has been progress from $T_{1}$ to
$T_{2}$ and this progress includes a new write of $v_{2}$ to a $R\\_init_{wi}$
register for a correct process $i$. Thus the progress is not a fake operation
reported by a Byzantine reader. Further, the latest values as per $T_{2}$ at
$n-t$ $R\\_init_{wj}$ are also $v_{2}$.

Let $T_{corr}$ denote the timestamp of a correct or a pseudo-correct write
operation, which is the timestamp of a stabilized write operation.

######  Definition 10.

A consistent timestamp of a write operation is a vector timestamp $T$ such
that $\not\exists T_{corr}\,|\,(\exists i\,|\,T[i]<T_{corr}[i]\wedge\exists
j\,|\,T[j]>T_{corr}[j])$.

The set of consistent timestamps forms a sublattice $({\cal T}_{c},<)$ of
$({\cal T},<)$. No consistent write timestamp is concurrent with a correct or
pseudo-correct write timestamp. Thus at run-time, it is determined that a
correct write timestamp and a pseudo-correct write timestamp is an inevitable
timestamp in $({\cal T}_{c},<)$. The execution path traced in the lattice
$({\cal T}_{c},<)$ passes through these correct and pseudo-correct write
operation timestamp states.

######  Definition 11.

(View Consistency Property:) If a write operation $T(v)$ is returned to a
correct reader’s read R, it is returned to all correct readers’ read
operations that are preceded by R, assuming there are no further writes to
$R\\_init_{wi}$ after $T(v)$.

######  Definition 12.

(Total Ordering Property:) If two write operations $T(v_{1})$ and $T(v_{2})$
are seen by any two correct readers, they are seen in a same common order.

View Stability and Total Ordering properties together guarantee that all
correct readers can see all correct and pseudo-correct writes in the same
order.

Only correct and pseudo-correct writes may be returned by correct readers. A
correct reader cannot distinguish between a correct and a pseudo-correct write
operation. A pseudo-correct write operation $o_{1}(v_{1})$ timestamped
$T_{1}(v_{1})$ may lose a race due to asynchrony of process executions to a
pseudo-correct or correct write operation timestamped $T_{2}(v_{2})$ where
$T_{1}<T_{2}$, in which case $v_{1}$ is not actually returned to any read
operation and $o_{1}$ is deemed to have an invisible linearization point. The
correct and pseudo-correct writes are totally ordered by their linearization
points, and (if the Monotonicity/Total Order on Vector Timestamps Property is
satisfied) this order is (a) the total order on their timestamps, which is (b)
the total order in logical time in which these writes were performed, as also
(c) the total order in which these write operation timestamped values are
encountered in a run-time traversal of the lattice $({\cal T}_{c},<)$ and
potentially returned by HLI read operations. 666Note this this total order on
the linearization points is not uniquely defined by the natural total order in
which operations were issued to the HLI object interface, because as observed
earlier, there is a many-many mapping from the writes issued to the HLI object
interface to values written to the object.

In our characterization, we used logical time and LLOs but now present the
final definition of the Byzantine linearizable register using physical time
and HLOs. Let $v^{i}$ be the value written by the $i$th correct or pseudo-
correct write $W^{i}$, following the notation in [7]. Note that to determine
$i$, $v^{i}$ and $W^{i}$ requires knowing what happened below the HLI and
above the LLI because of the nature of pseudo-correct writes; but there is
actually no need to determine $i$, $v^{i}$, and $W^{i}$.

######  Definition 13.

(Byzantine Linearizable Register). In a system with Byzantine process
failures, an implementation of a SWMR register is linearizable if and only if
the following two properties are satisfied.

  1. 1.

Reading a current value: When a read operation R by a non-Byzantine process
returns the value $v$:

    1. (a)

if $v=v_{0}$ then no correct or pseudo-correct write operation precedes R

    2. (b)

else if $v\neq v_{0}$ then $v$ was written by the most recent correct write
operation that precedes R or by a later pseudo-correct or correct write
operation (either a pseudo-correct write operation, that precedes or overlaps
with R, or a correct write operation that overlaps R).

  2. 2.

No “new-old” inversions: If read operations R and R’ by non-Byzantine
processes return values $v^{i}$ and $v^{j}$, respectively, and R precedes R’,
then $i\leq j$.

In Definition 13, “precedes”, “overlaps”, and “later” are with respect to
physical time of HLI invocations and responses. In Case 1b, note that the most
recent correct write operation W that precedes R has its linearization point
within the physical time duration of W. Later pseudo-correct write operations
that precede R or overlap with R may have their linearization points after
their response in physical time. In particular, the most recent pseudo-correct
write operation that precedes R in physical time may have its linearization
point after its physical time duration completes and hence it may be during R
or even after R completes.

Additionally, Monotonicity/Total Order of Vector Timestamps Property, Genuine
Advance Property, View Consistency Property, and Total Ordering Property are
useful properties that overcome the drawbacks of the previous definition(s) of
Byzantine Register Linearizability discussed in Section 1.1.

##  4 The Algorithm

###  4.1 Basic Idea and Operation

Because the writer $w$ is Byzantine, a reader $i$ cannot unilaterally use the
value in its register $R\\_init_{wi}$ but needs to coordinate with other
readers. But a reader may not invoke a read operation indefinitely. So we
assume that each reader process has a reader helper thread that is always
running and participates in this coordination. A correct write operation needs
to wait for acknowledgements from the readers so that the write value is
guaranteed to get written in the algorithm data structures and stabilize, and
is not overwritten before it stabilizes. This guarantees progress by ensuring
that the most recent correct write operation advances with time. The algorithm
data structures are described in Algorithm 1. The reader helper thread is
given in Algorithm 2. $w$ is the writer process and $P$ denotes the set of $n$
readers.

The writer writes $\langle k,u\rangle$, where $u$ is the value to be written
and $k$ is a sequence number assigned by the writer, to all the reader
registers $R\\_init_{wi}$ and then waits for $n-t$ of the acknowledgement
registers $R\\_ack_{iw}$ to be written with this value.

The reader helper thread ($\forall p\in P$) loops forever. In each iteration,
it reads $R\\_init_{wp}$ and if the value overwrites the earlier value, it
increments its local logical time $s$ (the witness time) and writes
$\langle\langle k,u\rangle,s,p\rangle$ to all the registers
$R\\_witness_{pi}$. It then reads each $R\\_witness_{ip}$ and if the logical
time of an entry is larger than the previous logical time read, it stores the
value in a local variable $T\\_witness_{i}$ (if less than, or equal but the
entry is different, $i$ is marked as Byzantine). If there are at least $n-t$
$T\\_witness_{q}$ entries with identical $\langle k,u\rangle$ values then
these $T\\_witness_{q}$ entries are placed in the local set $Witness\\_Set$.
This $Witness\\_Set$ signed by $p$ is written to all $R\\_inform_{pi}$. Each
$R\\_inform_{ip}$ is read to local variable $T\\_inform_{i}$. If there are at
least $n-t$ $T\\_inform_{j}$ having identical entries $\langle\langle
k,u\rangle,s_{l},l\rangle$ for at least $n-t$ readers $l$, these
$T\\_inform_{j}$ are placed in local variable $Inform\\_Set$, which is then
written in all $R\\_final_{pi}$, and $R\\_ack_{pw}$ is updated with $\langle
k,u\rangle$. All the $R\\_final_{ip}$ are read and placed in set $Z$. All the
elements in $Z$, i.e., ($\forall i$) $R\\_final_{ip}$ are totally ordered by a
relation $\mapsto$, (to be defined in Definition 18), as will be proved in
Theorem 4. The latest element in $Z$ is identified as $Y$ via a call to
$Find\\_Latest(Z)$ and if $Y$ is different from the local $Inform\\_set$, (a)
it is written to all $R\\_final_{pi}$ and (b) $R\\_ack_{pw}$ is updated with
the common $\langle k,u\rangle$ occurring in identical $T\\_witness$ entries
$\langle\langle k,u\rangle,s_{l},l\rangle$ for $\geq$ $n-t$ values of $l$ in
all the at least $n-t$ $Witness\\_Sets$ in $Inform\\_Set$ that is $Y$.

Observe that $R\\_inform_{**}$ registers are needed to ensure that the
$R\\_final_{**}$ entries, i.e., their vector timestamps, form a total order;
otherwise if two correct processes were to concurrently write their respective
$Witness\\_Set$s into their $R\\_final$ rows, the two entries may be partially
ordered. This introduces an additional level of indirection in the algorithm.

1 Shared variables:

2 For all processes $i\in P$: $R\\_init_{wi}$: atomic SWSR register
$\leftarrow\langle 0,u_{0}\rangle$

3 For all processes $i\in P$: $R\\_ack_{iw}$: atomic SWSR register
$\leftarrow\langle 0,u_{0}\rangle$

4 For all processes $i$ and $j$ in $P$: $R\\_witness_{ij}$: atomic SWSR
register $\leftarrow\langle\langle 0,u_{0}\rangle,0,i\rangle$

5 For all processes $i$ and $j$ in $P$: $R\\_inform_{ij}$: atomic SWSR
register $\leftarrow\langle\bigcup_{k\in P}\\{\langle\langle
0,u_{0}\rangle,0,k\rangle\\}\rangle_{i}$

6 For all processes $i$ and $j$ in $P$: $R\\_final_{ij}$: atomic SWSR register
$\leftarrow\bigcup_{l\in L}\\{\langle\bigcup_{k\in P}\\{\langle\langle
0,u_{0}\rangle,0,k\rangle\\}\rangle_{l}\\}$, where $|L|\geq n-t\wedge
L\subseteq P$

7 Local variables:

8 variable of $w$: $c$ $\leftarrow$ 0

9 variable of $i\in P$: $s$ $\leftarrow$ 0

10 variables of $j\in P$: For all processes $i\in P$: $T\\_witness_{i}$
$\leftarrow$ $\langle\langle 0,u_{0}\rangle,0,i\rangle$

11 variables of $j\in P$: For all processes $i\in P$: $T\\_inform_{i}$
$\leftarrow$ $\langle\bigcup_{k\in P}\\{\langle\langle
0,u_{0}\rangle,0,k\rangle\\}\rangle_{i}$

12 variable of $j\in P$: $Witness\\_Set$ $\leftarrow$ $\langle\bigcup_{k\in
P}\\{\langle\langle 0,u_{0}\rangle,0,k\rangle\\}\rangle_{p}$

13 variable of $j\in P$: $Inform\\_Set$ $\leftarrow$ $\bigcup_{l\in
L}\\{\langle\bigcup_{k\in P}\\{\langle\langle
0,u_{0}\rangle,0,k\rangle\\}\rangle_{l}\\}$, where $|L|\geq n-t\wedge
L\subseteq P$

14

15WRITE($u$):

16 $c=c+1$

17 $W(\langle c,u\rangle)$

18 return

19

20READ():

21 $R()$

22 return the value returned by the $R$ call

23

24$W(\langle k,u\rangle)$:

25 for  _every process $i\in P$_ do

26 $R\\_init_{wi}=\langle k,u\rangle$

27$d=0$

28 while  _$d <n-t$_ do

29 for  _each new $\langle k,u\rangle$ in $R\\_ack_{iw}$ among $R\\_ack$
registers_ do

30 $d=d+1$

31

32return done

33$R()$:

34 execute one iteration of the reader helper thread, Algorithm 2

35 return the value last written in $R\\_ack_{pw}$ in that execution

Algorithm 1 Constructing a linearizable SWMR atomic register. Code at process
$p$.

1 reader helper thread:

2 while  _$true$_ do

3 if  _$R\\_init_{wp}(=\langle k,u\rangle)$ is newly written (overwrites a
different value) _ then

4 $s=s+1$

5 for  _each $i\in P$_ do

6 $R\\_witness_{pi}\leftarrow\langle\langle k,u\rangle,s,p\rangle$

7

8 for  _each $i\in P$_ do

9 if  _$R\\_witness_{ip}(=\langle\langle k,u\rangle,s^{\prime},i\rangle)$ is
newly written, i.e., $s^{\prime}>T\\_witness_{i}.s$ _ then

10 $T\\_witness_{i}\leftarrow\langle\langle k,u\rangle,s^{\prime},i\rangle$

11 else if  _$s^{\prime}
<T\\_witness_{i}.s\vee(s^{\prime}=T\\_witness_{i}.s\wedge\langle
k,u\rangle(Line~{}\ref{line:ku})\neq T\\_witness_{i}.\langle k,u\rangle)$_
then

12 (optionally) mark process $i$ as Byzantine

13

14

15 if  _$\exists$ $\geq$ $n-t$ latest elements $\langle\langle
k,u\rangle,*,q\rangle$ $T\\_witness_{q}$ _ then

16 add all these $\geq n-t$ elements $T\\_witness_{q}$ to the emptyset
$Witness\\_Set$

17 for  _each $i\in P$_ do

18 $R\\_inform_{pi}\leftarrow\langle Witness\\_Set\rangle_{p}$

19 for  _each $i\in P$_ do

20 $T\\_inform_{i}\leftarrow R\\_inform_{ip}$

21 if  _$\exists\geq n-t$ processes $j$ (i.e., $T\\_inform_{j}$) having
identical entries $\langle\langle k,u\rangle,s_{l},l\rangle$ for $\geq n-t$
processes $l$_ then

22 Place the $\geq n-t$ $T\\_inform_{j}$ in emptyset $Inform\\_Set$

23 for  _each $i\in P$_ do

24 $R\\_final_{pi}\leftarrow Inform\\_Set$

25 $R\\_ack_{pw}\leftarrow\langle k,u\rangle$

26

27 $Z\leftarrow\emptyset$

28 for  _each $i\in P$_ do

29 $Z\leftarrow Z\cup\\{R\\_final_{ip}\\}$

30

31 $Y\leftarrow Find\\_Latest(Z)$

32 if  _$Y\neq Inform\\_Set$_ then

33 for  _each $i\in P$_ do

34 $R\\_final_{pi}\leftarrow Y$

35 $R\\_ack_{pw}\leftarrow$ the common $\langle k,u\rangle$ value occurring in
identical $T\\_witness$ entries $\langle\langle k,u\rangle,s_{l},l\rangle$ for
$\geq n-t$ values of $l$ in all the $\geq n-t$ $Witness\\_Set$s in
$Inform\\_Set$ that is $Y$

36

37$Find\\_Latest(Z)$:

38 while  _$|Z| >1$_ do

39 let $Z_{i},Z_{j}$ be any two elements of $Z$; $Z_{i}$ ($Z_{j}$) has $\geq
n-t$ entries and is the $Inform\\_Set$ of some reader

40 Let $Q_{i}$ ($Q_{j}$) be the set of $\geq n-t$ processes that have
identical $T\\_witness$ entries in the $\geq n-t$ $Witness\\_Set$s in
$Inform\\_Set$ that is $Z_{i}$ ($Z_{j}$). For the $\geq n-2t$ readers $q\in
Q_{i}\cap Q_{j}$, let $e^{i}_{q}=\langle\langle k,u\rangle,s^{i}_{q},q\rangle$
and $e^{j}_{q}=\langle\langle k^{\prime},u^{\prime}\rangle,s^{j}_{q},q\rangle$
be these $T\\_witness$ entries in the $\geq n-t$ $Witness\\_Set$s in the
$Inform\\_Set$s that are $Z_{i}$ and $Z_{j}$, resp.

41

42 if  _$s^{i}_{q}\geq s^{j}_{q}$ for any/all processes $q$_ then

43 $Z\leftarrow Z\setminus Z_{j}$

44 else

45 $Z\leftarrow Z\setminus Z_{i}$

46

47return(element in $Z$)

Algorithm 2 Reader helper thread for constructing a linearizable SWMR atomic
register. Code at process $p$.

###  4.2 Instantiating Framework Definitions in the Algorithm

A reader sees the value written by the most recent correct write operation
that precedes the read operation, or it may return a later written value that
is written by a correct or pseudo-correct write operation. In the context of
our algorithm, the definitions of a correct write operation, a potential
pseudo-correct write operation, and a pseudo-correct write operation apply
directly. A write operation stabilizes (Definition 16) if the value is
potentially returnable by a correct read operation, i.e., when it is written
to $R\\_final_{p*}$ for all values of $*$ (in the form of an $Inform\\_Set$
containing the required number of correctly signed $Witness\\_Set$s). A
correct write operation always stabilizes whereas a potential pseudo-correct
write operation may stabilize depending on the outcome of concurrency data
races and behavior of the writer and Byzantine readers.

A correct write operation always stabilizes because it waits for $n-t$
acknowledgements in $R\\_ack_{*w}$ before completion, thereby allowing the
value it has written to $R\\_final_{p*}$ to be eligible for being returned by
a read operation. A correct write operation corresponds to a sufficient
condition for stabilization. Writing the same value to $n-t$ readers’
$R\\_init_{wi}$ in a potential pseudo-correct operation is a necessary
condition for stabilization. For the potential pseudo-correct write operation
to become a pseudo-correct write operation, the Byzantine readers need to
collaborate to allow the value being written to the other correct readers’
$R\\_init_{wi}$ to stabilize. Recall that a pseudo-correct write operation may
have the value written to the readers’ $R\\_init_{wi}$ registers across
multiple prior write operations. The set of correct and pseudo-correct writes
is exactly the set of writes whose values stabilize (follows from Theorem 3).

We show (Corollary 2) that the set of all values that stabilize are totally
ordered by the logical times of their “reading” from the readers’ registers
$R\\_init_{w*}$. Specifically, we use $\overline{T}$ to denote the vector of
logical times of reading a value $\langle k,u\rangle$ from $R\\_init_{wi}$ by
the various readers $i$, and we denote this total order relation $\mapsto$.
The notation $\overline{T}$ as opposed to the timestamp vector $T$ we
introduced in Section 3 is useful because not all readers may report the
logical times of their reading $u$ from $R\\_init_{w*}$. Thus
$\overline{T}(u)$ may not have all $n$ components whereas $T(u)$ has all $n$
components. Roughly speaking, the $\overline{T_{1}}\mapsto\overline{T_{2}}$
relation is equivalent to $T_{1}<T_{2}$; the formal definition of $\mapsto$ is
given later in Definition 18. We will also abbreviate $\langle
k,v\rangle.\overline{T}\mapsto\langle
k^{\prime},v^{\prime}\rangle.\overline{T}$ as simply $\langle
k,v\rangle\mapsto\langle k^{\prime},v^{\prime}\rangle$. The total order
$\mapsto$ on timestamp vectors of values that stabilize is the total order on
the linearization points of correct and pseudo-correct write operations.777As
noted in Section 3, the total order in which the values stabilize may be
different from this total order because of concurrency races for stabilization
between a pseudo-correct write $T_{1}(u_{1})$ and a pseudo-correct or correct
write $T_{2}(u_{2})$, where $T_{1}<T_{2}$. If $T_{2}(u_{2})$ stabilizes before
$T_{1}(u_{1})$, the write of $u_{1}$ will have a invisible linearization point
as it will not be returned to any correct read operation. This follows from
the no “new-old” inversions clause in Theorem 8.

More than one value can stabilize as part of the same HLO write operation.
This can happen when, for example, some of the readers’ registers could have
been written to in earlier Write operations or a HLO invocation-response of a
Byzantine write contains multiple pseudo-correct write operations. For any
pair of values that stabilize, this total order $\mapsto$ between them
satisfies the Genuine Advance Property if $n>3t$, as we will prove in Theorem
5.

With the introduction of the $\mapsto$ relation, the definition of register
linearizability (Definition 2) is adapted to the algorithm by rephrasing the
No ‘‘new-old’’ inversions property as follows.

######  Definition 14.

(Byzantine Linearizabile Register for the algorithm). In a system with
Byzantine process failures, an implementation of a SWMR register is
linearizable if and only if the following two properties are satisfied.

  * •

Reading a current value: When a read operation R by a non-Byzantine process
returns the value $v$:

    * –

if $v=v_{0}$ then no correct or pseudo-correct write operation precedes R

    * –

else if $v\neq v_{0}$ then $v$ was written by the most recent correct write
operation that precedes R or by a later pseudo-correct or correct write
operation (either a pseudo-correct write operation, that precedes or overlaps
with R, or a correct write operation that overlaps R).

  * •

No “new-old” inversions: If read operations R and R’ by non-Byzantine
processes return values $\langle k,v\rangle$ and $\langle
k^{\prime},v^{\prime}\rangle$, respectively, and R precedes R’, then $\langle
k,v\rangle.\overline{T}\stackrel{{\scriptstyle=}}{{\mapsto}}\langle
k^{\prime},v^{\prime}\rangle.\overline{T}$.

##  5 Correctness Proof

######  Definition 15.

The witness set of an $Inform\\_Set$ $IS$ that is formed, $WS(IS)$, is the
maximal set of at least $n-t$ $T\\_witness$ entries $\langle\langle
k,u\rangle,s_{l},l\rangle$ common to the at least $n-t$ elements
($Witness\\_Set$s) of the $Inform\\_Set$ $IS$.

Those at least $n-t$ identical entries in the intersection of the at least
$n-t$ $Witness\\_Set$s in the $Inform\\_Set$ $IS$ form $WS(IS)$.

######  Definition 16.

The field/value $\langle k,u\rangle$ common to all the entries in the $WS(IS)$
witness set of an inform set $IS$ is defined to stabilize when the
$Inform\\_Set$ $IS$ containing correctly signed $Witness\\_Set$s is written to
all the $R\\_final_{pi}$ for some process $p$.

######  Definition 17.

For a value $\langle k,u\rangle$ that stabilizes with $Inform\\_Set$ $IS$,
$\langle k,u\rangle.\overline{T}$ is the set of tuples $(l,s_{l})$ for all the
at least $n-t$ reader processes $l$ for all the at least $n-t$
$T\\_witness_{l}$ entries $\langle\langle k,u\rangle,s_{l},l\rangle$ in
$WS(IS)$.

Only a value that stabilizes may be returned by a reader.

######  Theorem 1.

A correct write operation is guaranteed to stabilize provided $n>2t$.

###### Proof.

A correct write operation writes the same $\langle k,u\rangle$ to
$R\\_init_{wp}$ for all correct $p$ and will not complete unless it gets $n-t$
acks in $R\\_ack_{pw}$. It may get $t$ acks from Byzantine processes but as
$n>2t$, it will need an ack from at least one correct process. A correct
process $p$ gives the ack only after it has written the value to
$R\\_final_{p*}$, i.e., when the value has stabilized. We now show that at
least one correct process will have the value stabilize, before which the
value written to the $R\\_init_{w*}$ will not be overwritten.

For all correct $p$, the witness timestamps are correctly written to
$R\\_witness_{p*}$. At least $n-t$ correct reader helper threads of correct
processes $p$ will eventually read from $R\\_witness_{*p}$, form their
$Witness\\_Set$s, sign those sets and write to $R\\_inform_{p*}$. Some first
correct reader thread $p$ will eventually read from $R\\_inform_{*p}$ and have
at least $n-t$ $T\\_inform_{j}$ having identical entries $\langle\langle
k,u\rangle,s_{l},l\rangle$ for at least $n-t$ processes $l$. It will thus be
able to form its $Inform\\_Set$, then write it to all $R\\_final_{p*}$, and
will then write $\langle k,u\rangle$ to $R\\_ack_{pw}$ after which the correct
write operation will complete. Thus, $\langle k,u\rangle$ is guaranteed to
have stabilized as the $R\\_init_{wi}(\forall i)$ will not be overwritten
until then. ∎

######  Theorem 2.

A potential pseudo-correct write operation may stabilize provided $n>2t$.

###### Proof.

A value written by a potential pseudo-correct operation writes the same value
to $n-t$ readers’ $R\\_init_{wp}$, i.e., to at least $n-2t$ correct readers’
$R\\_init_{wp}$, across possibly multiple prior write operations and the
current write operation. These reader processes write that value, if not
overwritten, to $R\\_witness_{*p}$. Let the $t$ Byzantine processes $b$ read
the value from their $R\\_witness_{*b}$ and thereafter behave as though the
value had been written to their $R\\_init_{wp}$ and thenceforth behave
correctly. There is now a way that the value may stabilize if the Byzantine
writer does not overwrite the values in $R\\_init_{wp}$ ($\forall p$) until at
least one process $q$ forms its $Inform\\_Set$ of correctly signed
$Witness\\_Set$s for that value and writes the $Inform\\_Set$ to
$R\\_final_{q*}$. This condition will be satisfied as per the logic in the
proof of Theorem 1 (although the writer need not wait for $n-t$ acks) as now
the Byzantine reader processes $b$ are collaborating and behaving like correct
reader processes after having read the value set aside for them in
$R\\_witness_{*b}$. ∎

######  Theorem 3.

If a value stabilizes, it must have been written by a correct write operation
or by a potential pseudo-correct write operation.

###### Proof.

A correct write operation stabilizes (Theorem 1). So we need to only prove the
following contrapositive, namely that if a write is not a potential pseudo-
correct write operation, it will not stabilize.

If a write is not a potential pseudo-correct operation, it is not written to
at least $n-2t$ correct processes’ $R\\_init_{wi}$ across possibly multiple
write operations. Then there is no way a $Witness\\_Set$ of at least $n-t$
$T\\_witness$ entries can form at at least $n-t$ processes, and hence an
$Inform\\_Set$ of $n-t$ correctly signed $Witness\\_Set$s cannot form at any
process, correct or Byzantine, and cannot be written to any $R\\_final_{p*}$.
If a Byzantine process attempts to write a fake $Inform\\_Set$ in
$R\\_final_{p*}$, that will be detected by correct processes as that
$Inform\\_Set$ written in $R\\_final_{p*}$ will not pass the signature test.
Hence that value is deemed to not have stabilized. ∎

######  Lemma 1.

The View Consistency Property (Definition 11) is satisfied by Algorithm 1.

###### Proof.

If one correct process $p$ returns a value $v$ of write $T(v)$, it must have
written the $Inform\\_Set$ corresponding to this $T(v)$ to all
$R\\_final_{p*}$. If there are no further writes to $R\\_init_{w*}$ beyond
$T(v)$ by the writer, all correct readers’ read operations issued after $p$ is
returned $v$ will return $v$, based on the pseudo-code. Hence View Consistency
is satisfied. ∎

If an $Inform\\_Set$ $IS1$ is formed at reader $x$, it has read from
$R\\_inform_{*x}$ at least $n-t$ $Witness\\_Set$s having at least $n-t$
identical entries across those $Witness\\_Set$s. Likewise if an $Inform\\_Set$
$IS2$ is formed at reader $y$. (Recall that those at least $n-t$ identical
entries in the intersection of the at least $n-t$ $Witness\\_Set$s in the
$Inform\\_Set$ $IS$ form $WS(IS)$.) $x$ and $y$ write $Inform\\_Set$ $IS1$ and
$Inform\\_Set$ $IS2$ to $R\\_final_{x*}$ and $R\\_final_{y*}$, respectively.
When a third reader $z$ reads these two values and as part of
$Find\\_Latest(Z)$ invocation compares $IS1$ and $IS2$ ($Z$ and $Z^{\prime}$),

  * •

there are at least $n-2t$ reader witness timestamps common to $WS1(=WS(IS1))$
and $WS2(=WS(IS2))$. As the corresponding processes provided witnesses to both
witness sets, any such process would have done so first for $WS1$ and then for
$WS2$ or vice-versa.

  * •

there are at least $n-2t$ processes $p$ that provided (signed)
$Witness\\_Set$s written to $R\\_inform_{p*}$ that formed part of both $IS1$
and $IS2$. Any such process $p$ would have written its $Witness\\_Set$ that
formed part of $IS1$ to $R\\_Inform_{p*}$ before it wrote its $Witness\\_Set$
that formed part of $IS2$ or vice-versa.

######  Observation 1.

A correct process forms its successive $Witness\\_Set$s only in non-decreasing
order of source witness timestamps for the at least $n-2t$ common witnesses as
it writes these $Witness\\_Set$s to $R\\_inform$.

Let $p$ sign $Witness\\_Set$ $WS1^{\prime}$ that is part of $IS1$. Then let
$p$ sign $WS2^{\prime}$ that is part of $IS2$. ($p$ is one of the at least
$n-2t$ processes that sign $WS1^{\prime}\in IS1$ and $WS2^{\prime}\in IS2$,
assuming $n>2t$. Note that these at least $n-2t$ processes may not include any
correct process.) For all correct $p$, we have the property that all the at
least $n-2t$ witnesses common to $IS1$ and $IS2$ have a higher or equal
witness timestamp in $IS2$ than in $IS1$. Up to $t$ Byzantine processes $p$
can sign $WS1^{\prime}$ that is part of $IS1$ and $WS2^{\prime}$ that is
intended to be part of $IS2$ such that some of the common witness timestamps
common to $IS1$ and $IS2$ will have a smaller witness timestamp in $IS2$ than
in $IS1$ (while some will have a greater or equal witness timestamp in $IS2$
than in $IS1)$. Such $IS1$ and $IS2$, which require a quorum of at least $n-t$
signed $Witness\\_Set$s having identical $T\\_witness$ entries $\langle\langle
k,u\rangle,s_{l},l\rangle$ for $\geq$ $n-t$ processes $l$ will form at any
correct or Byzantine process only if $n-t\leq t$, ie., $n\leq 2t$. This is
because the $t$ Byzantine processes $p$ would be using fake (out-of-order)
witness timestamp entries for at least one of $WS1^{\prime}$ and
$WS2^{\prime}$. To prevent such a quorum $IS1$ or $IS2$ from forming, we
require $n>2t$.

######  Definition 18.

Given $WS1(=WS(IS))$ and $WS2(=WS(IS^{\prime}))$, $WS1\mapsto WS2$ iff for the
at least $n-2t$ readers $z$ that witnessed values in both $WS1$ and $WS2$,
$z$’s $WS1$ timestamp $\leq$ $z$’s $WS2$ timestamp and there is at least one
reader $z^{\prime}$ that witnessed values in both $WS1$ and $WS2$ and
$z^{\prime}$’s $WS1$ timestamp $<$ $z^{\prime}$’s $WS2$ timestamp.

If for any $z$ that witnessed both $WS1$ and $WS2$ the witness timestamps are
equal, then $WS1$ and $WS2$ have the same $\langle k,u\rangle$ value.

If $WS(IS)\mapsto WS(IS^{\prime})$, we also interchangeably say that for the
corresponding values, $\langle k,u\rangle\mapsto\langle
k^{\prime},u^{\prime}\rangle$ and $\langle
k,u\rangle.\overline{T}\mapsto\langle
k^{\prime},u^{\prime}\rangle.\overline{T}$.

######  Definition 19.

Given distinct $WS1(=WS(IS))$ and $WS2(=WS(IS^{\prime}))$, $WS1\|WS2$ iff
$WS1\not\mapsto WS2\wedge WS2\not\mapsto WS1$.

######  Observation 2.

If $WS1||WS2$ then of the at least $n-2t$ processes that provided witness
timestamps to both $WS1$ and $WS2$ there is a process $a$ whose $WS1$ witness
timestamp $ta1$ $<$ its $WS2$ witness timestamp $ta2$ and there is a process
$b$ whose $WS2$ witness timestamp $tb2$ $<$ its $WS1$ witness timestamp $tb1$.

######  Theorem 4.

For $Inform\\_Set$s $IS1$ and $IS2$ at any two (possibly different) reader
processes, $WS(IS1)\mapsto WS(IS2)\vee WS(IS2)\mapsto IS(IS1)$, i.e.,
$WS(IS1)\not\|\,WS(IS2)$, provided $n>2t$.

###### Proof.

We prove by contradiction. Assume $WS(IS1)\|WS(IS2)$. Given $WS1(=WS(IS1))$
and $WS2(=WS(IS2))$, from Observation 2 there is a process $a$ whose $WS1$
witness timestamp $ta1$ $<$ its $WS2$ witness timestamp $ta2$ and there is a
process $b$ whose $WS2$ witness timestamp $tb2$ $<$ its $WS1$ witness
timestamp $tb1$. As noted earlier, a process $p$ that provided witness set
inputs to both $IS1$ and $IS2$ by writing to $R\\_inform_{p*}$ could have
provided its input for $IS1$ first and then for $IS2$ or vice-versa.

Without loss of generality assume $p$ provides the witness set input for $IS1$
before providing the witness set input for $IS2$. Then consider the process
$b$’s witness timestamps. So let process $p$ provide $b$’s $WS1$ witness
timestamp $tb1$ (along with other $WS1$ witness timestamps) which is written
to $R\\_inform_{p*}$. If $p$ is correct, it will not consider/input $b$’s
$WS2$ witness timestamp $tb2$ as $tb2<tb1$. Only up to $t$ Byzantine processes
can process/input $b$’s $WS2$ timestamp $tb2$ after $tb1$ but, as $n>2t$, that
falls short of the $n-t$ threshold required to form an $Inform\\_Set$ (of
signed $Witness\\_Set$s) at any process. So $IS2$ and $WS2$ will not exist.

Likewise if we assume the process $p$ provides its witness set input for $IS2$
before providing its witness set input for $IS1$, then consider process $a$’s
witness timestamps. Let process $p$ provide $a$’s $WS2$ witness timestamp
$ta2$ (along with other $WS2$ witness timestamps) which is written to
$R\\_inform_{p*}$. If $p$ is correct, it will not consider/input $a$’s $WS1$
witness timestamp $ta1$ as $ta1<ta2$. Only up to $t$ Byzantine processes can
process/input $a$’s $WS1$ witness timestamp $ta1$ after $ta2$. But as $n>2t$,
each correct or Byzantine process will fall short of the $n-t$ threshold
required to form an $Inform\\_Set$ (of signed $Witness\\_Set$s). So $IS1$ and
$WS1$ will not exist.

Thus if $IS1$ and $IS2$ form, all processes that provide input witness
timestamps to both $WS1$ and $WS2$ provide first to $WS1$ and then to $WS2$ or
all provide first to $WS2$ and then to $WS1$. Thus $WS1\not\|WS2$. ∎

######  Definition 20.

(Genuine Advance Property in the algorithm:) When $WS1(=WS(IS1))\mapsto
WS2(=WS(IS2)$, $WS2$ is a genuine advance over $WS1$ if there is at least one
correct reader process $i$ such that $i$’s $WS1$ witness timestamp $<$ $i$’s
$WS2$ witness timestamp.

Only value $\langle k,v\rangle$ corresponding to an $Inform\\_Set$ that is
written to $R\\_final_{p*}$ could be returned by a correct process if the
signed $Witness\\_Set$s in that $Inform\\_Set$ pass the signature test. The
Genuine Advance Property is useful because each new value returned by a
correct reader is a new value genuinely written to at least one correct reader
$i$’s $R\\_init_{wi}$ and not falsely reported by a Byzantine reader, in
addition to that same value being the most recent value in a total of $n-t$
readers $j$’s $R\\_init_{wj}$ registers as per $\langle
k,u\rangle.\overline{T}$. Another very important reason why this property is
important is explained after Theorem 6. Definition 20 is the counterpart of
Definition 9.

######  Theorem 5.

Algorithm 1 satisfies the Genuine Advance Property if $n>3t$.

###### Proof.

If $WS1(=WS(IS1))\mapsto WS2(=WS(IS2))$, then in order that the Genuine
Advance Property holds, there is at least one correct reader process $i$ such
that $i$’s $WS1$ witness timestamp $<$ $i$’s $WS2$ witness timestamp. For this
to happen, we require that two quora of size $n-2t$, which is the minimum
number of correct processes having $T\\_witness$ entries in $WS1$ and $WS2$,
intersect among the set of correct processes (having size $\geq n-t$). Thus,

$2(n-2t)>n-t\Longrightarrow n>3t$

∎

Only value $\langle k,v\rangle$ corresponding to an $Inform\\_Set$ that is
written to $R\\_final_{p*}$ could be returned by a correct process if the
signed $Witness\\_Set$s in that $Inform\\_Set$ pass the signature test. From
Theorem 4, all the $\langle k,v\rangle.\overline{T}$ form a total order based
on $\mapsto$. This leads to the following corollary.

######  Corollary 1.

The partial vector timestamps $\langle k,u\rangle.\overline{T}$ of $\langle
k,u\rangle$ values that stabilize are totally ordered.

Recall that the $\langle k,u\rangle.\overline{T}$ are partial vectors having
$\geq n-t$ entries because not all $n$ readers’ entries may be present in the
$Witness\\_Set$s of the $Inform\\_Set$. Let those entries that are not
reported have a timestamp value denoted $\perp$ in $\overline{T}$.

######  Theorem 6.

The Monotonicity/Total Order of Vector Timestamps of Stabilized Writes
Property (Definition 8) and the Genuine Advance Property (Definition 9) are
satisfied by Algorithm 1, provided $n>2t$ and $n>3t$, respectively.

###### Proof.

For every partial timestamp vector $\overline{T}$ of a value that stabilizes
in the algorithm, we construct a full timestamp vector $T$ as follows. Let
$\overline{T}_{current}$ and $T_{current}$ be the corresponding timestamps of
the current value that has stabilized. Let $\overline{T}_{next}$ be the
smallest timestamp greater than $\overline{T}_{current}$ to stabilize and let
$T_{next}$ denote the corresponding full vector timestamp we construct.

Initialize: $\overline{T}_{current},T_{current}\leftarrow[0,\ldots 0]$
loop:
Identify $\overline{T}_{next}$
// Invariant 1: $\overline{T}_{current}\mapsto\overline{T}_{next}$
$\forall
i\,|\,\overline{T}_{next}[i]\neq\perp:T_{next}[i]\leftarrow\overline{T}_{next}[i]$
$\forall i\,|\,\overline{T}_{next}[i]=\perp:T_{next}[i]\leftarrow
T_{current}[i]$
// Invariant 2: $T_{current}<T_{next}$
$T_{current}\leftarrow T_{next}$,
$\overline{T}_{current}\leftarrow\overline{T}_{next}$
endloop

Let $\overline{{\cal T}}$ denote the (total order) set of $\langle
k,u\rangle.\overline{T}$ partial vector timestamps for values $\langle
k,u\rangle$ that have stabilized. Let ${\cal T}^{f}$ denote the set of
corresponding full vector timestamps.

######  Theorem 7.

$({\overline{\cal T}},\mapsto)$ is isomorphic to $({\cal T}^{f},<)$.

###### Proof.

With respect to Invariant 1,

  * •

let $j$ be any index such that
$\overline{T}_{current}[j]<\overline{T}_{next}[j]$,

  * •

let $k$ be any index such that
$\overline{T}_{current}[k]=\overline{T}_{next}[k]\neq\perp$,

  * •

let $l$ be any index such that
$\overline{T}_{current}[l]=\overline{T}_{next}[l]=\perp$,

  * •

let $a$ be any index such that $\overline{T}_{current}[a]\neq\perp$ and
$\overline{T}_{next}[a]=\perp$,

  * •

let $b$ be any index such that $\overline{T}_{current}[b]=\perp$ and
$\overline{T}_{next}[b]\neq\perp$.

Invariant 2 follows because of the following.

  * •

For all $j$, $T_{current}[j]<T_{next}[j]$,

  * •

for all $k$, $T_{current}[k]=T_{next}[k]$,

  * •

for all $l$, $T_{current}[l]=T_{next}[l]$,

  * •

for all $a$, $T_{current}[a]=T_{next}[a]$,

  * •

for all $b$, $T_{current}[b]\leq T_{next}[b]$.

From Invariant 1, there must exist at least one index $j$, or one index $b$
such that $T_{current}[b]<T_{next}[b]$. Hence $T_{current}<T_{next}$ and
Invariant 2 holds.

In order to satisfy the Genuine Advance of Timestamps Property (Definition 9)
for $T_{current}<T_{next}$, there must exist a correct process index $j$, or
$b$ satisfying $T_{current}[b]<T_{next}[b]$, in the analysis above. This
requires 2 quora of $n-2t$ processes to intersect among the set of correct
processes, requiring $n>3t$ as shown in the proof of Theorem 5.

The theorem follows from Invariants 1 and 2. ∎

As $(\overline{{\cal T}},\mapsto)$ is a total order from the proof of Theorem
4, Theorem 7 implies that $({\cal T}^{f},<)$ is also a total order. The
Monotonocity/Total Order of Vector Timestamps of Stabilized Writes Property is
thus satisfied, and requires $n>2t$ as Theorem 4 also requires it.

From the proof of Theorem 7, the Genuine Advance of Timestamps Property over
$({\cal T}^{f},<)$ is satisfied by the algorithm, provided $n>3t$. ∎

Note that when $3t\geq n>2t$, $n-t$ different values written to different
correct readers’ $R\\_init$ registers can be ordered/stabilized in any
permutation by the Byzantine processes but in any given execution, only one
permutation can occur. But as the Genuine Advance Property is not satisfied
when $n\leq 3t$ as is this case, the Byzantine readers can cause any arbitrary
sequence of unbounded length (with each member of the sequence being distinct
from the one before it) of these $n-t$ different values to successively
stabilize and be returned by correct readers. This is an unbounded sequence of
fake writes that can be returned to reads. This is another reason why the
Genuine Advance Property is important.

An $Inform\\_Set$ that is formed at any process $p$ is written to
$R\\_final_{p*}$ and thus stabilizes, by Definition 16. We now have the
following corollary to Theorems 4 and 5.

######  Corollary 2.

The set of all values that stabilize is totally ordered by $\mapsto$ provided
$n>2t$ (from Theorem 4). The Genuine Advance Property is satisfied provided
$n>3t$ (from Theorem 5).

######  Theorem 8.

Algorithm 1 implements a linearizable SWMR register using SWSR registers,
provided $n>3t$.

###### Proof.

We show that the value returned by a read operation satisfies “reading a
current value” and “no new-old inversions”.

  * •

Reading a current value: From the algorithm pseudo-code, a read R returns the
value $\langle k,u\rangle$ such that $\langle k,u\rangle.\overline{T}$ is the
latest value ordered by $\mapsto$ that has stabilized, up until some point of
time during R. By Theorem 3, such a value must have been written by a correct
write operation or by a pseudo-correct write operation that has stabilized.
From Theorem 1, a correct write always stabilizes before the write operation
returns/completes. Therefore, $\langle k,u\rangle$ will be the value written
by the most recent correct write operation that precedes R, or by a later
write operation. The later write operation may be (i) a correct write
operation that overlaps with R, or (ii) a pseudo-correct write operation that
has stabilized (and which precedes or overlaps R). Thus a current value is
read.

  * •

No “new-old” inversions: Let read R by $i$ return $\langle k,u\rangle$ and let
read R’ by $j$ return $\langle k^{\prime},u^{\prime}\rangle$, where R precedes
R’. R will write $\langle k,u\rangle$ in $R\\_final_{i*}$ before returning. R’
will read from $R\\_final_{*j}$, add these elements to $Z$ and invoke
$Find\\_Latest(Z)$ which will return the most recent value $\langle
k,u\rangle^{max}$ as per $\mapsto$. It is guaranteed that if $\langle
k,u\rangle^{max}\neq\langle k,u\rangle$ then $\langle
k,u\rangle.\overline{T}\mapsto\langle k,u\rangle^{max}.\overline{T}$ because
all the values in $Z$ are totally ordered by $\mapsto$ (Theorem 4, Corollary
2) and from Definition 18, $\langle k,u\rangle.\overline{T}\mapsto\langle
k,u\rangle^{max}.\overline{T}$ implies that the write of $\langle
k,u\rangle^{max}$ had greater (or equal) witness timestamps than the write of
$\langle k,u\rangle$ for the at least $n-2t$ common processes that witnessed
both writes. The value $\langle k^{\prime},u^{\prime}\rangle$ returned by R’
is $\langle k,u\rangle^{max}$. Thus there are no inversions.

The Genuine Advance Property implicitly needed requires $n>3t$ (Theorem 5). ∎

Let correct reader $i$ return $\langle k,u\rangle$ to R(i,1) and return
$\langle k^{\prime},u^{\prime}\rangle$ to R(i,2), where R(i,1) precedes
R(i,2). Let correct reader $j$ return $\langle k^{\prime},u^{\prime}\rangle$
to R(j,1) and let it then issue R(j,2), where R(j,1) precedes R(j,2). As the
register is Byzantine linearizable (Theorem 8), from the values returned to
$i$, we have $\langle k,u\rangle.\overline{T}\mapsto\langle
k^{\prime},u^{\prime}\rangle.\overline{T}$. If R(j,2) were to return $\langle
k,u\rangle$, $\langle k^{\prime},u^{\prime}\rangle.\overline{T}\mapsto\langle
k,u\rangle.\overline{T}$ which leads to a contradiction. Hence R(j,2) must
return $\langle k^{\prime},u^{\prime}\rangle$ or a value with a higher
timestamp vector $\overline{T}$. Thus, the Total Ordering Property cannot be
violated by the algorithm. This logic along with Theorem 5 about the Genuine
Advance Property, implicitly needed for linearization, gives the following
corollary.

######  Corollary 3.

The Total Ordering property (Definition 12) of values returned by correct
readers is satisfied, provided $n>3t$.

As stated in Section 2, a SWMR register supports Byzantine linearizable
executions because before every read operation of a correct process, one can
add a corresponding Byzantine write in the linearization [4]. Next, we
elaborate on this to give a linearization of an execution to show that the
SWMR Byzantine linearizable register we constructed supports Byzantine
linearizability of executions. First, read operations of correct readers are
linearized in the order of the return values, as per the $\mapsto$ relation.
Then an update of a value $\langle k,v\rangle$ by the Byzantine writer is
added just before the first read operation that reads that value. In general,
the value returned by a read operation is based on the values written by one
or more than one HLI write operation as the writer is Byzantine. Further, one
HLI write operation by the Byzantine writer may result in different read
values being returned by multiple correct readers. To differentiate among the
multiple updates of different values over time to the SWMR register, we treat
each update, which has stabilized, as an independent Byzantine (correct or
pseudo-correct) write operation, associated with its vector timestamp.

######  Theorem 9.

The SWMR Byzantine linearizable register implemented by Algorithm 1 satisfies
Byzantine linearizability of executions.

###### Proof.

Let $L_{R}$ be a linearization of the correct readers’ read operations such
that (i) the local order of reads at each such reader is preserved, and (ii)
if read R returns $\langle k,v\rangle$, read R’ returns $\langle
k^{\prime},v^{\prime}\rangle$, and $\langle k,v\rangle.\overline{T}$ $\mapsto$
$\langle k^{\prime},v^{\prime}\rangle.\overline{T}$ then R precedes R’ in
$L_{R}$.

When $\langle k,v\rangle$ is returned by a read, the latest write operation to
which any of the witness timestamps in $\langle k,v\rangle.\overline{T}$
belongs is denoted as $latest\\_W({\tt R})$. In the linearization $L_{R}$,
place a (Byzantine) write operation writing a value $\langle k,v\rangle$ and
assigned timestamp $\langle k,v\rangle.\overline{T}$ immediately before the
first read operation R in $L_{R}$ that reads $\langle k,v\rangle$ – this is
one of the possibly multiple Byzantine write operations corresponding to the
write operation $latest\\_W({\tt R})$.

The resulting linearization is seen to be a Byzantine linearization that
considers all the read operations of correct readers, and includes some
Byzantine write operations. In the extreme case, before every correct read
operation in $L_{R}$, we add a corresponding Byzantine write operation. ∎

Additionally, the algorithm satisfies Monotonicity/Total Order of Stabilized
Vector Timestamps (Def. 8 & Theorem 6, $n>2t$), Genuine Advance of Timestamps
(Def. 9 & Theorem 6, $n>3t$), View Consistency (Def. 11 & Lemma 1, $n>2t$),
Total Ordering (Def. 12 & Corollary 3, $n>3t$).

### Space Complexity

The algorithm uses $3n^{2}$ shared SWSR registers: $n^{2}$ $R\\_witness$
registers of size $O(1)$, $n^{2}$ $R\\_inform$ registers of size $O(n)$,
$n^{2}$ $R\\_final$ registers of size $O(n^{2})$. It also uses $2n^{2}$ shared
SWSR registers: $n$ $R\\_init$ registers of size $O(1)$, and $n$ $R\\_ack$
registers of size $O(1)$.

The local space at each reader process can be seen to be $O(n^{2})$.

##  6 Conclusions

This paper studied Byzantine tolerant construction of a SWMR atomic register
from SWSR atomic registers. It is the first to propose a definition of
Byzantine register linearizability by non-trivially taking into account
Byzantine behavior of the writer and readers, and by overcoming the drawbacks
of the definition used by previous works. We introduced the concept of a
correct write operation by a Byzantine writer. We also introduced the notion
of a pseudo-correct write operation by a Byzantine writer, which has the
effect of a correct write operation. Only correct and pseudo-correct writes
may be returned by correct readers. The correct and pseudo-correct writes are
totally ordered by their linearization points and this order is the total
order in logical time in which the writes were performed. We then gave an
algorithm to construct a Byzantine tolerant SWMR atomic register from SWSR
atomic registers that meets our definition of Byzantine register
linearizability.

## References

  * [1] Marcos K. Aguilera, Naama Ben-David, Rachid Guerraoui, Virendra J. Marathe, and Igor Zablotchi.  The impact of RDMA on agreement.  In Peter Robinson and Faith Ellen, editors, Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019, pages 409–418. ACM, 2019.
  * [2] Hagit Attiya, Amotz Bar-Noy, and Danny Dolev.  Sharing memory robustly in message-passing systems.  J. ACM, 42(1):124–142, 1995.
  * [3] James E. Burns and Gary L. Peterson.  Constructing multi-reader atomic values from non-atomic values.  In Fred B. Schneider, editor, Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing, Vancouver, British Columbia, Canada, August 10-12, 1987, pages 222–231. ACM, 1987.
  * [4] Shir Cohen and Idit Keidar.  Tame the wild with byzantine linearizability: Reliable broadcast, snapshots, and asset transfer.  In Seth Gilbert, editor, 35th International Symposium on Distributed Computing, DISC 2021, October 4-8, 2021, Freiburg, Germany (Virtual Conference), volume 209 of LIPIcs, pages 18:1–18:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [5] Sibsankar Haldar and K. Vidyasankar.  Constructing 1-writer multireader multivalued atomic variable from regular variables.  J. ACM, 42(1):186–203, 1995.
  * [6] Maurice Herlihy.  Wait-free synchronization.  ACM Trans. Program. Lang. Syst., 13(1):124–149, 1991.
  * [7] Maurice Herlihy and Nir Shavit.  The Art of Multiprocessor Programming.  Morgan-Kaufmann, 2008.
  * [8] Maurice Herlihy and Jeannette M. Wing.  Linearizability: A correctness condition for concurrent objects.  ACM Trans. Program. Lang. Syst., 12(3):463–492, 1990.
  * [9] Xing Hu and Sam Toueg.  On implementing SWMR registers from SWSR registers in systems with byzantine failures.  In Christian Scheideler, editor, 36th International Symposium on Distributed Computing, DISC 2022, October 25-27, 2022, Augusta, Georgia, USA, volume 246 of LIPIcs, pages 36:1–36:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
  * [10] Damien Imbs, Sergio Rajsbaum, Michel Raynal, and Julien Stainer.  Read/write shared memory abstraction on top of asynchronous byzantine message-passing systems.  J. Parallel Distributed Comput., 93-94:1–9, 2016.
  * [11] Amos Israeli and Amnon Shaham.  Optimal multi-writer multi-reader atomic register.  In Norman C. Hutchinson, editor, Proceedings of the Eleventh Annual ACM Symposium on Principles of Distributed Computing, Vancouver, British Columbia, Canada, August 10-12, 1992, pages 71–82. ACM, 1992.
  * [12] Leslie Lamport.  On interprocess communication. part I: basic formalism.  Distributed Comput., 1(2):77–85, 1986.
  * [13] Leslie Lamport.  On interprocess communication. part II: algorithms.  Distributed Comput., 1(2):86–101, 1986.
  * [14] Dahlia Malkhi and Michael K. Reiter.  Secure and scalable replication in phalanx.  In The Seventeenth Symposium on Reliable Distributed Systems, SRDS 1998, West Lafayette, Indiana, USA, October 20-22, 1998, Proceedings, pages 51–58. IEEE Computer Society, 1998.
  * [15] Friedemann Mattern.  Virtual time and global states of distributed systems.  In Parallel and Distributed Algorithms, pages 215–226. North-Holland, 1988.
  * [16] Achour Mostéfaoui, Matoula Petrolia, Michel Raynal, and Claude Jard.  Atomic read/write memory in signature-free byzantine asynchronous message-passing systems.  Theory Comput. Syst., 60(4):677–694, 2017.
  * [17] Richard E. Newman-Wolfe.  A protocol for wait-free, atomic, multi-reader shared variables.  In Fred B. Schneider, editor, Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing, Vancouver, British Columbia, Canada, August 10-12, 1987, pages 232–248. ACM, 1987.
  * [18] Gary L. Peterson.  Concurrent reading while writing.  ACM Trans. Program. Lang. Syst., 5(1):46–55, 1983.
  * [19] Gary L. Peterson and James E. Burns.  Concurrent reading while writing II: the multi-writer case.  In 28th Annual Symposium on Foundations of Computer Science, Los Angeles, California, USA, 27-29 October 1987, pages 383–392. IEEE Computer Society, 1987.
  * [20] Michel Raynal and Mukesh Singhal.  Logical time: Capturing causality in distributed systems.  Computer, 29(2):49–56, 1996.
  * [21] Ambuj K. Singh, James H. Anderson, and Mohamed G. Gouda.  The elusive atomic register revisited.  In Fred B. Schneider, editor, Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing, Vancouver, British Columbia, Canada, August 10-12, 1987, pages 206–221. ACM, 1987.
  * [22] K. Vidyasankar.  Converting lamport’s regular register to atomic register.  Inf. Process. Lett., 28(6):287–290, 1988.
  * [23] K. Vidyasankar.  A very simple construction of 1-writer multireader multivalued atomic variable.  Inf. Process. Lett., 37(6):323–326, 1991.
  * [24] Paul M. B. Vitányi and Baruch Awerbuch.  Atomic shared register access by asynchronous hardware (detailed abstract).  In 27th Annual Symposium on Foundations of Computer Science, Toronto, Canada, 27-29 October 1986, pages 233–243. IEEE Computer Society, 1986.