Another Look at the Implementation of Read/write Registers in Crash-prone Asynchronous Message-Passing Systems (Extended Version)
Damien Imbs Achour Mostefaoui Matthieu Perrin Michel Raynal















plain


decorations.markings
decorations.pathmorphing
decorations.pathreplacing



square


 -12pt











definitionDefinition
theoremTheorem
lemmaLemma
corollaryCorollary
propertyProperty
specificationSpecification
observationObservation









lemma-repeat[1]

  Lemma <ref> 

               



linecounter







algorithmthplop
algorithmAlgorithm
constructionthplop
constructionConstruction










  













    









 
























































 §.§ 


 §.§ 
[1]
#1



  §.§.§ 


  §.§.§ 
[1]
#1







 


  
  



Another Look at the Implementation of  Read/write Registers 

            in Crash-prone
            Asynchronous Message-Passing Systems 

            (Extended Version)
    Damien Imbs^∘, 
         Achour Mostéfaoui^†, 
         Matthieu Perrin^▵, 
         Michel Raynal^⋆,
 

   
^∘LIF, Université Aix-Marseille, 13288  Marseille, France 

^†LINA, Université de Nantes, 44322 Nantes, France 

^▵Computer science department, Technion, Haifa, 3200003, Israel 

^⋆Institut Universitaire de France

^IRISA, Université de Rennes, 35042 Rennes, France 



    
==============================================================================================================================================================================================================================================================================================================================================================================================







  “Yet another paper on” the implementation of read/write registers
  in crash-prone asynchronous message-passing systems! Yes..., but,
  differently from its predecessors, this paper looks for a
  communication abstraction which captures the essence of such an
  implementation in the same sense that total order broadcast can be
  associated with consensus, or message causal delivery can be
  associated with causal read/write registers.  To this end, the paper
  introduces  a new communication abstraction, named -broadcast
  ( standing for “Set Constrained Delivery”), which, instead of
  a single message, delivers to processes sets of messages (whose size
  can be arbitrary), such that the sequences of message sets delivered
  to any two processes satisfies some constraints.  The paper then
  shows that: (a) -broadcast allows for a very simple
  implementation of a snapshot object (and consequently also of atomic
  read/write registers) in crash-prone asynchronous message-passing
  systems; (b) -broadcast can be built from snapshot objects
  (hence -broadcast and snapshot objects –or read/write
  registers– are “computationally equivalent”); (c) -broadcast
  can be built in message-passing systems where any minority of
  processes may crash (which is the weakest assumption on the number
  of possible process crashes needed to implement a read/write
  register).
  
   
 
Keywords:
  Asynchronous system, Atomicity, Communication abstraction, Linearizability,
  Message-passing system, Process crash, Read/write atomic register, 
  Snapshot object.









empty









§ INTRODUCTION


The “one-shot” terracotta tablets introduced and used at Sumer about 3030
BC <cit.>, and the “multi-shot” palimpsests used in the middle-age,
can be considered as ancestors of the read/write register
abstraction. Such an object provides its users with a write operation
which defines a new value of the register, and a read operation which
returns its value.  When considering sequential computing, read/write
registers are universal in the sense that they are assumed to allow  solving
any problem that can be solved <cit.>.




  
On the variety of read/write registers
           and their distributed implementation 
In a shared read/write memory system, the registers are given for
free.  The situation is different in a message-passing system, where
the computing entities (processes) communicate by sending and
receiving messages transmitted through a communication network.
Hence, in such a distributed context, a register is not given for
free, but constitutes a communication abstraction which must be built by
a distributed algorithm with the help of the local memories of the
processes and the communication network.


Several types of registers have been proposed. They differ  according to
(a) their size (from binary registers  which contain a single bit,
to bounded and unbounded registers); (b) their behavior in the presence
of concurrency (safe, regular, atomic <cit.>); 
(c) the number of processes
which are allowed to read  them (Single-Reader -SR- vs Multi-Reader -MR-
register);
and (d) the number of processes which are allowed to write them
(Single-Writer -SR- vs Multi-Writer -MR- register), which gives four
possible combinations from SWSR to MWMR. There are algorithms building
MWMR atomic (bounded and unbounded) registers from SWSR binary safe
registers <cit.> (see <cit.> for surveys of such algorithms).




As far as a read/write register is concerned, atomicity means
that (a) each read or write operation appears as if it had been
executed instantaneously at a single point of the time line, (b) this
point appears between its start event and its end event, (c) no two
operations appear at the same point of the time line, and (d) a read
returns the value written by the closest preceding write operation (or
the initial value of the register if there is no preceding
write) <cit.>.  Linearizability is atomicity extended to
any object defined from a sequential specification on total
operations <cit.>.  In the following, we consider the terms
atomicity and linearizability as synonyms.  Hence, a sequence of read
and write operations satisfying atomicity is said to be linearizable,
and is called a linearization. The point of the time line at which an
operation appears to have been executed is called its linearization point. 

  

Many distributed algorithms have been proposed, which build a read/write
register on top of a message-passing system, be it failure-free or
failure-prone. In the failure-prone case, the addressed failure models
are the process crash failure model, and the Byzantine process
failure model (see textbooks, e.g.,  <cit.>).
When considering process crash failures (the one considered in this
paper[For Byzantine failures, see for example <cit.>.]),
the most famous of these algorithms was proposed by H. Attiya, A. Bar-Noy,
and D. Dolev in <cit.>. This algorithm, usually called ABD
according to the names of its authors, considers an n-process asynchronous
system in which up to t < n/2 processes may crash.
As  t < n/2 is an upper bound of the number
of process crashes which can be tolerated (see <cit.>),
this algorithm is t-resilient optimal. Its instances
implementing SWMR or MWMR atomic read/write registers rely on (a)
quorums <cit.>, and (b) a classical broadcast/reply communication pattern.
This communication pattern is used twice in a read operation, and 
once (twice) in a write operation for an SWMR (MWMR) atomic 
read/write register. 

Other algorithms –each with its own properties– implementing atomic
read/write registers on top of crash-prone asynchronous message-passing
systems can be found in the literature (<cit.> to
cite a few; see also the analytic presentation given in <cit.>). 



  
From registers to snapshot objects
The snapshot  object was introduced in <cit.>.
A snapshot object is an array [1..m] of atomic read/write registers
which provides the processes with two operations,
denoted () and ().
If the base registers are SWMR  
the snapshot is called SWMR snapshot (and we have then m=n). In this case,
the invocation of (v) by a process p_i assigns v to [i], 
and the invocation of () by a process p_i returns the
value of the full array as if the operation had been executed
instantaneously.
If the base registers are MWMR, the snapshot is called MWMR snapshot.
The invocation  of (r,v), where 1≤ r≤ m,
by a process p_i assigns v to [r],
and  () is defined as before.
Said another way, the operations () and () are atomic,
i.e., in any execution of an SWMR (or MWMR) snapshot object, its operations 
() and () are linearizable.



Implementations of both  SWMR and  MWMR snapshot objects on top of
read/write atomic registers have been proposed
(e.g., <cit.>). 
The “hardness” to build snapshot objects in read/write systems and
associated lower bounds are presented in the  survey <cit.>.
The best algorithm known to implement  an SWMR snapshot requires 
O(n log n) read/write on the base SWMR registers  for both 
the () and () operations <cit.>.
As far as MWMR snapshot objects are concerned, there are implementations 
where each operation has an O(n) cost[Snapshot objects built
  in read/write  models enriched with operations such as Compare&Swap,
  or LL/SC, have also been considered, e.g.,<cit.>. Here
  we are interested in pure read/write models.]. 


As far as the construction of an SWMR (or MWMR) snapshot object in 
crash-prone asynchronous message-passing systems where t<n/2 is
concerned, it is possible to stack two constructions: first 
an algorithm implementing SWMR (or MWMR) atomic read/write registers
(such as ABD), and, on top of it, an algorithm implementing an
SWMR (or MWMR) snapshot object. This stacking approach provides
objects whose operation cost is O(n^2 log n) messages for SWMR
snapshot, and O(n^2) messages for MWMR snapshot.  An algorithm
based on the same communication pattern as ABD, which builds an atomic
SWMR snapshot object “directly” (i.e., without stacking algorithms)
was recently presented in <cit.> (the aim of this algorithm is to
perform better that the stacking approach in concurrency-free executions). 




  
Another look at the implementation of read/write registers
and snapshot objects
In sequential computing, there are “natural” pairings
linking data structures and control structures. The most
simple examples are the pair “array and for loop”, and
the pair “tree and recursion”.

When we look at the implementation of a causal read/write
register <cit.> on top of a (crash-free or crash-prone)
message-passing system, the causal message delivery broadcast
abstraction <cit.> is the appropriate communication abstraction.
Namely, given this abstraction for free, 
the algorithms implementing the read and write operations build on top of it,
become very simple,  need only a few lines, and are easy to understand and to
prove correct. Of course, this is due to the fact that the  causal  broadcast
abstraction captures and abstracts the causality relation needed to
implement a causal read/write  register. Similarly, total order broadcast is the
communication abstraction associated with the consensus object <cit.>. 
This is summarized in Table <ref>. 







As already said, all the algorithms we know which implement atomic
read/write registers, and (by stacking transitivity or directly)
SWMR or MWMR snapshots objects, on top of
crash-prone asynchronous message-passing systems, are based on a
broadcast/reply pattern plus the use of intersecting quorums.  Hence,
the following question naturally arises: Is this approach the “only” way
to implement a snapshot object (or an atomic register), or
is there a specific
  communication abstraction which captures the essence and simplifies
  the implementation of snapshot objects (and atomic read/write registers)?




  
Content of the paper
Informatics in general (and  distributed computing in particular)
is a science of abstractions, and this paper is distributed programming
abstraction-oriented. It strives to address a
“desired level of abstraction and generality – one that is broad
enough to encompass interesting new situations yet specific
enough to address the crucial issues” as expressed in <cit.>. 
More precisely, it  answers the previous question in a positive way. 
To this end, it presents a simple broadcast abstraction which matches –and
therefore captures the essence of– snapshot objects (and atomic read/write
registers). We call it Set-Constrained Delivery Broadcast (in
short -broadcast).  Given this communication abstraction, it is
possible to quorum-free build snapshot objects, and vice versa.
Hence,  similarly to consensus and total order broadcast, -broadcast
and snapshot objects have the same computational power (Table <ref>). 


The -broadcast communication abstraction allows a process to
broadcast messages, and to deliver sets of messages (instead of single
messages) in such a way that, if a process p_i delivers a message
set[In the rest of the paper, the identifiers starting
  with”ms” denote message sets.] ms containing a
message m, and later delivers a message set ms' containing a
message m', then no process p_j can deliver first a set containing
m' and later another set containing m.  Let us notice that p_j
is not prevented from delivering m and m' in the same set.














The implementation of an instance of -broadcast costs
O(n^2) messages. It follows that  the cost  of a snapshot operation
(or a read/write register operation) on top of a message-passing
asynchronous system, where any minority of processes may crash, is
also O(n^2) for both SWMR and  MWMR snapshot objects
(i.e., better than the stacking approach for SWMR snapshot objects).
Additionally, be the snapshot objects that are  built SWMR or MWMR, 
their implementation differ only in the fact that their underling
read/write registers are SWMR or MWMR. This provides us with a
noteworthy   genericity-related design simplicity. 

Of course, there is rarely something for free.  The algorithms
implementing the snapshot and write operations are simple because the
-broadcast abstraction hides enough “implementation details” and
provides consequently a high level abstraction (much higher than the
simple broadcast used in ABD-like algorithms). Its main interest lies
in its capture of the high level message communication abstraction
that, despite asynchrony and
process failures, allows simple message-passing implementations of shared
memory objects such as snapshot objects and atomic read/write registers.




  
Roadmap
 The paper is composed of <ref> sections.
Section <ref> presents the two base computation models
concerned in this paper, 
(read/write and message-passing). Section <ref>
presents the -broadcast communication abstraction.  Then,
Section <ref> presents a simple algorithm
which implements a snapshot object on top of an asynchronous system
enriched with -broadcast, in which any number of processes may
crash.  Section <ref> addresses the other
direction, namely, it presents an algorithm building the
-broadcast abstraction on top of an asynchronous system enriched
with snapshot objects and where any number of processes may crash.
Section <ref> concludes the paper.
A noteworthy feature of the algorithms that are presented
lies in their simplicity, which is a first class property. 

Appendix <ref> describes an implementation
of -broadcast suited to  asynchronous message-passing systems where any
minority of processes may crash.  Hence, being implementable in the
weakest[ From the point of view of the
  maximal number of process crashes that can be tolerated, assuming
  failures are independent.]  message-passing system model in which a
read/write register can be built, -broadcast is not “yet another
oracle” which makes things simpler to understand but cannot be
implemented.  Appendix <ref>
presents simplified -based algorithms which build atomic and 
sequentially consistent read/write registers.






§ BASIC COMPUTATION MODELS



This section presents two basic computation models.
In both cases, the process  model  is the same. 




 §.§ Processes

The computing model is composed of a set of n asynchronous
sequential processes, denoted p_1, ..., p_n. “Asynchronous” means
that each process proceeds at its own speed, which can be arbitrary
and always remains  unknown to the other processes.  

A process may halt prematurely (crash failure), but it executes 
its local algorithm correctly until its possible crash. The model parameter t
denotes the maximal number of processes that may crash in a  run.
A process that crashes in a run is said to be faulty. Otherwise, 
it is non-faulty. Hence a faulty process behaves as a non-faulty process
until it crashes. 





 §.§ Basic crash-prone asynchronous shared memory model




  
Atomic read/write register
The notion of an atomic read/write register has been formalized
in <cit.>. An MWMR atomic 
register (say ) is a concurrent object which provides each 
process  with an operation denoted . write(), 
and an operation denoted . read().  
When a process invokes . write(v) it defines
v as being the new value of .  An MWMR atomic register  is
defined by the following set of properties. 



  * Liveness.
An invocation of an operation by a non-faulty process terminates.


  * Consistency (safety).  All the operations invoked by the
processes, except possibly –for each faulty process– the last
operation it invoked, appear as if they have been executed
sequentially and this sequence of operations is such that:



  * each read returns the value written by the closest write that precedes
it (or the initial value of  if there is no preceding write), 


  * if an operation op1 terminates before an operation op2 starts, then 
 op1 appears before op2 in the sequence.


This set of properties states that, from an external observer point of
view, the read/write register appears as if it is accessed sequentially 
by the processes, and this sequence (a) respects the real-time access order,
and (b) belongs to the sequential specification of a register. 




  
Notation
The previous computation model is denoted _n,t[∅]
(Crash Asynchronous Read-Write).
This basic read/write model is also called wait-free read/write model. 
The symbol ∅ means there is no specific
constraint on t, which is equivalent to t<n, as it is always
assumed that not all processes crash.




  
Snapshot object
This object was defined in the introduction. As we have seen,
snapshot objects can be built in _n,t[∅].
As we have seen there are two types of snapshot objects.
SWMR snapshot objects (whose base registers are SWMR), and
MWMR snapshot objects (whose base registers are MWMR).

In the following we consider MWMR snapshot objects, but the algorithms
can  be trivially adapted to work with  SWMR snapshot objects. 

 _n,t[∅] enriched with snapshot objects is
denoted  _n,t[.
As a snapshot object can be built in  _n,t[∅]
this model has the same computational power as _n,t[∅].
It only offers a higher abstraction level. 





 §.§ Basic crash-prone asynchronous message-passing model





  
Communication
Each pair of processes communicate by sending and receiving messages
through two uni-directional channels, one in each direction. Hence,
the communication network is a complete network: any process p_i can
directly send a message to any process p_j (including itself).
A process p_i invokes the operation “send type(m)
to p_j” to send to p_j the message m, whose type is
type.  The operation “receive type() from
p_j” allows p_i to receive from p_j a message whose type is
type.

Each channel is reliable (no loss, corruption, nor creation of messages),
not necessarily first-in/first-out, and asynchronous (while the transit time 
of each message is finite, there is no upper bound on message transit times).

Let us notice that, due to process and message asynchrony, no process can
know if another process crashed or is only very slow.




  
Notation and   necessary and sufficient condition
This computation model is denoted _n,t[∅]
(Crash Asynchronous Message-Passing).

The constraint (t<n/2) is a necessary and sufficient condition to implement 
an atomic read/write register in _n,t[∅] <cit.>. 
Hence, the model  _n,t[∅] whose runs are constrained by 
t<n/2  is denoted _n,t[t<n/2].





§ A BROADCAST ABSTRACTION: SET-CONSTRAINED MESSAGE DELIVERY






  
Definition
The set-constrained broadcast abstraction (-broadcast)
provides the processes with
two operations, denoted () and  ().
The first operation takes a message to broadcast as input  parameter. 
The second one returns a non-empty set of messages to the process that
invoked it. 
Using a classical terminology, when a process invokes (m),
we say that it “scd-broadcasts a message m”. Similarly, when it invokes 
() and obtains a set of messages ms, we say that
it “scd-delivers a set of messages ms”. By a slight abuse of language,
we also say that a process “scd-delivers a  message m” when it  delivers 
a message  m∈ ms. 



-broadcast is defined by the following
set of properties, where we assume –without loss of generality–
that all the messages that are scd-broadcast are different. 



  * Validity.
  If a process scd-delivers a set containing a message m,
  then m was scd-broadcast by some process.


  * Integrity.
  A message is scd-delivered at most once by each process.


  * MS-Ordering.
  If a process p_i scd-delivers first a message m belonging to a set
  ms_i and later a message m' belonging to a set ms_i'≠ ms_i, then 
  no process  scd-delivers first the message m' in some
  scd-delivered set ms'_j and later the message m in some scd-delivered
  set ms_j≠ ms'_j. 


  * Termination-1.
  If a non-faulty process scd-broadcasts a message m,
  it terminates its scd-broadcast invocation and 
  scd-delivers a message set containing m.


  * Termination-2.
  If a non-faulty process scd-delivers a message m, every  non-faulty process
  scd-delivers a message set containing m.


Termination-1 and Termination-2 are classical liveness properties
(found for example in Uniform Reliable Broadcast). 
The other ones are safety properties.
Validity and Integrity are classical communication-related properties.
The first  states that there is neither  message creation nor message
corruption, while the second states that there is no message duplication.


The MS-Ordering property is new,
and characterizes -broadcast. It states that the contents of the sets of
messages  scd-delivered at any two processes are not totally independent:
the sequence of sets scd-delivered at a process p_i and
the sequence of sets scd-delivered at a process p_j must be mutually
consistent in the sense that a process p_i cannot scd-deliver
first m∈ ms_i and later m'∈ ms_i'≠ ms_i, while another process 
p_j  scd-delivers first m'∈ ms_j' and later m∈ ms_j≠ ms_j'. 
Let us nevertheless observe that if p_i  scd-delivers
first m∈ ms_i and later m'∈ ms_i',
p_j may scd-deliver m and m' in the same set of messages. 





  
An example
Let m_1, m_2, m_3,  m_4, m_5, m_6, m_7, m_8, ... be
messages that have been scd-broadcast by different processes.
The following  scd-deliveries of message sets by p_1, p_2 and p_3
respect the definition of -broadcast: 



  * at p_1:
{m_1,m_2}, {m_3,m_4,m_5}, {m_6}, {m_7,m_8}.


  * at p_2:
{m_1}, {m_3,m_2}, {m_6,m_4,m_5}, {m_7}, {m_8}.


  * at p_3:
{m_3,m_1,m_2}, {m_6,m_4,m_5}, {m_7}, {m_8}.  

Differently, due to the scd-deliveries of the sets including m_2 and m_3, 
the following  scd-deliveries by p_1 and p_2 do not satisfy  the
MS-broadcast property: 



  * at p_1:
{m_1,m_2}, {m_3,m_4,m_5}, ...  


  * at p_2:
{m_1,m_3}, {m_2}, ...






  
A containment property
Let ms_i^ℓ be the  ℓ-th message set  scd-delivered by p_i.
Hence, at some time, p_i scd-delivered the sequence
of message sets ms_i^1, ⋯, ms_i^x.
Let _i^x= ms_i^1∪⋯∪ ms_i^x. 

The following  property follows directly from the 
MS-Ordering and Termination-2 properties: 



  * Containment.
∀ i,j,x,y:
(_i^x ⊆_j^y) ∨ (_j^y⊆_i^x).




  
Remark 1: Weakening SCD-broadcast
If the messages in a message set are delivered one at a time, and
the MS-Ordering property is suppressed, -broadcast boils down to
Reliable Broadcast. 



  
Remark 2: On the partial order created by the  message sets
The MS-Ordering  and Integrity properties establish
a partial order on the set of all the messages, defined as follows.
Let ↦_i be the local message delivery order at a process
p_i defined as follows:
m ↦_i m' if p_i
scd-delivers the set containing m before the set containing m'. 
As no message is scd-delivered twice, it is easy to see that 
↦_i is a  partial order (locally know by p_i). 

The reader can check that there is a total order (which remains
unknown to the processes)  on the whole set of messages,
that complies with the  partial order ∪_1≤ i≤ n↦_i. 
This is where -broadcast can be seen as a weakening
of total order broadcast. 



Let →_msg 𝑑𝑒𝑓=∪_1≤ i ≤ n→_i.
Due to the MS-Ordering  property, this  relation  is partial order
on the set of all the  messages  that have been scd-broadcast.
It is  global in the sense that
it involves all the local relations →_i, and consequently
cannot be fully  known by each process taken individually. 






§ FROM -BROADCAST TO AN MWMR SNAPSHOT OBJECT



Let  _n,t[] denote
_n,t[∅] enriched with the  -broadcast abstraction.
Hence, this abstraction is given for free. 
This section presents and proves correct a simple algorithm building an 
MWMR snapshot object  on top of _n,t[].

The same algorithm with very few  simple modifications can be used to
build SWMR or MWMR atomic registers in  _n,t[]
(see Appendix <ref>).




 §.§ Building an MWMR snapshot object  on top
  of _n,t[]

Let [1..m] denote the MWMR snapshot object  that is built.








  
Local representation of   at a process p_i
At each register p_i,  [1..m] is represented by three local variables
reg_i[1..m] (data part), plus  tsa_i[1..m] and done_i (control part). 



  * _i is a Boolean variable. 


  * _i[1..m] contains the current value of  [1..m],
  as known by p_i.


  * tsa_i[1..m] is an array of timestamps associated with the values
  stored in _i[1..m].
A timestamp is a pair made of a local clock value and a process identity. 
Its initial value is ⟨ 0,-⟩.
The fields associated with tsa_i[r] are denoted
 ⟨ tsa_i[r].date ,tsa_i[r].proc ⟩. 





  
Timestamp-based order relation
We consider the classical lexicographical total order relation
on timestamps, denoted  <_ts. Let ts1= ⟨ h1,i1⟩ and
ts2= ⟨ h2,i2⟩. We have 
ts1  ts2 𝑑𝑒𝑓=
(h1<h2) ∨ ((h1=h2)∧ (i1<i2)).




  
Algorithm <ref>: snapshot operation
(Lines <ref>-<ref>) When p_i invokes
.(), it first sets _i to , and invokes
 (i).  () is a synchronization message,
whose aim is to entail the refreshment of the value of _i[1..m]
(lines <ref>-<ref>) which occurs before
the setting of _i to  (line <ref>).
When this happens, p_i returns the value of its local variable
_i[1..m] and terminates its snapshot invocation.













  
Algorithm <ref>: write operation
(Lines <ref>-<ref>)
When a process p_i wants to assign a value v to [r], 
it invokes .(r,v).
This operation is made up of two parts.
First p_i executes a re-synchronization
(lines <ref>-<ref>, exactly 
as in the snapshot operation) whose side
effect is here to provide p_i with an up-to-date value of _i[r].date.

In the second part, p_i associates the timestamp ⟨_i[r].date+1,i⟩ with v, and invokes 
(r, v, ⟨_i[r].date+1,i⟩)
(line <ref>).  In addition to informing the other
processes on its write of [r], this message () acts as a
re-synchronization message, exactly as a message (i).  When
this synchronization terminates (i.e., when the Boolean _i is
set to ), p_i returns from the write operation
(line <ref>).






  
Algorithm <ref>:
  scd-delivery of a set of messages
When p_i scd-delivers a message set, namely, 


{ (r_j_1, v_j_1, ⟨ date_j_1, j_1⟩), ⋯,
     (r_j_x, v_j_x, ⟨ date_j_x, j_x⟩), 
      (j_x+1), ⋯, (j_y) }
 

it first looks if  there are messages ().
If it is the case, for each register [r] for which there are 
messages (r,-,-)   (line <ref>),
p_i computes the maximal timestamp carried
by these messages (line <ref>), and  updates accordingly
its local representation of [r]
(lines <ref>-<ref>).
Finally, if p_i is the sender of one of these messages
(() or ()), 
done_i is set to , which terminates p_i's re-synchronization
(line <ref>).



  
Message cost
An invocation of  () involves one
invocation of (), and an  invocation of
() involves two such invocations. 
It is shown in Appendix <ref> that,
in a message-passing system, () costs O(n^2) protocol
messages. It follows that, in such systems,  the message cost of both
operations of a snapshot object  is O(n^2). 
(This remains true for SWMR snapshot objects, see
Appendix <ref>.) 





 §.§ Proof of Algorithm <ref>


As they are implicitly used in the  proofs that follow, let us recall
the properties of the -broadcast abstraction. The non-faulty processes
scd-deliver the same messages (exactly one each), and
each of them was scd-broadcast. As a faulty process behaves correctly
until it crashes, it scd-delivers a subset of the messages 
scd-delivered by the non-faulty processes. 

Without loss of generality, we assume that there is an initial write
operation issued by a non-faulty process.
Moreover, if  a process crashes in a snapshot operation, its snapshot is not
considered;  if  a process crashes in a write operation, its
write is considered only if the message () it sent at
line <ref> is scd-delivered to at least one non-faulty process
(and by the Termination-2 property, at least to all non-faulty processes). 
Let us notice that  a message  () scd-broadcast by a process p_i
does not modify the local variables of  the other processes.










§ PROOF OF LEMMAS FOR THEOREM <REF>







If a non-faulty process invokes an operation, it returns from its invocation. 



  Let p_i be a non-faulty process that invokes a read or write  operation.
  By the Termination-1 property of -broadcast, it 
  eventually receives a message set containing the message
  () or () it sends at 
  line <ref>, <ref> or <ref>.
  As all the statements associated with the scd-delivery of a message set
  (lines <ref>-<ref>) terminate, 
  it follows that  the synchronization Boolean _i   is eventually
  set to . Consequently,  p_i returns from the invocation of its
  operation.








  
Extension of the relation 
The relation  is extended to  
a partial order on arrays of timestamps, denoted ≤_,
defined as follows: 
tsa1[1..m] ≤_ tsa2[1..m] 𝑑𝑒𝑓=∀ r: (1[r] = 2[r] 1[r]  tsa2[r]).
Moreover,  1[1..m] <_2[1..m] 𝑑𝑒𝑓=
(1[1..m] ≤_tsa2[1..m])∧ (1[1..m] ≠ tsa2[1..m]).




  
Definition
Let _i be the set of the array values  taken by ts_i[1..m] at
line <ref> (end of the processing of  a message set
by process p_i). Let =∪_1≤ i≤ n_i. 




The order ≤_ is total on .



  Let us first observe that, for any i,  all values in _i
  are totally ordered (this comes from ts_i[1..m] whose entries can
  only increase,  lines <ref> and <ref>).  
  Hence, let 1[1..m] be an array value
  of _i, and  2[1..m] an array value of _j, where i≠ j. 


  Let us assume, by contradiction, that ¬ (1 ≤_2) and ¬ (2 ≤_1).  As ¬ (1
  ≤_2), there is a registers r such that 2[r] <1[r].
  According to lines <ref>
  and <ref>, there is a message (r,-,  1[r])
  received by p_i when _i = 1 and not received  
  by p_j when _j = 2 (because 2[r] <1[r]).
  Similarly, there is a message
  (r',-, 2[r']) received by p_j when _j = 2
  and not received by p_i when _i = 1.
  This situation contradicts the MS-Ordering property, from which we conclude
  that either 1 ≤_2 or 2 ≤_1. 
   







  
Definitions
Let us associate a timestamp ts((r, v)) with each write
operation as follows. Let p_i be the invoking process; ts((r,
v)) is the timestamp of v as defined by p_i at
line <ref>, i.e., ⟨_i[r].date+1, i⟩.

Let 1 and 2 be any two operations. The relation
≺ on the whole set of operations is defined as follows:
 1 ≺2 if 1 terminated before 2 started. 
It is easy to see that ≺ is a real-time-compliant partial order 
on all the operations.




No two distinct write operations on the same register 1(r, v)
and 2(r, w) have the same timestamp, and (1(r, v)
≺2(r, w)) ⇒ (ts(1)  ts(2)).



Let ⟨ date1,i⟩ and ⟨ date2,j⟩ be the
timestamp of 1(r, v) and 2(r, w), respectively.  If
i≠ j, 1(r, v) and 2(r, w) have been produced by
different processes, and their timestamp differ at least in their
process identity.

So, let us consider that the operations have been issued by the same
process p_i, with 1(r, v) first.  As 1(r, v)
precedes 2(r, w), p_i first invoked  
(r, v,⟨ date1,i⟩) (line <ref>) and
later (r, w,⟨ date2,i⟩). It follows that these
-broadcast invocations are separated by a local reset of the Boolean
done_i at line <ref>.  Moreover, before the reset of
_i due to the scd-delivery of
the message {⋯,(r, v,⟨ date1,i⟩),⋯},
we have _i[r].date_i≥ date1
(lines <ref>-<ref>).  Hence, we have
_i[r].date≥ date1 before the reset of _i
(line <ref>).  Then, due to the “+1” at
line <ref>, (r, w,⟨ date2,i⟩) is
such that date2>date1, which concludes the proof of the first part
of the lemma. 

Let us now consider that  1(r, v) ≺2(r, w). If
1(r, v) and 2(r, w) have been produced by the same process
we have date1 < date2 from the previous reasoning.
So let us assume that they have been produced by different processes
p_i and p_j.
Before  terminating 1(r, v) (when the Boolean _i is set
  at line <ref>), p_i  received a message set
ms1_i containing the message (r, v,⟨ date1,i⟩). 
When p_j executes  2(r, w), it first  invokes
 (j) at line <ref>. 
Because 1(r, v) terminated before  2(r, w) started, 
this message (j) cannot belong to ms1_i.

Due to Integrity and Termination-2 of -broadcast, p_j eventually
scd-delivers exactly one  message set ms1_j containing
(r, v,⟨ date1,i⟩). Moreover, it also
scd-delivers  exactly one  message set ms2_j containing
its own message (j).
On the the other side, p_i scd-delivers exactly one  message
set ms2_i containing the message (j).
It follows from the MS-Ordering property that, if  ms2_j≠ ms1_j, 
p_j cannot scd-deliver ms2_j  before  ms1_j.
Then, whatever the case (ms1_j=ms2_j or  ms1_j is scd-delivered at
p_j before ms2_j), it follows from the fact that the messages ()
are processed (lines <ref>-<ref>)
before the messages (j) (line <ref>), that we have
_j[r]≥⟨ date1,i⟩ when _j is set to . 
It then follows from line <ref> that date2>date1,
which concludes the proof of the lemma. 





  
Associating timestamp arrays with operations
Let us associate a timestamp array ()[1..m] with each operation
() as follows.



  * Case ()=(). Let p_i be the invoking process;
  () is the value of _i[1..m] when p_i returns from the
  snapshot operation (line <ref>).  


  * Case ()=(r,v). 
  Let _({A}), where A is a set of array values,      
  denote the smallest array value of A according to <_. 

  Let ()𝑑𝑒𝑓=_({[1..m] ∈ ts() ≤_ts[r]}).    
   Hence,  () is the first [1..m] of , that reports
   the operation ()=(r,v).        






Let  and ' be two distinct operations such that ≺'. We have () ≤_('). Moreover, if '
is a write operation, we have () <_(').



  Let p_i and p_j be the processes that performed  and 
  ', respectively.
  Let _j be the (j) message sent by p_j (at
  line <ref> or <ref>) during the
  execution of '.  Let 𝑡𝑒𝑟𝑚__𝑖 be the
  value of _i[1..m] when  terminates
  (line <ref> or <ref>), and
  𝑠𝑦𝑛𝑐__𝑗
  the value of _j[1..m] when 𝑑𝑜𝑛𝑒_𝑗 becomes true for the first
  time after p_j sent _j (line <ref>
  or <ref>). Let us notice that 𝑡𝑒𝑟𝑚__𝑖
  and  𝑠𝑦𝑛𝑐__𝑗 are elements of the set . 


  

  According to lines <ref> and <ref>, for
  all r, _i[r] is the largest timestamp carried by
  a message (r,v,-)
  received by p_i in a message set before  terminates.  Let m be a
  message such that there is a set sm scd-delivered by p_i before it
  terminated . As p_j sent _j after p_i terminated,
  p_i did not receive any set containing _j before it
  terminated . By the properties Termination-2 and MS-Ordering, p_j
  received message m in the same set as _j or in a message
  set sm' received before the set containing _j. Therefore,
  we have 𝑡𝑒𝑟𝑚__𝑖≤_𝑠𝑦𝑛𝑐__𝑗.
  
  If  is a snapshot operation, then () =
  𝑡𝑒𝑟𝑚__𝑖. Otherwise, ()=(r,v). As p_i has
  to wait until it processes a set of messages including  its () message
  (and executes line <ref>),
   we have ts() 𝑡𝑒𝑟𝑚__𝑖[r].
   Finally, due to the fact that 𝑡𝑒𝑟𝑚__𝑖∈ and
   Lemma <ref>, we have
   ()≤_𝑡𝑒𝑟𝑚__𝑖.

  If ' is a snapshot operation, then 𝑠𝑦𝑛𝑐__𝑗 = (')
   (line <ref>).
  Otherwise, ()=(r,v) and thanks to the +1 in
  line <ref>,
  𝑠𝑦𝑛𝑐__𝑗[r] is strictly smaller than (')[r]
  which, due to Lemma <ref>, implies
  𝑠𝑦𝑛𝑐__𝑗 <_(').

  It follows that, in all cases, we have
  () ≤_𝑡𝑒𝑟𝑚__𝑖≤_𝑠𝑦𝑛𝑐__𝑗≤_(')
  and if ' is a write operation, we have () ≤_𝑡𝑒𝑟𝑚__𝑖≤_𝑠𝑦𝑛𝑐__𝑗 <_('),
  which concludes the proof of the lemma.
  




The previous lemmas allow the operations to be linearized (i.e.,
totally ordered in an order compliant with both the sequential
specification of a register, and their real-time occurrence order)
according to a total order extension of the reflexive and transitive
closure of the →_lin relation defined thereafter.

  Let , ' be two operations. We define the →_lin relation
  by →_lin' if one of the following properties holds:
  
  
  * 
    ≺',
  
  * 
    tsa() <_tsa tsa('),
  
  * 
    tsa() = tsa('), op is a write operation
    and ' is a snapshot operation,
  
  * 
    tsa() = tsa('),  and ' are two
    write operations on the same register and ts()  ts('),
  



 
 The snapshot object built by Algorithm <ref>
 is linearizable.




  We recall the definition of the →_lin relation: →_lin' if one of the following properties holds:
  
  
  * 
    ≺',
  
  * 
    tsa() <_tsa tsa('),
  
  * 
    tsa() = tsa('), op is a write operation
    and ' is a snapshot operation,
  
  * 
    tsa() = tsa('),  and ' are two
    write operations on the same register and ts()  ts('),
  
  We define the →_lin^⋆ relation as the reflexive
  and transitive closure of the →_lin relation.

  Let us prove that the →_lin^⋆ relation is a
  partial order on all operations. Transitivity and reflexivity are
  given by construction.  Let us prove antisymmetry. Suppose there are
  _0, _2, ..., _m such that _0 = _m and _i
  →_lin_i+1 for all i<m.  By
  Lemma <ref>, for all i<m, we have
  tsa(_i) ≤_tsa tsa(_i+1), and tsa(_m) =
  tsa(_0), so the timestamp array of all operations are the
  same.  Moreover, if _i is a snapshot operation, then _i
  ≺_(i+1) % m is the only possible case
  (% stands for “modulo”) , and by
  Lemma <ref> again, _(i+1) % m
  is a snapshot operation. Therefore, only two cases are possible.
  
  
    
  
  * Let us suppose that all the _i are snapshot operations
    and for all i, _i ≺_(i+1) % m. As ≺ is a
    partial order relation, it is antisymmetric, so all the _i
    are the same operation.
    
  
  * Otherwise, all the _i are write operations. By
    Lemma <ref>, for all _i
    ⊀_(i+1) % m.  The operations _i and
    _i+1% m are ordered by the fourth point, so they are write
    operations on the same register and ts(_i) 
    ts(_i+1% m). By antisymmetry of the  relation, all
    the _i have the same timestamp, so by
    Lemma <ref>, they are the same
    operation, which proves antisymmetry.
  
  Let ≤_lin be a total order extension of
  →_lin^⋆. Relation ≤_lin is real-time
  compliant because →_lin^⋆ contains ≺.
  
  Let us consider a snapshot operation  and a register r such
  that tsa()[r] = ⟨ date1, i ⟩. According to
  line <ref>, it is associated to the value v that
  is returned by 1() for r, and comes from a
  (r,v,⟨ date1, i ⟩) message sent by a write
  operation _r = (r,v).  By definition of tsa(_r), we have
  tsa(_r) ≤_tsa tsa() (Lemma <ref>), 
  and therefore _r ≤_lin. Moreover, for any different write operation '_r on r,
  by Lemma <ref>, ts('_r) ≠
  ts(_r). If ts('_r)  ts(_r), then '_r ≤_lin_r. Otherwise, tsa() <_tsa tsa('_r), and (due to the first item
  of the definition of  →_lin) we have  ≤_lin'_r.
  In both cases, the value written by _r is the last
  value written on r before , according to ≤_lin.
  







Algorithm <ref> builds an MWMR  snapshot
object in the system model  _n,t[].



  The proof follows from
  Lemmas <ref>-<ref>. 








§ FROM  SWMR SNAPSHOT TO -BROADCAST



This section presents an algorithm which builds the -broadcast
abstraction in  _n,t[. This algorithm
completes the computational equivalence of  snapshot and -broadcast.
(SWMR snapshot objects can be easily implemented in
_n,t[ by instantiating
Algorithm <ref>  with m=n, and
only allowing p_i  to invoke .(r,-).) 







 §.§ Algorithm <ref>





  
Shared objects
The shared memory is composed of two SWMR snapshot objects (as defined above).
Let ϵ denote the empty sequence. 



  * [1..n]: is a snapshot object, initialized to
[∅, ⋯,∅], such that 
[i] contains the messages scd-broadcast by p_i. 


  * [1..n]: is a snapshot object,  initialized to
  [ϵ, ⋯,ϵ], such that [i] contains
  the sequence of the sets of messages scd-delivered by p_i. 

The notation ⊕ is used for the concatenation of a message set
at the end of a sequence of message sets. 




  
Local objects
Each process p_imanages the following local objects.



  * _i is a  local copy of the snapshot object .


  * _i is a  local copy of the snapshot object . 


  *  is an auxiliary variable whose aim is to contain the
  next message set that p_i has to scd-deliver. 

The function (set_seq)
returns the set of all the messages contained in  set_seq.




  
Description of Algorithm <ref>



When a process p_i invokes  (m), it adds m to
_i[i] and [i] to inform all the processes 
on the scd-broadcast of m. It then invokes the internal procedure
() from which it exits once it has
a set containing m (line <ref>). 

A background task T ensures that all messages will be
scd-delivered (line <ref>). This task invokes repeatedly
the internal procedure ().

As, locally, both the application process and the underlying task T can
invoke  (), which accesses the local variables of p_i,
those variables  are protected by a local fair mutual exclusion algorithm
providing the operations () and  ()
(lines <ref> and <ref>).  






The procedure () first invokes the internal procedure
(), whose aim is to allow p_i to scd-deliver sets of messages
which have been scd-broadcast and not yet locally scd-delivered. 

To this end, () works as follows (lines <ref>-<ref>).
Process p_i first obtains a snapshot of , and saves it in _i 
(line <ref>). This allows p_i to know which message sets have been
scd-delivered by all the processes; p_i then enters a “while” loop to
scd-deliver as many message sets as possible according to what was
scd-delivered by the other processes. 
For each process p_j that has scd-delivered a message set set containing
messages not yet scd-delivered by p_i  (predicate of line <ref>), 
p_i builds a set _i containing the messages in set that it
has not  yet scd-delivered  (line <ref>),  and locally scd-delivers it
(line <ref>). This local scd-delivery needs to update accordingly
both _i[i] (local update) and [i] (global update). 

When it returns from (), p_i strives to scd-deliver messages
not yet scd-delivered by the other processes. To this end, it first obtains
a snapshot of , which it stores in _i  (line <ref>).
If there are messages that can be scd-delivered (computation of _i
at line <ref>, and predicate at line <ref>), p_i
scd-delivers them and updates  _i[i] and  [i]
(lines <ref>-<ref>) accordingly.




 §.§ Proof of Algorithm <ref>




If a process scd-delivers a set containing a message m, some process invoked
(m). 



  The proof follows directly from the text of the algorithm, which copies
  messages from  to , without creating new messages.






No process scd-delivers  the same message twice. 



  Let us first observe that, due to lines <ref> and <ref>,
  all messages that are scd-delivered at a process p_i have been  added to
  _i[i]. The proof then follows directly from (a) this observation, 
  (b) the fact that (due to the local mutual exclusion at each process)
  _i[i] is updated consistently,
  and (c) lines <ref> and <ref>,
  which state that a message already scd-delivered (i.e., a message
  belonging to  _i[i]) cannot be added to _i. 






Any invocation of  () by a non-faulty process p_i terminates.



The proof consists in showing that the internal procedure
() terminates. 

As the  mutex algorithm is assumed to be fair, process p_i cannot block
forever at line <ref>. Hence, p_i invokes the 
internal  procedure (). It then 
issues first a snapshot invocation on  and stores the 
value it  obtains  the value of _i.
There is consequently a finite number of message sets in _i.
Hence,  the “while” of lines <ref>-<ref>
can be executed only a finite number of times, and it follows that 
any invocation of () by a non-faulty process terminates. 

The same reasoning (replacing  by ) shows that
process p_i cannot block forever when it executes the 
lines <ref>-<ref> of the procedure (). 







If a non-faulty process scd-broadcasts a message m,

it scd-delivers a message set containing m.



Let p_i be a non-faulty process that  scd-broadcasts a message m.
As it is non-faulty, p_i adds m to  [i]
and then invokes  ()  (line <ref>).
As m∈, it is eventually added to 
if not yet scd-delivered (line <ref>),
and scd-delivered at line <ref>, which concludes the proof
of the lemma. 






If a non-faulty process scd-delivers a message m, every  non-faulty process
scd-delivers a message set containing m.



Let us assume that a process scd-delivers a message set containing
a message m. It follows that the  process that invoked (m) 
added m to  (otherwise no process could scd-deliver m). 
Let p_i be a correct process. 
It invokes () infinitely often  (line <ref>).
Hence, there is a first execution of ()
such that sent_i contains m   (line <ref>).
If then follows from line <ref>  that m will be added to
_i (if not yet scd-delivered). If follows that p_i will
scd-deliver a set of messages containing m at line <ref>.    








Let p_i be a process that scd-delivers a set ms_i containing a
message m and later scd-delivers a set ms'_i containing a message
m'.  No process p_j scd-delivers first a set ms'_j containing m'
and later a set ms_j containing m.



  Let us consider two messages m and m'. Due to
   total order property on the  operations on  the  snapshot object
  , it is possible to order the write operations
  of m and m' into . Without loss of generality, let us assume
  that m is added to  before m'.
  We show that no process scd-delivers m' before m.[Let us
    notice that it is possible that a process scd-delivers them in two
    different message sets, while another process scd-delivers them in the same set
    (which does not contradicts the lemma).]

Let us consider a process p_i that scd-delivers the message m'.
There are two cases. 



  * p_i scd-delivers the message m'  at line <ref>. 
Hence, p_i obtained m' from the snapshot object 
(lines <ref>-<ref>).
As m was written in  before m', we conclude that
 contains m. It then follows from line <ref> that,
if p_i has not scd-delivered m before (i.e., m is not in  
_i[i]), then p_i scd-delivers it in the same set as m'. 


  * p_i scd-delivers the message m'  at line <ref>.
  Due to the predicate used at line <ref> to build a set
  of message to scd-deliver, this means that there is a process p_j
  that has previously scd-delivered a set of messages containing m'.

  Moreover, let us observe that the first time the  message m' is copied
  from  to some [x] occurs at line <ref>.
  As m was written in  before m', the corresponding process
  p_x cannot see m' and not m. 
  It follows from the previous item that p_x has scd-delivered m
  in the same  message set (as the one including m'), or in a previous 
  message set. It then follows from the predicate of line <ref> that
  p_i cannot scd-delivers m' before m.

  To summarize, the scd-deliveries of message sets in the procedure
  ()  cannot violate the MS-Ordering property, which is established
  at lines <ref>-<ref>. 









Algorithm <ref>
implements the -Broadcast abstraction in the system model
_n,t[t<n].



  The proof follows from
  Lemma <ref> (Validity), 
  Lemma <ref> (Integrity),
  Lemmas <ref>
  and <ref> (Termination-1), 
  Lemma <ref> (Termination-2), and
  Lemma <ref> (MS-Ordering).












§ CONCLUSION



This paper has introduced a new communication abstraction
(-broadcast) providing processes
with an abstraction level between reliable broadcast and total
order broadcast (which captures
the necessary and sufficient constraint on message
deliveries which allows  consensus objects to  be implemented in
asynchronous crash-prone message-passing systems).

More precisely, -broadcast  captures
the  abstraction level which is  “necessary and sufficient”
to implement read/write registers and snapshot objects on top of
asynchronous message-passing systems prone to process
failures. “Sufficient” means here that no other notion or
object[The notion of intersecting quorums
is neither  provided by the abstraction level offered by -broadcast,
nor required –in addition to -broadcast–
to implement registers or snapshot objects. Actually, 
it is  hidden  and majority quorums appear only in the implementation
of -broadcast.]
is needed to build a register or a snapshot object 
at the abstraction level provided by
-broadcast, while “necessary” means that the objects that are
built (registers and snapshot objects) are the weakest from a shared
memory computational point of view.  









As announced in the Introduction, an algorithm implementing
-broadcast in an asynchronous message-passing system where any minority
of processes may crash is described in Appendix <ref>.



This algorithm  requires O(n^2) protocol messages per invocation of
().  It follows that the -broadcast-based
MWMR snapshot algorithm

presented in the paper requires O(n^2) protocol messages
per invocation of () or () operation.
This is the best read/write snapshot algorithm we know in the context
of asynchronous message-passing systems. 







roman




§ ACKNOWLEDGMENTS

This work has been partially supported by the  Franco-German
DFG-ANR Project 40300781 DISCMAT (devoted to connections between
mathematics and distributed computing), and the French ANR project DESCARTES 
(devoted to layered and modular structures in distributed computing). 
The authors want to thank Faith Ellen for fruitful exchanges on
shared memory snapshot. 





99




AADGMS93 
Afek Y., Attiya H., Dolev D., Gafni E., Merritt M. and Shavit N., 
Atomic snapshots of shared memory. 
Journal of the ACM, 40(4):873-890 (1993)
    

ANBHK95
Ahamad M.,  Neiger G.,  Burns J.E.,  Hutto P.W., and Kohli P. 
Causal memory: definitions, implementation and programming. 
Distributed Computing, 9:37-49 (1995)   

A94
Anderson J., 
Multi-writer composite registers.
Distributed Computing, 7(4):175-195 (1994)

A00
Attiya H.,
Efficient and robust sharing of memory in message-passing systems.
Journal of Algorithms, 34:109-127 (2000) 


ABD95
Attiya H., Bar-Noy A. and Dolev D.,
Sharing memory robustly in  message passing systems. 
Journal of the ACM, 42(1):121-132 (1995)


AR98
Attiya H. and Rachmann O.,
Atomic snapshots in O(nlog n) operations. 
SIAM Journal of Computing,  27(2):319-340 (1998)




AW94
Attiya H. and  Welch J.L., 
Sequential consistency versus linearizability.
ACM Transactions on Computer Systems, 12(2):91-12 (1994)

AW04
Attiya H. and Welch J.L.,  
Distributed computing: fundamentals, simulations  and advanced  topics, 
(2d  Edition),  Wiley-Interscience, 414  pages (2004) 

BJ87
Birman K.  and  Joseph T.
Reliable communication in the presence of failures.
ACM Transactions on Computer Systems, 5(1):47–76 (1987)


CT96
Chandra T. and Toueg S., 
Unreliable failure detectors for reliable distributed systems. 
Journal of the ACM, 43(2):225-267 (1996)


DFRR16
Delporte-Gallet  C., Fauconnier H., Rajsbaum S., and Raynal M., 
Implementing snapshot objects on top of 
crash-prone asynchronous message-passing systems.
Proc.  16th Int'l Conference on Algorithms and Architectures for
Parallel Processing (ICA3PP'16), Springer LNCS 10048,  pp. 341–355 (2016)


DGLV10 
Dutta P.,  Guerraoui R.,   Levy R., and  Vukolic M., 
Fast  access to distributed atomic memory.
SIAM Journal of  Computing, 39(8):3752-3783 (2010)


E05
Ellen F.,
How hard is it to take a snapshot? 
Proc. 31th Conference on Current Trends in 
Theory   and  Practice  of   Computer  Science (SOFSEM'05),
 Springer 3381, pp. 27-35 (2005)


EFR07
Ellen F., Fatourou P., and  Ruppert E., 
Time lower bounds for implementations of multi-writer snapshots.
Journal of the ACM, 54(6), 30 pages (2007)


 







FLP85
Fischer M.J., Lynch N.A. and Paterson M.S.,
Impossibility of distributed consensus with one faulty process. 
Journal of the ACM, 32(2):374-382 (1985)

FM03
Fischer M.J. and Merritt M.,
Appraising two decades of distributed computing theory research.
Distributed Computing,  16(2-3):239-247 (2003)
  

HNS16
Hadjistasi Th.,  Nicolaou N., and  Schwarzmann A.A., 
Oh-RAM! One and a half round read/write atomic memory.
Brief announcement.  Proc. 35th ACM Symposium on  Principles of 
Distributed Computing (PODC'16), ACM Press, pp. 353-355 (2016)








HW90 
Herlihy  M. P.  and Wing J. M.,  Linearizability: a correctness
condition  for concurrent  objects.  
ACM Transactions  on Programming Languages and Systems, 
12(3):463-492 (1990)



IR12
Imbs D. and Raynal M., 
Help when  needed, but no more:  efficient read/write partial snapshot. 
Journal of Parallel and Distributed Computing, 72(1):1-12 (2012)

ICMT94
Inoue I.,  Chen W., Masuzawa T. and Tokura N.,
Linear time snapshots using multi-writer multi-reader registers.
Proc.  8th Int'l Workshop on Distributed Algorithms (WDAG'94), 
Springer LNCS 857, pp. 130-140 (1994)


J05
Jayanti P., 
An optimal multiwriter snapshot algorithm. 
Proc. 37th ACM Symposium on Theory of Computing (STOC'05), 
ACM Press, pp. 723-732 (2005)


JFC08
Jiménez E.,  Fernández A.,  and Cholvi V.,  
A parameterized algorithm that implements sequential, causal, and cache memory 
consistencies. 
Journal of Systems and Software,  81(1):120-131 (2008)


K56
Kramer S. N., 
History Begins at Sumer: Thirty-Nine Firsts in Man's Recorded History.
University of Pennsylvania Press, 416 pages, ISBN 978-0-8122-1276-1 (1956)

L79
Lamport L., 
How to make a multiprocessor computer that correctly executes
multiprocess programs.
IEEE Transactions on Computers, C28(9):690–691 (1979)

  
L86
Lamport L.,
On interprocess communication, Part I: basic formalism. 
Distributed Computing, 1(2):77-85 (1986) 







L96
Lynch N. A.,
Distributed algorithms.
Morgan Kaufmann Pub., San Francisco (CA), 872 pages, ISBN 1-55860-384-4 (1996)

M86 
Misra  J., Axioms for memory access  in asynchronous hardware systems.   
ACM  Transactions  on Programming  Languages and  Systems,
8(1):142-153 (1986)

MPRJ17 
Mostéfaoui A., Pétrolia M.,  Raynal M., and Jard Cl., 
Atomic read/write memory in signature-free  
 Byzantine asynchronous message-passing systems.
Springer  Theory of  Computing Systems (2017)
DOI: 10.1007/s00224-016-9699-8










MR16-podc
Mostéfaoui A. and Raynal M.,
Two-bit messages are sufficient to implement  atomic read/write 
registers in crash-prone  systems. 
Proc. 35th ACM Symposium on  Principles of 
Distributed Computing (PODC'16), ACM Press, pp. 381-390 (2016)

PMMJ16
Perrin M., Mostéfaoui A., Pétrolia M., and Jard Cl., 
On composition and implementation of sequential consistency.
Proc. 30th Int'l  Symposium on  Distributed Computing (DISC'16),
Springer LNCS 9888, pp. 284-297 (2017)


R02
Raynal M., 
Sequential consistency as lazy linearizability.  
Brief announcement.
  Proc. 14th  ACM Symposium on Parallel Algorithms and Architectures
(SPAA'02), ACM press, pp. 151-152, (2002)

R10
Raynal M.,
Communication and agreement abstractions for fault-tolerant 
asynchronous distributed systems. 
Morgan & Claypool Publishers, 251 pages, ISBN 978-1-60845-293-4 (2010)


R13
Raynal M.,
Distributed algorithms for message-passing systems. 
Springer, 510 pages, ISBN 978-3-642-38122-5  (2013)


R13-1
Raynal M.,
Concurrent programming: algorithms, principles and  foundations.
Springer,  515 pages, ISBN 978-3-642-32026-2 (2013) 


RST91
Raynal M., Schiper A., and Toueg S., 
The causal ordering abstraction and a simple way to implement it.
Information Processing Letters, 39:343-351 (1991)
  

R08
Ruppert E., 
Implementing shared registers in asynchronous message-passing systems. 
Springer Encyclopedia of Algorithms, pp. 400-403 (2008)


T36
Turing A.M.,
On computable numbers with an application to the Entscheidungsproblem.
Proc. of the London Mathematical Society, 42:230-265 (1936)


V12
Vukolic M., 
Quorum systems, with applications to storage and consensus. 
Morgan & Claypool Publishers, 132 pages, ISBN 978-1-60845-683-3 (2012)










§ AN IMPLEMENTATION OF -BROADCAST  IN MESSAGE-PASSING SYSTEMS


This section  shows that the -broadcast communication abstraction is not an
oracle-like object which allows us to extend our understanding of computing,
but cannot be implemented. It describes an  implementation of  -broadcast 
in _n,t[t<n/2], which is the weakest assumption on process failures
that allows a  read/write register to be built on top of an asynchronous 
message-passing system <cit.> (see footnote <ref>).

To simplify the presentation, and without loss of generality, we consider
that the communication channels are FIFO. The associated communication
operations are denoted () and (). 




 §.§ Algorithm <ref>




  
Local variables at a process p_i
Each process p_i manages the following local
variables. 
     


  * : buffer where are stored the messages not yet
scd-delivered in a message set. 


  * : next set of messages to be scd-delivered.


  * sn_i: local sequence number (initialized to 0),
              which measures the local progress of p_i.


  * clock_i[1..n]: array of sequence numbers.
  clock_i[j] is the greatest sequence number x such that the  application
  message  identified by ⟨ x,j⟩ was in a message set scd-delivered
  by p_i.  


  



  
Operation ()
When p_i invokes (m), where m is an application message,
it sends the message (m,i,sn_i,i,sn_i) to itself
(this simplifies the writing of the algorithm), and waits until
it has no more message from itself pending in _i, which means
it has scd-delivered a set containing m.

A protocol message () (line <ref>) is made up of five
fields: the associated application message m, and two pairs, each
made up of a sequence number and a process identity.  The first pair
(sd,sn) is the identity of the application message, while the second
one (f,) is the local progress () of the forwarder process
𝑝_𝑓 when it forwards this protocol message.




  
Reception of  (m,sd,,f,)
When a process p_i receives such a protocol message, it first
invokes (m,sd,,f,) to participate in the reliable
broadcast of this message (line <ref>), and then
invokes () to see if a message set can be scd-delivered
(line <ref>).




  
Procedure ()
This procedure can be seen as an enrichment (with the fields f and )
of the reliable broadcast implemented by the messages
(m,sd,,-,-).
Considering such a message (m,sd,,f,), 
m was scd-broadcast by p_sd at its local time , and
relayed by the forwarding process  p_f at its local time .

If ≤  clock_i[sd], p_i has already  scd-delivered a message set
containing m (see lines <ref> and <ref>). 
If > clock_i[sd], there are two cases. 



  * The message m is not in .
  In this case, p_i creates a quadruplet msg, and  adds it to 
   (lines <ref>-<ref>). This quadruplet 
  ⟨ msg.m, msg.sd,msg.f,msg.cl⟩ is such that



  * the field msg.m contains the  application message m,


  * the field msg.sd contains the id of the sender of this application message,


  * the field  msg.sn contains the local date associated with m by its sender, 


  * the field msg.cl is an array of size n, such that msg.cl[x] = sequence
number (initially +∞)
associated with m by p_x when it broadcast (msg.m,-,-,-,-).
This last field is crucial in the scd-delivery of a message set containing m.

After the quadruplet msg has been built, p_i first adds it to
 (line <ref>), and invokes
(line <ref>)
 (m,sd,,i,sn_i) to implement the
reliable broadcast of m identified by ⟨ sd,⟩.
Finally, p_i records its progress by increasing sn_i
(line <ref>).


  * There is a quadruplet  msg in  
associated with m, i.e., msg=⟨ m, sd,-, -⟩∈
(predicate of line <ref>). In this case,  p_i  assigns 
to msg.cl[f] (line <ref>), thereby indicating that
m was known and forwarded by 𝑝_𝑓 at its local time .










  
Procedure ()
When it executes (), p_i first computes  the set
 of the quadruplets msg containing  application
messages m which have been seen by a majority of processes
(line <ref>).  From p_i's point of view, a message has been
seen by a process 𝑝_𝑓 if msg.cl[f] has been set to a
finite value (line <ref>).

If a majority of processes received first a message
(m',-,-,-,-) and later another message (m,-,-,-,-),
it might be
that some process p_j scd-delivered a set containing m' before
scd-delivering a set containing m.  Therefore, p_i must avoid 
scd-delivering a set containing m before scd-delivering a set containing m'.
This is done at line <ref>, where p_i withdraws the
quadruplet msg corresponding to m if it has not enough information
to deliver m' (i.e. the corresponding msg' is not in
_i) or it does not have the proof that the situation cannot 
happen, i.e. no majority of processes saw the message
corresponding to msg before the message corresponding to msg'.


If  is not empty after it has been purged
(lines <ref>-<ref>), p_i computes a
message set to scd-deliver.  This set ms contains all the application
messages in the quadruplets of 
(line <ref>).  These quadruplets are withdrawn from
 (line <ref>).  Moreover, before this
scd-delivery, p_i needs to updates clock_i[x] for all the entries
such that x=msg.sd where msg∈
(line <ref>).  This update is needed to ensure that
the future uses of the predicate of line <ref> are correct.





 §.§ Proof of Algorithm <ref>




If a process  scd-delivers a set containing  m, some
process invoked (m).



  If process p_i scd-delivers a set containing a message m, it
  has previously added into  a quadruplet msg
  such that msg.m=m (line <ref>), for which it
  has fifo-received at least n/2 (m,-,-,-,-)
  messages. The first of these messages ever sent was sent
  after a process invoked (m).
  





No process scd-delivers  the same message twice. 



  After a message m scd-broadcast by p_sd with a sequence number
   is scd-delivered by p_i, clock_i[sd] ≥ thanks
  to line <ref> and there is no msg∈_i with
  msg.sd=sd and msg.sn=, as it was removed on line
  <ref>.  Thanks to line <ref>, no such
  msg' will be added again in . As  is
  defined as a subset of  on line <ref>, m
  will never be scd-delivered by p_i again.
  


 
If a message (m, sd, ,i, sn_i) is broadcast by a non-faulty
process p_i, then each non-faulty process p_j broadcasts a single
message (m, sd, ,j, sn_j).


  First, we prove that p_j broadcasts a message
  (m, sd,,j, sn_j).
  As p_i is non-faulty, p_j will eventually receive the
message sent by p_i. At that time, if > clock_j[sd], after
the condition on line <ref> and whatever its result,
_i contains a value msg with msg.sd = sd and msg. =. That msg was inserted at line <ref> (possibly
after the reception of a different message), just before p_j sent a
message (m, sd, , j,sn_j) at line <ref>.
Otherwise, clock_j[sd] was incremented on line <ref>,
when validating some msg'  added to  after p_j
received a (first) message (msg'.m,sd,,f, clock_f[sd])
from p_f. Because the messages () are fifo-broadcast
(hence they are  delivered in their sending order), p_sd sent
message (msg.m, sd, ,sd, ) before
(msg'.m, sd, clock_j[sd],  sd,clock_j[sd]),
and all other processes only forward
messages, p_j received a message (msg.m, sd, ,-,-)
from p_f before the message (msg'.m, sd, clock_j[sd],-,-).
At that time, > clock_j[sd], so the previous case applies.

After p_j broadcasts its message (m, sd, ,j, sn_j) on
line <ref>, there is a msg∈_j with ts(msg)
= ⟨ sd, ⟩, until it is removed on
line <ref> and clock_j[sd] ≥. Therefore, one of the
conditions at lines <ref> and <ref> will
stay false for the stamp ts(msg) and p_j will never execute
line <ref> with the same stamp ⟨ sd, ⟩ later.





  
  Let p_i be a process that  scd-delivers a set ms_i containing a
  message m and later  scd-delivers a set ms'_i containing a message
  m'.  No process p_j  scd-delivers first a set ms'_j containing
  m'  and later a set ms_j containing m.



  Let us suppose there are two messages m and m' and two processes
  p_i and p_j such that p_i scd-delivers a set ms_i
  containing m and later scd-delivers a set ms'_i containing m'
  and p_j scd-delivers a set ms'_j containing m' and later
  scd-delivers a set ms_j containing m.

  When m is delivered by p_i, there is an element msg∈_i such that msg.m = m and because of line
  <ref>, p_i has received a message (m,-,-,-,-)
  from more than n/2 processes.
  
  
  
  * If there is no element msg'∈_i such that msg'.m =
    m', since m' has not been delivered by p_i yet, p_i has not
    received a message (m',-,-,-,-) from any process
    (lines <ref> and <ref>). Therefore,
    because the communication channels are FIFO, more than
    n/2 processes have sent a message (m,-,-,-,-)
    before sending a message (m',-,-,-,-).
    
   
  * Otherwise, msg'∉_i after
    line <ref>. As the communication channels are
    FIFO, more than n/2 processes have sent a message
    (m,-,-,-,-) before a message (m',-,-,-,-).
  

  Using the same reasoning, it follows that
  when m' is delivered by p_j, more than
  n/2 processes have sent a message (m',-,-,-,-) before
  sending a message (m,-,-,-,-).  There exists a process p_k in
  the intersection of the two majorities, that has both sent a message
  (m',-,-,-,-) before sending (m,-,-,-,-) and sent a message
  (m',-,-,-,-) before sending (m,-,-,-,-).
  However, by Lemma <ref>, p_k can only send one message
  (m',-,-,-,-) and one message (m,-,-,-,-), which leads
  to a  contradiction.











 
  If a message (m, sd, ,i, sn_i) is fifo-broadcast
  by a non-faulty
  process p_i, this process  scd-delivers a set containing m.



  Let p_i be a non-faulty process.   For any pair of messages
  msg and msg' ever inserted
  in ,  let ts = ts(msg) and  ts' = ts(msg').
  Let  →_i be the dependency relation defined  as follows:
  ts →_i ts' def=|{j : msg'.cl[j] < msg.cl[j]
  }| ≤n/2 (i.e. the dependency does not exist if p_i
  knows that a majority of processes have seen the first update
  –due to msg'– before the second –due to msg–).
  Let →_i^⋆ denote the transitive  closure of →_i.
  
  Let us suppose (by contradiction) that the timestamp ⟨ sd,
  ⟩ associated with the message m (carried by the
  protocol message (m, sd, ,i, sn_i) fifo-broadcast by
  p_i), has an infinity of predecessors according to
  →_i^⋆.  As the number of processes is finite, an
  infinity of these predecessors have been generated by the same
  process, let us say p_f.  Let ⟨ f, sn_f(k) ⟩_k∈ℕ be the infinite sequence of the timestamps associated
  with the invocations of the () issued by p_f. The
  situation is depicted by Figure <ref>.
  
  As p_i is non-faulty, p_f eventually receives a message
  (m,sd, , i, sn_i), which means p_f broadcast an
  infinity of messages (m(k), f, sn_f(k), f, sn_f(k)) after
  (m, sd, , f, sn_f). Let ⟨ f, sn_f(k1) ⟩
  and ⟨ f, sn_f(k2) ⟩ be the timestamps associated with the
  next two messages sent by p_f, with sn_f(k1) < sn_f(k2).  By
  hypothesis, we have ⟨ f, sn_f(k2) ⟩→_i^⋆⟨ sd, ⟩.  Moreover, all processes received their
  first message (m, sd, , -,-) before their first
  message (m(k), f, sn_f(k), -,-), so ⟨ sd, ⟩→_i^⋆⟨ f, sn_f(k1) ⟩. Let us
  express the path ⟨ f, sn_f(k2) ⟩→_i^⋆⟨ f, sn_f(k1) ⟩:
 ⟨ f, sn_f(k2) ⟩ =
  ⟨ sd'(1), sn'(1) ⟩→_i ⟨ sd'(2), sn'(2)
  ⟩→_i …→_i ⟨ sd(m), sn'(m)
  ⟩ = ⟨ f, sn_f(k1) ⟩.

  
  In the time interval starting when p_f sent the message
  (m(k1), f, sn_f(k1), f, sn_f(k1)) and finishing when it
  sent the the message (m(k2), f, sn_f(k2), f, sn_f(k2)),
  the waiting condition of line <ref> became true, so p_f
  scd-delivered a set containing the message m(k1), and according
  to Lemma <ref>, no set containing the
  message m(k2). Therefore, there is an index l such that process
  p_f delivered sets containing messages associated with a timestamp
  ⟨ sd'(l), sn'(l) ⟩ for all l'>l but not for
  l'=l. Because the channels are FIFO and thanks to
  lines <ref> and <ref>, it means that a
  majority of processes have sent a message (-, sd'(l+1),
  sn'(l+1),-,-) before a message (-, sd'(l), sn'(l),-,-),
  which contradicts the fact that ⟨ sd'(l), sn'(l) ⟩→_i ⟨ sd'(l+1), sn'(l+1) ⟩.

  Let us suppose a non-faulty process p_i has fifo-broadcast a
  message (m, sd, ,i, sn_i)
  (line <ref>).  It inserted a quadruplet msg with
  timestamp ⟨ sd, ⟩ on line <ref>
  and by what precedes, ⟨ sd, ⟩ has a finite number
  of predecessors ⟨ sd_1, sn_1⟩, …, ⟨ sd_l,
  sn_l⟩ according to →_i^⋆.  As p_i is
  non-faulty, according to Lemma <ref>, it eventually
  receives a message (-,sd_k, sn_k,-,-) for all 1≤ k ≤
  l and from all non-faulty processes, which are in majority.

  Let 𝑝𝑟𝑒𝑑 be the set of all quadruplets msg' such that
  ⟨ msg'.sd, msg'.⟩→_i^⋆⟨ sd,
  ⟩.  Let us consider the moment when p_i receives the
  last message (-,sd_k, sn_k, f, sn_f) sent by a correct
  process p_f.  For all msg'∈𝑝𝑟𝑒𝑑, either msg'.m has
  already been delivered or msg' is inserted _i on
  line <ref>.  Moreover, no msg'∈𝑝𝑟𝑒𝑑
  will be removed from _i, on line <ref>,
  as the removal condition is the same as the definition of
  →_i.  In particular for msg' = msg, either m has
  already been scd-delivered or m is present in _i on
  line <ref> and will be scd-delivered on
  line <ref>.  







If a non-faulty process scd-broadcasts a message m, it scd-delivers
a message set containing m.



  If a non-faulty process scd-broadcasts a message m, it sends a
  message (m, i, ,i,) on
  line <ref>, so it scd-delivers a message set
  containing m by lemma <ref>.
  





If a non-faulty process scd-delivers a message m, every  non-faulty process
scd-delivers a message set containing m.



  Suppose a non-faulty process p_i scd-delivers a message m. At
  line <ref>,
  there is msg∈_i such that msg.m = m.
  At line <ref>, msg∈_i, and 
  msg was inserted in _i at line <ref>,
  just before p_i sent message (m, sd, ,i, sn_i).
  By Lemma <ref>, every non-faulty process p_j sends
  a message (m, sd, ,j, sn_j), so by Lemma <ref>,
  p_j scd-delivers a message set containing m.
  






Algorithm <ref>
implements the -broadcast communication abstraction
in _n,t[t<n/2]. Moreover, it requires O(n^2)
messages per invocation of (). 



The proof follows from
Lemma <ref> (Validity), 
Lemma <ref> (Integrity), 
Lemma <ref> (MS-Ordering), 
Lemma <ref> (Termination-1), and
Lemma <ref> (Termination-2).

The  O(n^2) message complexity comes from the fact that,
due to the predicates of line <ref> and <ref>,
each application message m is forwarded at most once by each process
(line <ref>).
    



The next corollary follows from (i)
Theorems <ref>  and <ref>, and (ii) 
the fact that the constraint
(t<n/2) is an upper bound on the number of faulty processes
to build a read/write register (or snapshot object) <cit.>.



Algorithm <ref> is resiliency optimal. 
 




§ BUILDING AN MWMR ATOMIC REGISTER ON TOP
  OF _N,T[]



This appendix shows the genericity dimension of
Algorithm <ref>.
It presents trivial simplifications of it, which build MWMR
atomic registers and MWMR  sequentially consistent registers. 






 §.§ The algorithm


Let  denote the MWMR atomic read/write register that is built.
The algorithm that builds it is a trivial simplification of the
snapshot Algorithm <ref>,
namely its projection on a single MWMR atomic register.


  is now locally represented 
by a  local variable reg_i and the associated timestamp ts_i
initialized to ⟨ 0,-⟩.  The message sent at
Line <ref> is now (v,⟨ ts_i.date_i+1,i⟩),
and the predicate of line <ref> simplifies to  
“there are messages ())”.






 §.§ Proof of the algorithm



The proof is a simplified version of the proof of
Theorem <ref>. For self-completeness,
we give here its full proof even if some parts of it are
“cut-and-paste” of parts of proofs given in Section <ref>. 
As in that section, 
let us associate a timestamp ts() with each operation () 
as follows (this is the place where the proof is simplified 
with respect to a snapshot object). 



  * Case  ()=(v). Let p_i be the invoking process;
  ts() is the timestamp of v 
  as defined by p_i at line <ref>, i.e.,
  ⟨ ts_i.date+1, i⟩. 

  

  * Case ()=(). Let w be the value returned by
  the read;  ts() is then the timestamp associated with w at
  line <ref> by its writer. 



Let 1 and 2 be any two operations. The relation
≺ on the whole set of operations is defined as follows:
 1 ≺2 if 1 terminated before 2 started. 
It is easy to see that ≺ is a real-time-compliant partial order 
on all the operations.


The reader can easily check that the statement and the  proof of
Lemma <ref> (applied to the termination of read and
write operations), and Lemma <ref> (applied
to the total order on the write operations, compliant with both
the sequential specification of a register, and their real-time occurrence
order)  remain valid for the algorithm suited to an MWMR atomic read/write
register.  The next lemma addresses the read operations (which are simpler
to manage than snapshot operations). 




 
 The read/write register  is linearizable.




Let us now insert each read operation in the previous (real time compliant)
total order  as follows.

Let 1() be a read operation  whose timestamp is
⟨ date1, i ⟩. This operation is inserted just after the
write operation  1()  that has the same timestamp
(this write wrote the value  read by 1()).
Let us remark that, as  1() obtained the value timestamped
⟨ date1, i ⟩,  it  did not terminate  before  1()
started.  It follows that the insertion of 1() into the total order
cannot violate the real-time order between 1() and  1().

Let us consider the operation  2() that follows
1() in the write total order. 
If 1() ≺2(), the placement of 1()
in the total order is real-time-compliant.
If  (1() ≺2()), due to the timestamp obtained by 
1(), we cannot  have 2()≺1().
It follows that in this  case also, the placement of 1()
in the total order is real-time-compliant.

Finally, let us consider two read operations 1() and 2()
which have the same timestamp  ⟨ date, i ⟩ (hence, they read
from the same write operation, say 1()). 
Both are inserted after  1() in the order of their invocations (if 
1() and 2() started simultaneously, they are  inserted
according to the order on the identities of the processes that invoked them).
Hence,  the read and write operations are linearizable, which concludes
the proof of the lemma.






The read/write register 
is an MWMR atomic read/write register.



The proof follows from Lemma <ref>,
Lemma <ref>,
and Lemma <ref>. 








 §.§ The case of an SWMR atomic register

When the register  can be written by a single process (say p_k), 
the algorithm simplifies. The timestamps disappear at all processes, and
as only the writer p_k can invoke .(), 
it  manages a simple  date date_k (which is actually
a sequence number). The modifications are:



  * Line <ref>   becomes:
date_k← date_k+1;  (v,date_k). 



  * The lines <ref>-<ref> become:


aaaaaaaaaaaaaaaaaāaāaaāaaaaa if (̄there are messages ()) 


 then l̄ēt̄ date be the maximal date in
                   the messages () received;



   reg_i← the value associated with date

  end if.
 



Let us remark that, due to the Boolean _k, the writer p_k
scd-delivers message sets containing at most one message (). 





 §.§ On sequentially consistency




  
The case of an MWMR sequentially consistent register
As indicated in the Introduction, sequential consistency was introduced
in <cit.>. It is atomicity minus the  requirement stating that
“if  an operation op1 terminates before an operation op2 starts, then 
op1 must appear before op2 in the sequence of the read and write
operations”. As noticed in <cit.>, sequential consistency can be
seen as a weakened form of atomicity, namely lazy linearizability.
The composition of sequentially consistent registers is investigated
in <cit.>. The algorithm for sequential consistency
presented in <cit.> and Algorithm <ref>
are based on similar principles. 
The constraint (t<n/2) is also  a necessary and sufficient condition to
implement  a sequentially consistent read/write register
in _n,t[∅]. 

The reader can check that an algorithm building a  a sequentially
consistent MWMR read/write register can easily be obtained from
Algorithm <ref> as simplified in
Section <ref>.
One only needs to suppress the synchronization messages ()
which ensure the compliance with respect to real-time.
The concerned lines are  lines <ref>-<ref>
(read synchronization), and lines <ref>-<ref>
(write synchronization). In a simple way, this  shows the versatility
dimension of Algorithm <ref>.




  
From sequential consistency to atomicity
Given a sequentially consistent snapshot object,
Algorithm <ref> builds the
-broadcast communication abstration.  (As the reader can check,
this follows from the fact that, when looking at its proof, this
algorithm relies only on the fact that the operations on the snapshot
object can be totally ordered.)  Hence, using on top of it the
-broadcast-based Algorithm <ref>, we obtain
an atomic snapshot object.  It follows that, thanks to SCD-broadcast,
the algorithms presented in the paper allow a sequentially consistent
snapshot object to be transformed into an atomic snapshot object
(and it is known that –differently from sequential consistent objects– 
atomic objects are composable for free <cit.>). 





