Multiwriter Atomic Registers and bounded timestamps

Uri Abraham Department of mathematics and computer science Ben-Gurion University, Be’er Sheva, ISRAEL.

January 5, 1996

Abstract

The problem of implementing timestamps with bounded values is investigated, and its connection with the Multiwriter Atomic Register Problem is established in an unexpected way: Whereas in the unbounded case timestamps can be used to implement an atomic register, in the bounded case, as we show, it is the solution to the Multiwriter Atomic Register Problem which is extended in order to implement bounded timestamps. A new type of protocol for atomic registers is identified here.

1 Preface

The Multiwriter Atomic Register Problem dealt with in this paper is the problem of devising a protocol which implements an n-writer, m-reader atomic register with 1-writer, m-reader atomic registers. (A variant of this problem is to use point-to-point registers instead of the 1-to-m registers.) It is required that these protocols are WAIT free: The execution of the protocol consists of a fixed number of read/write events which only depends on the number of processes involved and not on the particular system execution.

The use of unbounded timestamps can easily solve the Multiwriter Atomic Register Problem, as we are going to show in the next section. This is wellknown (see the attempt by Vitanyi and Awerbuch [1986]) but the problem asks for solutions with bounded registers.

The Timestamp Problem is to devise a protocol for implementing timestamps with bounded data-types. Israeli and Li [1987] and Dolev and Shavit [1989] formalized this problem and gave solutions. In this formalization there are N writing processes Writer_{i}, 1 ≤ i ≤ N, and Scanner processes. A SCAN executed by a scanner returns an N-tuple of values written by Writer_{i} events, and it also returns an ordering on these writes which agrees with a definable global order on all the Writer events. A complete and detailed definition will be given later.

In this paper a solution to the bounded timestamps problem is given in which only 2N^{2} reads are required in a SCAN operation; this is more economical than the 8N^{2} log N reads required by the Dolev and Shavit protocol (our WRITE protocol, however, is more involved than theirs). Our solution to the bounded timestamps problem is based on a solution to the Multiwriter Atomic Register Problem with a special feature. This special feature is the following: In any system execution H = (H, <_{H}, G) implemented by the protocol, there is a linear order, ⇒, extending <_{H}, defined on the protocol’s WRITE events, such that this definition does not depend on the READ events, and such that an augment of H extends ⇒ and serializes all the READ and WRITE events.

The paper is organized as follows: The Introduction gives formal definitions of some of the notions used in the paper. The section of the unbounded timestamps presents the (well known) unbounded timestamp protocol and then an economical variant of this protocol is given. In this variant Writers do not have to read long messages of other Writers, and a Reader needs to read only two messages by the Writer it decided to return. In this variant, however, each message register is carrying two messages: a new message and an old one. Sections 4, 5 and 6 bring, in a modular fashion, the READ-WRITE protocol. By this modularity the protocol’s correctness is proved in at least two stages: In one stage high-level specifications are stated, and it is proven that in any system execution in which they hold, the register R is atomic. In the lower-level stage the protocol is described and it is shown that the specifications are met whenever the protocol is used. Since the protocol is quite complex, a module of the protocol is identified and studied separately (the CHANGE/REPORT protocol in Section 5).

Section 6 contains the bounded timestamps protocol. An extended abstract of this paper was distributed in June 1990 (“A sketch for a Time-Stamp scheme”).

2 Introduction

This introduction contains a short description of some notions from the theory of interprocess communication develloped by L. Lamport [1986], and V. Pratt [1986] that will be used in the sequel: System execution, Atomic and regular registers. The notions of higher-level and lower-level views will be described in Section 3.8 through an example. For a full treatment of this theory, the reader is referred to the above cited references. A new family of atomic registers is introduced: “atomic registers with writer’s definable global-order”. Three axioms are stated for this family of registers in Section 2.1, and a proof is given that atomicity is implied by these three axioms. The READ / WRITE protocols given in the body of this paper (Sections 3.1, 6.2, 8.2) satisfy the axioms and hence implement an atomic register. A slight variation of the READ protocol describes what we call here a “full” READ. It is shown (in Section 9) how full READs can be used to implement timestamps through WRITE and SCAN operations.

A system execution S = (E, <_{S}, F) is a model describing a run of a system consisting of several communicating processes; it consists of a set of events, E, and a temporal precedence relation <_{S} on E, and a collection F of unary predicates and functions describing the nature of the events and their relationship. a<_{S}b means that ‘a totally precedes b’. a> |_{S}b is just the negation of b<_{S}a.

We say that system execution S_{1} = (E_{1}, <_{S_{1}}, F_{1}) augments system execution S_{2} = (E_{2}, <_{S_{2}}, F_{2}) iff E_{1} = E_{2}, F_{1} = F_{2} and <_{S_{2}} is a subset of <_{S_{1}}.

The processes communicate with registers (shared variables). Registers can be classified according to the list of processes allowed to write and read them. Thus an n-reader, m-writer register, is a register R which has a list of m specified processes which can write onto R , and n specified processes which can read R .

Register R is called serial in S iff all the events in E connected with R (read and write) are linearly ordered by <_{S}, and value(r) (the value returned by the read r) equalls the value of the <_{S} rightmost write w such that w<_{S}r. We say that R is atomic in S iff R is serial in some augment S_{1} of S.

Lamport [1986] classified registers according to their behaviour when reads and writes may concurrently be executed. He introduced the notion of a regular register. Register R is regular iff for any read r of R there is a write w such that

1. value(r) = value(w),

2. w> |_{S}r and there is no write w′ onto R such that w<_{S}w′<_{S}r.

Equivalently, a register is regular in S if there is a function, ω, defined on the read events of the register, and takling values write events of the register, such that the following holds:

1. value(r) = value(ω(r)),

2. ω(r)> |_{S}r and there is no write w′ onto R such that ω(r)<_{S}w′<_{S}r.

The notion of a regular register leads quit naturally to the useful notion of a regular function. Suppose that P ⊂ E is a process then a (partial) function from E into E is regular (with respect to P) iff for all x ∈ dom(f);

1. f(x)> |_{S}x.

2. Whenever f(x) ∈ P, there is no p ∈ P such that f(x)<_{S}p<_{S}x.

2.1 Axioms which imply atomicity

Our aim here is to axiomatize the behaviour of the unbounded timestamp protocol in such a way that protocols with bounded values will not be excluded. Three axioms suffice to conclude atomicity, and are satisfied in system executions in which the protocols described in this paper run.

We assume a system execution H = (H, <_{H}, G), where H = Writer ∪ Reader is a disjoint union of two (not sequential) processes. We assume that G contains a function Value(X), which is defined on H and takes on values in a certain type called message type. We also assume in G an irreflexive linear order ⇒ defined on Writer, and a function Ω : Reader → Writer. We shall call ⇒ “the Writer’s global order”, and Ω “the return function”. The following axioms may hold in H.

1. ⇒ extends <_{H}. (i.e., <_{H} ⊂⇒).

2. For a Reader event R, and a Writer event L, if L<_{H}R then (L = Ω(R) or L ⇒ Ω(R)).

3. Ω(R)<_{H}end(R). (This means that for any event X ∈ H, R<_{H}X implies Ω(R)<_{H}X.)

4. For any READ, R, Value(R) = Value(Ω(R)).

Theorem 2.1 If H satisfies the Axioms (1) − (4), then Ω and Value form an atomic register.

Proof. We have to define an augment H_{1} of H in which <_{H} is extended to a linear order <_{H_{1}}, and such that Value(R), for a READ R, is Value(W) for the <_{H_{1}}rightmost write event W such that W <_{H_{1}}R.

For each Writer event, W, let the block of W consists of W together with all Reader events, R ∈ H, such that Ω(R) = W.

First, define <_{H_{1}} on each block separately by extending <_{H} on the Reader events in the block, and setting the Writer event W to be the <_{H_{1}}first in it’s block. There is no problem in putting W first, and still extending <_{H}, because Axiom 3 implies that R<_{H}Ω(R) is not possible (otherwise Ω(R)<_{H}Ω(R) follows).

Secondly, for events X_{1}, X_{2} in different blocks, determined by the Writer events W_{1} and W_{2} respectively; set X_{1}<_{H_{1}}X_{2} iff W_{1} ⇒ W_{2}. Clearly, <_{H_{1}}is a linear order on the Reader/Writer events in H as required, and the only problem is to show that it extends <_{H}.

For each block separately, we already have seen that <_{H_{1}}extends <_{H}. So now let W_{1} ⇒ W_{2} be two Writer events; we must show that there are no X_{1}, X_{2} in the blocks of W_{1} and W_{2} such that X_{2}<_{H}X_{1}. Since W_{2}<_{H}W_{1} is not possible (as ⇒ extends <_{H}) the only possibilities one must exclude are the following:

1. W_{2}<_{H}R_{1}.

2. R_{2}<_{H}W_{1}.

3. R_{2}<_{H}R_{1}.

for Reader events R_{1} and R_{2} in the blocks of W_{1} and W_{2} respectively.

The first possibility to rule out is W_{2}<_{H}R_{1}. This is a consequence of Axiom 2 which would imply W_{2} ⇒ Ω(R_{1}) = W_{1}, in contradiction to W_{1} ⇒ W_{2}.

The second bad possibility is R_{2}<_{H}W_{1}. For the sake of a contradiction assume that it holds. By 3, Ω(R_{2})<_{H}end(R_{2}), and thus Ω(R_{2})<_{H}W_{1}. that is, W_{2}<_{H}W_{1}, which would imply W_{2} ⇒ W_{1} in contradiction to W_{1} ⇒ W_{2}.

The third possibility is R_{2}<_{H}R_{1}. As above, Ω(R_{2})<_{H}end(R_{2}) would imply Ω(R_{2}) = W_{2}<_{H}R_{1}, and we are back to case one.

Remark: The extension of <_{H} on a single block to a linear order is of course possible by a general theorem stating that any partial order can be so extended. But for those who want to do the proof in a formal way and need a definable extension we propose the following. Define the relation

A ≺ B iff ∀X(B<_{H}X → A<_{H}X).

Now ≺ is a linear preorder; that is ≺ is transitive and reflexive, and if ¬(A ≺ B) then B ≺ A. We may resolve the ordering of two events in the same equivalence class by the assumption that the set of events is a disjoint union of serial processes, P_{i}, 1 ≤ i ≤ K. Then put A < B iff A ≺ B but ¬(B ≺ A), or ∀ ≺ B and B ≺ A and A ∈ P_{i}, B ∈ P_{j} and i < j. Then < is a linear order which extends <_{H}.

3 Unbounded timestamps

This section begins with the well-known unbounded timestamp READ/WRITE protocol, and then describes a variant in which the number of messages is reduced to no more than 2 per READ or WRITE. We make here a distinction between the messages which are the data transmitted by the register and the coordinating values (such as timestamps) used by the protocol. The timestamps in this section are just integers.

The processes are the serial Writer_{i}, 1 ≤ i ≤ N, collectively called Writer, and the not necessarily serial Reader process. We assume that each Writer_{i} writes on an atomic register, Head(i), which is read by all other processes. Reader has no register to write on. Head(i) carries values of a type called head type. If h is in head type, then h has two fields: h.message is a data in message type, and h.timestamp is an integer. Initially, these registers are set to an initial value ⟨a_{0}, 0⟩ where a_{0} is an initial message. It is convenient to assume an event, Initialization_{i}, which writes this value to Head(i).

The local variables h(j), 1 ≤ j ≤ N, used by the READ and the WRITE protocols are of type head type. Initially, h(i).timestamp = 0; and at the begining of any subsequent WRITE, h(i).timestamp retains it value from the previous WRITE (it is a static variable).

The instruction ‘read(R ; x)’ is executed by a read event which returns a value and assigns that value to the variable x. The instruction ‘write(R ; v)’ assigns the value of v to register R .

WRITE (a: message type) (*by Writer_{i}*)

1. FORALL j (1 ≤ j ≤ N AND j ≠ i) DO read(Head(j); h(j))

2. h(i).timestamp := 1 + max{ h(j).timestamp | 1 ≤ j ≤ N}

3. h(i).message := a.

4. write(Head(i); h(i))

READ

1. FORALL j (1 ≤ j ≤ N) DO read(Head(j); h(j))

2. t := max{ h(j).timestamp | 1 ≤ j ≤ N} r := max{ j | h(j).timestamp = t}

3. RETURN h(r).message

In executing line 1, Writer_{i} concurrently reads all other Writers’ timestamps, and sets its own timestamp to be greater than all of their timestamps and greater than its own previous timestamp (which we assume to be initially 0). Then the Writer writes in its register the message a (given as the parameter) together with its timestamp.

The Reader concurrently reads all the Writer’s registers and records their values in the variables h(j)’s. Then it considers all the timestamps found and chooses the return index r in executing line 2.

The main issue of this paper is to change this protocol so that bounded coordinating values are sufficient. But in this section we describe another modification — to minimize the number of messages per protocol execution. The problem with the READ/WRITE protocol described above is not so much the unboundedness of the timestamps, as the need of a Writer to read all the data of its fellow Writers even though it only uses the timestamp fields. Similarly, the Reader has to read N messages in executing its protocol, even though it finally returns a single message. In practice, the assumption of unbounded timestamps is a convenient way to express the fact that the number of messages the register is transmitting is actually small, in comparison to the number of timestamps potentially available. However, the need to read long message files is really bothersome and we wish to reduce the number of messages read in the protocol. The price paid in our economical protocol is the need to use two messages (old and new) in a single WRITE.

3.1 The economical unbounded timestamp protocol

In the economical protocol presented here, the Head(i) register no longer carries a message, and it only contains a natural number—its timestamp. A special register, called Messages(i), is added. It carries values of type messages type which contains two messages in fields ‘old’ and ‘new’, and an integer in a third field, ‘timestamp’ (which contains the same timestamp as Head(i) does). Head(i) is atomic as before, but Messages(i) needs only to be regular.

The local variables h(i) are now just of type integer. The WRITE protocol uses a local variable messages, in messages type.

WRITE (a: message type) (*by Writer_{i} *)

1. FORALL j (1 ≤ j ≤ N AND j ≠ i) DO read(Head(j); h(j));

2. h(i) := 1 + max{ h(j) | 1 ≤ j ≤ N};

3. messages.old:=messages.new; messages.new:=a; messages.timestamp:= h(i)

4. 1. write(Messages(i);messages);

2. write(Head(i); h(i)).

READ

1. FORALL j (1 ≤ j ≤ N) DO read(Head(j); h(j));

2. t := max{ h(j) | 1 ≤ j ≤ N}; r := max{ j | h(j) = t};

3. read(Messages(r); m);

4. If m.timestamp = t THEN RETURN m.new ELSE RETURN m.old.

The proof that this protocol implements an atomic register, given in the rest of this section, is probably too long, and the reader may find a direct proof. However, this proof illustrates the structure of the proofs for the more complex protocols presented later in the paper.

Let L = (L, <_{L}, F) and H = (H, <_{H}, G) be a lower-level and a higher-level system executions resulting from application of the protocol. A fuller description of H and L is given for those not familiar with these notions, other readers should note the minor differences with Lamport’s original definitions (Lamport [1986]). The ‘higher-level’ events in H are formed by grouping together the ‘lower-level’ events of L belonging to a single execution of the READ/WRITE protocol. Events in H, of type READ or WRITE are implemented in L by an execution of the READ/WRITE protocol. The events in H and the events in L are partitioned into serial processes, Writer_{i}, 1 ≤ i ≤ N, and (a not necessarily linear process) Reader. Each event X ∈ H is also a subset of L, and the temporal precedence relations <_{L} and <_{H}are related by the following formula.

X<_{H}Y iff ∀x ∈ X ∀y ∈ Y (x<_{L}y).

We assume that each lower-level event x ∈ L is included in a single higherlevel event [x] ∈ H.

Besides READ and WRITE events, H contains also Initialization_{i} events. Each Initialization_{i} is a singleton containing the lower-level Initialization writes of the registers of Writer_{i}.

The set F contains predicates and functions to ensure that indeed L describes executions of the protocol. One of the functions in F is value(x) which gives the value of the read/write event x.

By definition of atomicity, the atomic registers Head(j) are serial in some augment of L, but for notational simplicity these registers are assumed to be serial already in L. F contains a function, ω, defined on lower-level reads r ∈ L of Head(j) and taking on values which are writes into Head(j), for 1 ≤ j ≤ N, such that

1. ω(r)<_{L}r, and there is no write w into Head(j) such that ω(r)<_{L}w<_{L}r,

2. value(r) = value(ω(r)).

Since register Messages(i) is regular, there is a function (denoted again ω) from the reads of Messages(i) into the writes of Messages(i), such that

1. ω is regular,

2. value(r) = value(ω(r)).

Notation (1) For any event X ∈ H and variable v local to the process executing X, v(X) is the value of v at the end of X (as it is determined in L).

(2) If φ is a statement about the variables of the process of X, then φ^{X} is obtained from φ by substituting v(X) for any variable v in φ. So for example, (v = u)^{X} is v(X) = u(X).

A priory, H includes only a few predicates which describe it as higherlevel view of L. For example Value(W) for a WRITE event is the value of the parameter, a, of the procedure executing W. For a READ event, R, Value(R) is the value returned at line 4 of the READ protocol. In the following Subsection we will define three more functions: consider, ts, and Ω; add them to G, and prove some crucial properties. The use of these functions is to transfer into H those properties of the protocol-execution in L which are required in order to prove atomicity of the implemented register. There will be no more need to investigate the protocol, and in fact we can even forget about L altogether and deduce atomicity only from these higher-level properties of the functions.

We call these properties “specifications” because they specify the higher-level behaviour, which on the one hand is ensured by the protocol, and on the other hand suffices to derive the required atomicity.

The relation X<_{H}end(Y) is defined in the following way: Let y_{0} ∈ Y be the last event in Y (i.e., ∀y ∈ Y y≤_{L}y_{0}); then define

X<_{H}end(Y) iff ∀x ∈ X (x≤_{L}y_{0}).

3.2 The functions consider, ts and Ω, and their properties

consider(X, j) is defined for a higher-level READ or WRITE X ∈ H and index 1 ≤ j ≤ N: If X is a WRITE by Writer_{j}, then consider(X, j) is the previous Writer_{j} event in H (it could well be Initialization_{j}). Else, let s ∈ X be the lower-level read of register Head(j) executed in line 1 (of the READ or WRITE protocol), and set

consider(X, j) = [ω(s)].

The following Lemma is easy to establish.

Lemma 3.1 (1) For a fixed j, consider(X, j) is a regular function from READ/WRITE into Writer_{i}.

(2) consider(X, j)<_{H}end(X).

Next, define the function ts(W) (the timestamp of W) for every Writer event. It is the value written by W in the Head register. So ts(Initialization_{i}) = 0, and for a WRITE event W by Writer_{i}, ts(W) = h(i)(W).

The two functions, consider and ts are connected in the following obvious Lemma, which expresses the fact that a WRITE chooses bigger timestamps than those considered.

Lemma 3.2 For any WRITE W and index j

ts(consider(W, j)) < ts(W)

Every READ is establishing a linear order on the set of indices [1 … N] in order to determine which is the return index r.

Definition 3.3 For any READ, R, define a relation <(R) on [1 … N] as follows. For i ≠ j, i< (R)j iff (h(i) < h(j))^{R} or (h(i) = h(j))^{R} and i < j. Whatever the values of h(i)(R) are, <(R) is clearly a linear order on [1 … N]. Since h(i)(R) is the value obtained by R in the read of Head(i), we obviously have:

Lemma 3.4 i < (R)j iff ts(consider(R, i)) < ts(consider(R, j)) or ts(consider(R, i)) = ts(consider(R, j)) and i < j.

We see in line 2 of the READ protocol, that r(R) (the value of variable r as determined by R) is the <(R) maximal index. We call r(R) ‘the return index of R’. Line 3 instructs R to read register Messages(r(R)). The value obtained is m(R), and the value returned is determined in line 4. Either m(R).new or m(R).old is returned and accordingly Ω(R) is defined in the following.

Definition 3.5 Ω(R) is a Writer event defined as follows for every READ R. Let t = t(R) be the maximal timestamp, r = r(R) be the return index, m = m(R) be the value obtained in reading Messages(r). Let s ∈ R be the lower-level read event of Messages(r) (for line 3). Then Ω(R) is defined as follows:

If m.timestamp = t then Ω(R) = [ω(s)]. Else, [ω(s)] has a predecessor event in Writer_{r} and we let Ω(R) be that predecessor. (It is possible that Ω(R) is Initialization_{r}.)

Lemma 3.6 Ω(R) is defined for any READ R, and it satisfies:

1. Value(R) = Value(Ω(R)),

2. If r is the return index of R, then

consider(R, r)≤_{H}Ω(R)<_{H}end(R)

The proof is left to the reader.

We sum up now all the higher-level properties of H gathered so far, which we need to know in order to show atomicity. For the rest of the section, READ, WRITE etc. are just abstract names and do not necessarily refer to the protocol. Higher-Level Specifications

The system execution H = (H, <_{H}, G) contains the following processes:

• Writer_{i}, for 1 ≤ i ≤ N, contains events of type WRITE, and an event Initialization_{i}. Writer_{i} is serial. Collectively, these processes are called Writer, and for X ∈ Writer_{i} i is denoted index(X).

• Reader contains events of type READ.

It is assumed that Initialization_{i}<_{H}X for any event X which is not an Initialization event. For simplicity, Initialization_{i} and Initialization_{j} are <_{H} incomparable.

The following functions are in G:

• Value(X) is of type message type. For a READ, R, Value(R) is called the ‘return’ value of R.

• consider(X, i) is defined for 1 ≤ i ≤ N and X a READ or WRITE event. consider(X, i) is a Writer_{i} event.

• ts(W) is a natural number (≥ 0) defined for every Writer event W; it is called ‘the timestamp’ of W.

• Ω(R) is a Writer event defined for every Reader event R.

Definition 3.7 For any READ event R, define the following order relation <(R) on the index set [1 … N]: i < (R)j iff ts(consider(R, i)) < ts(consider(R, j)) OR ts(consider(R, i)) = ts(consider(R, j)) and i < j.

The following properties hold:

[reg] For a fixed i, the function consider(X, i) is regular. This means that

1. consider(X, i)> |_{H}X.

2. There is no W ∈ Writer_{i} with consider(X, i)<_{H}W < X.

[mono] For every WRITE W, if V = consider(W, i) then ts(V) < ts(W).

[ret] For any READ event R, let r, the ‘return index’, be defined as the <(R) maximal index in [1 … N]. Then

1. r = index(Ω(R))

2. Value(Ω(R)) = Value(R)

3. consider(R, r)≤_{H}Ω(R)<_{H}end(R)

3.3 The specifications imply atomicity

Theorem 3.8 If system execution H satisfies all the Higher-Level Specifications listed above, then the READ/WRITE events in H and the function Value(X) establish an atomic register.

Proof: We will show that the four Axioms from the Introduction hold. Theorem 2.1 may then be used to obtain the desired atomicity. We begin by defining a global order ⇒ on the Writer events in H.

Definition 3.9 For distinct Writer events W_{1}, W_{2}: W_{1} ⇒ W_{2} iff ts(W_{1}) < ts(W_{2}) or ts(W_{1}) = ts(W_{2}) and index(W_{1}) < index(W_{2}).

Clearly, ⇒ is a linear order on Writer. To show that it extends <_{H}, we have:

Lemma 3.10 [Monotonicity] If X<_{H}Y are Writer events, then ts(X) < ts(Y).

Proof: The proof is by induction on ts(Y). If Y is an Initialization event then no X<_{H}Y exists. So assume Y is a WRITE, and hence consider(Y, i) is defined for any i.

Put i = index(X). Since X<_{H}Y, X≤_{H}consider(Y, i) (or else, by the seriality of Writer_{i}, consider(Y, i)<_{H}X is in contradiction to the regularity of consider).

By [mono], ts(consider(Y, i)) < ts(Y). Induction can be applied to Y′ = consider(Y, i) to prove that ts(X) ≤ ts(consider(Y, i)); and this proves the lemma. So Axiom 1 of Section 2.1 is proved.

Now to prove Axiom 2, suppose that L<_{H}R and we shall see that L = Ω(R) or L ⇒ Ω(R).

Let i = index(L), r = index(Ω(R)). Let M = consider(R, i). Then M is by Writer_{i}. By [reg]2 and the seriality of Writer_{i}, L<_{H}R implies L≤_{H}M (and hence, as ⇒ extends <_{H}, L = M or L ⇒ M). So it suficess to prove M = Ω(R) or M ⇒ Ω(R).

Assume first that i = r. Then [ret]3 implies M = consider(R, i)≤_{H}Ω(R). So M = Ω(R) or M ⇒ Ω(R).

Next assume i ≠ r. Then i < (R)r since r is the return index (see [ret]1). Put t_{0} = ts(consider(R, i)), t_{1} = ts(consider(R, r)). Then i < (R)r means (by Definition 3.2) that t_{0} < t_{1} or (t_{0} = t_{1} and i < r). Now, by [ret]3, consider(R, r)≤_{H}Ω(R). So by the Monotonicity Lemma ( 3.10), t_{1} ≤ ts(Ω(R)) = k. Hence t_{0} < k or (t_{0} = k, and i < r). This implies M ⇒ Ω(R).

Axioms 3 and 4 are directly stated in [ret].

4 Bounded-values protocols: An introduction

The second part of the paper is its main body, it contains three protocols with only bounded values. As the reader knows by now, the presentation of a protocol is done here in at least two stages: at the lower stage, we find the protocol’s text, the definition of the higher-level functions, and the higher-level specifications; and at the higher stages, the discussion of the consequences of these specifications. We could not decide on the best order in which these two stages should be presented. The reader inclined to the abstract may want to begin with higher-level specifications, see how they suffice to derive atomicity of the register, and then, after she is convinced of the usefulness of the specifications, agree to read the details of the lower-level implementation. To other readers it makes more sense to see first the protocol, the definition of the higher-level functions, the statement of the higher-level specifications and the proof that they hold in the higher-level system execution, and finally (only after realizing that these specifications are not vacuous) the proof of the specifications’ consequences. It is rather in this second option that we have arranged the paper, but the reader who may wish to do so can start reading section 7.

Since the protocol is quite complex, we have isolated a component and presented it before anything else: the CHANGE/ REPORT protocol. Some readers may prefer to first see the full READ / WRITE protocol, and only then concentrate on that component, and they are advised to read first section 6.

5 The CHANGE/REPORT protocol

This protocol assumes two sequential processes: Changer and Reporter executing the CHANGE and the REPORT procedures respectively. Alone, the protocol seems useless, but it is a basic unite (module) in our final READ/WRITE protocol. Its isolation may ease understanding of that protocol, and may perhaps allow for other uses as well. Formally, the notion of restriction can be used to define when protocol P_{0} is a module of protocol P_{1}: If there is a way to identify in every system execution of P_{1} a restriction which is an execution of P_{0}. It will take us too far to try to define what a restriction is in general, but in each instance where it is defined here it will be clear what we are doing.

5.1 Data-types and registers

Here we first describe the data-type used in the REPORT/CHANGE protocol.

diagonal number = A finite set containing D > 6 integers. Later this set will be defined to be = [1..4N] where N is the number of writing processes, but now there is no need for this information.

four set = Collection of all sets of ≤ 4 diagonal number.

The register owned by Reporter is called LL; it is read by Changer. The register owned by Changer is called Diagonal, and is read by the Reporter. Register Diagonal is assumed to be atomic and to carry values of type diagonal number. Register LL is regular, and carries values of type four set.

The local variables used in the protocols are the following: d_{1}, d_{2}, d_{3}, old report, report val, old diagonal, diagonal are of type diagonal number. ll is a four set. evade is a set of < D diagonal number (there is thus always a diagonal number not in evade).

Variables whose values are not yet determined at some point of the potocol by an assignment or read statement, get the same value they had at the end of the previous execution of the protocol by that process, or at the initial event of that process which is assumed to assign a value (any value) to all the variables. Such variables are sometimes called ‘static’.

5.2 The protocol

REPORT 1. read(Diagonal;d_{1});

2. write(LL; {old report, report val, d_{1}});

3. read(Diagonal;d_{2});

4. IF d_{1} ≠ d_{2} THEN

(a) write(LL; {old report, report val, d_{1}, d_{2}});

(b) read(Diagonal;d_{3});

5. (* Calculation of report val *)

(a) old report := report val;

(b) IF d_{1} = d_{2} OR (d_{1} ≠ d_{2} AND d_{2} ≠ d_{3}) THEN report val := d_{1}; (* this is case 1 *) ELSE report val := d_{2}; (* this is case 2: d_{1} ≠ d_{2} AND d_{2} = d_{3} *)

CHANGE

1. read(LL; ll);

2. evade := ll ∪ {old diagonal, diagonal}; (* evade can even contain more elements, as long as at least one diagonal number is left out *)

3. old diagonal := diagonal;

4. Assign to diagonal some diagonal number not in evade;

5. write(Diagonal;diagonal);

5.3 The functions report, avoid, and their properties

Let H = (H, <_{H}, G) and S = (E, <_{S}, F) be a higher-level view and a corresponding lower-level view system executions resulting from an application of our protocol. H includes events of type CHANGE and REPORT, which are executions of the CHANGE protocol, and the REPORT potocol respectively. Recall that each such event X in H can be viewed as a subset of E consisting of those events resulting from executing the protocol. For x ∈ X, [x] = X is the higherlevel event in H which includes x. We recall that V <_{S}r, for V ∈ H, r ∈ E, means ∀x ∈ V (x<_{S}r). ω is the regular function defined on the read events in E (i.e., reads of the registers Diagonal and LL). LL is a regular register (see Section 2). There is no loss of generality in assuming that the atomic register Diagonal is actually serial.

Besides CHANGE and REPORT events, H contains two Initialization events which preceed all other events; these are Initialization_{C} and Initialization_{R} which contain the initial writes onto Diagonal and LL respectively. The values written initially can be determined arbitrarily. It is natural to assume that the initial events determine the values of the local (static) variables too; in our case these values can also be determined arbitrarily.

The process Changer in H consists of Initialization_{C} and all the CHANGE events; similarly, Reporter is the process containing Initialization_{R} and all RE-PORT events.

We use the following notational conventions: For any variable v and execution X of a protocol, v(X) is the value of v as determined by the execution X. So, for example, if X is an execution of the CHANGE protocol, then diagonal(X) refers to the value of this variable at the end of the execution of X, i.e., the value of diagonal as set in line 4. An equation like (d_{1} = d_{2})^{R}, for example, refers to the truth-value of this statement at the end of the execution R, i.e., the truth value of d_{1}(R) = d_{2}(R).

Definition 5.1 The following functions are defined:

report: Let R be a REPORT event in H. Define a Changer event report(R) in H as follows: Let r_{1}, r_{2}, r_{3} be the three reads of Diagonal executed in lines 1, 3, and 4(b) respectively in R (r_{3} may be undefined). r_{1}<_{S}r_{2}<_{S}r_{3}.

case 1 (d_{1} = d_{2})^{R} or ((d_{1} ≠ d_{2})AND(d_{2} ≠ d_{3}))^{R}. If (d_{1} = d_{2})^{R} then R contains only two reads of Diagonal (for lines 1 and 3); and if (d_{1} ≠ d_{2})^{R} then R contains a third read of Diagonal (for line 4(b)). Let r_{0} be the first read of Diagonal in R (executed for line 1). Then [ω(r_{0})] = V_{0} is a Changer event with diagonal(V_{0}) = d_{1}(R). Since the write onto Diagonal is the last event in V_{0}, and as Diagonal is assumed to be serial, V_{0}<_{S}r_{0}. Let r be the last read of Diagonal in R, and let V be the <_{S}-rightmost Changer event such that V <_{S}r and diagonal(V) = d_{1}(R). Then define report(R) = V. In picking that rightmost V we used the finiteness requirement and the assumption that events belonging to a single process are linearly ordered by <_{H}. Observe that if R only contains two reads of Diagonal, then (d_{1} = d_{2})^{R} holds and report(R) = [ω(r)] in this case.

case 2 Not case 1. That is ((d_{1} ≠ d_{2})AND(d_{2} = d_{3}))^{R}. Let r be the third read of Diagonal in R. Then define report(R) = [ω(r)].

avoid: Suppose that C is a CHANGE event. Let r ∈ C be the read event executing line 1 for C. That is, r is the read of LL in C. Let V be the Reporter event such that ω(r) ∈ V. Then define: V = avoids(C)

Definition 5.2 Say that a Reporter event, R, is in case1 iff report val(R) = d_{1}(R). Otherwise, report val(R) = d_{2}(R) ≠ d_{1}(R), and we say that R is in case2. These cases correspond to the two cases in the definition of report (see line 5 of the REPORT protocol).

If X is an event in a serial process P, and P contains another event after X, then X^{+} denotes the event following X in P.

Lemma 5.3 1. For any Changer event C, the value diagonal(C), written onto register Diagonal, is also in evade(C^{+}) and in evade(C^{++}). Hence diagonal(C) ≠ diagonal(C^{+}), and diagonal(C) ≠ diagonal(C^{++}).

2. For any Reporter event W, report val(W) is a diagonal number which is written by all the writes onto LL in W^{+} and in W^{++}. Hence, if avoid(C) = W^{+} or avoid(C) = W^{++} then diagonal(C) ≠ report val(W).

3. If avoid(C) = W, then diagonal(C) ≠ d_{1}(W). Hence if W is in case1 then diagonal(C) ≠ report val(W).

4. Let R be a REPORT event. If report(R) = V, then diagonal(V) = report val(R).

5. report is a regular function, and report(R)<_{H}end(R).

As an example, we prove 4, but the rest of this simple proof is left to the reader. Proof of 4. Assume report(R) = V. Look at the definition of report. Suppose first R is in case 1. By the definition, diagonal(V) = d_{1}(R), and d_{1}(R) = report val(R). Suppose next that R is in case 2. Then V = report(R) = [ω(r)], where r is the third read of Diagonal in R, executed for line 4(b). By our assumption on ω, value(ω(r)) = value(r) = d_{3}(R). Since diagonal(V) = value(ω(r)), and as d_{3}(R) = d_{2}(R) = report val(R) in case2, we get diagonal(V) = report val(R) as required.

Lemma 5.4 (The report Lemma) Let W_{1} be a Reporter event; V_{1}, V_{2} be Changer events. Suppose

1. report(W_{1}) = V_{1}, and

2. V_{1}<_{H}V_{2}, and

3. diagonal(V_{1}) = diagonal(V_{2}), and

4. W_{2} = avoids(V_{2}).

Then W_{1}^{++}<_{H}W_{2}.

Proof: First observe that since diagonal(V_{1}) = diagonal(V_{2}), V_{1}^{+}<_{H}V_{2}. This follows 1 in Lemma 5.3. Next observe that by 4 there, diagonal(V_{1}) = report val(W_{1}), so that by 2, neither W_{2} = W_{1}^{+} nor W_{2} = W_{1}^{++} is possible. So we must prove that W_{1}<_{H}W_{2} to conclude the Lemma.

Assume first W_{1} is in case 1. Then W_{2} = W_{1} is not possible by 3 of 5.3, as report val(W_{1}) = diagonal(V_{1}) = diagonal(V_{2}). Let w_{1} be the first write (onto LL) in W_{1}; and let r be the last read in W_{1} (of Diagonal), of course w_{1}<_{S}r; let s be the read of LL in V_{2}. We shall prove that w_{1}<_{S}s in order to derive that w_{1}≤_{S}ω(s) and hence that W_{1}≤_{H}avoid(V_{2}).

For the sake of a contradiction assume that s> |_{S}w_{1}. Then,

V_{1}<_{H}V_{1}^{+}<_{S}s> |_{S}w_{1}<_{S}r

imply that V_{1}^{+}<_{S}r. Hence ω(r) is not in V_{1}, and thus report(W_{1}) is not [ω(r)]. Hence r is the third read of Diagonal in W_{1} and ((d_{1} ≠ d_{2})AND(d_{2} ≠ d_{3}))^{W_{1}}. (See the observation made at the end of case 1 in the definition of report.) We are going to derive a contradiction by showing that (d_{2} = d_{3})^{W_{1}}.

Let u be the write onto Diagonal ending V_{2}, then u<_{S}r is not possible, as in such a case V_{1}<_{H}V_{2} and V_{2}<_{S}r are in contradiction to the definition of report(W_{1}). Thus r<_{S}u by the seriality of Diagonal. (d_{2} = d_{3})^{W_{1}} may be derived as follows. Let r_{2} be the second read of Diagonal in W_{1}. From the protocol’s structure, w_{1}<_{S}r_{2}<_{S}r. Then s> |_{S}w_{1}<_{S}r_{2}<_{S}r<_{S}u imply that ω(r_{2}) = ω(r) and hence that (d_{2} = d_{3})^{W_{1}}.

Assume next W_{1} is in case 2, that is (d_{1} ≠ d_{2} = d_{3})^{W_{1}} and report val(W_{1}) = d_{2}(W_{1}). In this case, by definition, V_{1} = report(W_{1}) = [ω(r)], where r is the third read of Diagonal in W_{1}. Hence r<_{S}end(V_{1}^{+}), and so r<_{S}V_{2}. If w_{2} denotes the second write in W_{1} on register LL, and s denotes, as before, the read of LL in V_{2}, then w_{2}<_{S}s follows and shows that W_{1}≤_{H}W_{2}.

The equality W_{1} = W_{2} is not possible since, otherwise, ω(s) = w_{2}. In this case, report val(W_{1}) which is one of the values in w_{2} (i.e. d_{2}(W_{1})) is thus in evade(V_{2}), and then diagonal(V_{2}) ≠ report val(W_{1}). Yet diagonal(V_{1}) = report val(W_{1}), and hence diagonal(V_{1}) ≠ diagonal(V_{2}).

6 The READ/WRITE protocol

Some intuitive remarks on the READ/WRITE protocol are given first. There are N serial writing processes, Writer_{i}, 1 ≤ i ≤ N, and several Readers. The protocol’s aim is to implement a multiwriter atomic register. The protocol is such that to each WRITE event, L, of index i, an i-tuple report of (L) = (L_{1}, ..., L_{i}) is associated. L_{k} is here a WRITE event of index k ≤ i “reported by L” (any WRITE reports itself, that is, L_{i} is L).

A linear order, ⇒, is defined on the WRITE events. Suppose that report of (L) = (L_{1}, ..., L_{i}), report of (L′) = (L′_{1}, ..., L′_{i′}). Then L ⇒ L′ iff either there is some k ≤ min{i, i′} such that L_{k} ≠ L′_{k}, and for the first such k, L_{k}<_{H}L′_{k}, or else for all k ≤ min{i, i′} L_{k} = L′_{k} and i < i′.

The READ protocol is executing two reading cycles, in each cycle it reads the registers of all the Writers and it finally decides which index, r, to return and it is the value of Writer_{r} read in the second cycle which is returned.

In deciding the return index, the READ tries to estimates the Global-Order on the WRITEs it obtained in the first reading cycle and then chooses the index of the rightmost one. The first reading cycle does not contain enough information to make such an estimate and the second reading cycle is the basis on which the READ makes its decision.

6.1 Data-types and registers used

Here we first describe the data-type used in the protocol. index order = linear order of [1..N]. (N is the number of Writer processes.) diagonal number = [1..4N]. That is , a diagonal number is an integer in

the range 1-to-4N. diag order = linear order of [1..4N]. If D is of type diag order, then D is

implemented by an ARRAY [1..4N] OF [1..4N] which is a permutation. So, D[i] gives the place of the diagonal number i in this order, and hence i D j means D[i] < D[j].

base type = ARRAY [1..N] OF diag order. message type is the data type of the messages our Writer sends and Reader

receives. report type = ARRAY [1..i] OF diagonal number; i ≤ N. head type = RECORD

message : message type;

trace : diag order; report : report type; diagonal : diagonal number; END .

four set = a SET OF ≤ 4 diagonal number. The procedure PUT LAST(d : diagonal number; VAR D : diag order) removes the first item from D, shifts all numbers in D one place backwards, and puts d at the last place. Formally: PUT LAST(d; D)

1. FORALL i (1 ≤ i ≤ 4N AND i ≠ d) DO IF D[d] < D[i] THEN D[i] := D[i] − 1;

2. D[d] := 4N.

Definition 6.1 [LEXicographical order] If b = (≺_{1}, ..., ≺_{N}) is of type base type, then LEX(b) is an order defined on the sequences of length ≤ N of diagonal number by:

(s LEX (b) t)

iff either for some i, s[i] ≠ t[j] andfortheleastsuchi, s[i] ≺_{i} t[j], or else forall i ≤ min{length(s), length(t)}, s[i] = t[i] and length(s) < length(t).

The registers owned by Writer_{i} are the regular registers LL(i, k) for k < i that are read by Writer_{k}; and the atomic register Head(i) which is read by all Readers and by higher indexed Writers. These registers carry values of type four set and head type respectively. The Readers have no registers to write on.

The local variables used by the Writer are the following: head is of type head type. d_{1}, d_{2}, d_{3}, old report[k], report val[k], old diagonal, diagonal are of type diagonal number. ll[j] is a four set. evade is a set of < 4N diagonal number. i, j are indexes in [1..N].

The local variables used in READ are the following: h is of type head type. rep[i] is of type report type. basis is of type base type. < is of type index order. message[i] is of type message type.

The initial value of the registers and local variables is determined by fixing an initial message a_{0} and assigning it to all the message fields of the Head registers; and assigning some fixed diagonal number, say 4N, to all places where a diagonal number is required; the diag order trace is chosen to be the identity.

The statement “FORALL k (ϕ(k)) CONCURRENTLY DO α(k)” is executed by creating a process for each index k satisfying ϕ(k) and then executing α(k) for all these processes. The variables appearing in α(k) are local to these processes, and are not considered to be shared variables.

If T is a register, ‘d’ a field in the value type that T is carrying, then the statement ‘read(T.d;v)’ is a shorthand for: read(T;t); v := t.d. (We do not assume the possibility of a direct approach to a field of a register.)

6.2 The protocol

WRITE(of message a by Writer_{i});

1. FORALL k ≠ i, 1 ≤ k ≤ N CONCURRENTLY DO;

down IF 1 ≤ k < i THEN

(a) read(Head(k).diagonal;d_{1});

(b) write(LL(i, k)); {old report[k], report val[k], d_{1}};

(c) read(Head(k).diagonal;d_{2});

(d) IF d_{1} ≠ d_{2} THEN

i. write(LL(i, k); {old report[k], report val[k], d_{1}, d_{2}}); ii. read(Head(k).diagonal;d_{3});

(e) (* Calculation of report val[k] *) i. old report[k] := report val[k]; ii. IF d_{1} = d_{2} OR (d_{1} ≠ d_{2} AND d_{2} ≠ d_{3}) THEN report val[k] :=

d_{1}; iii. IF d_{1} ≠ d_{2} AND d_{2} = d_{3} THEN report val[k] := d_{2};

up IF (i < k ≤ N) THEN read(LL(k, i); ll[k]);

2. (* Calculation of head.diagonal *)

(a) evade := {old diagonal, diagonal} ∪ {ll[j] | i < j ≤ N};

(b) old diagonal := diagonal;

(c) Assign to diagonal some diagonal number not in evade;

(d) PUT LAST(diagonal; head.trace); head.diagonal := diagonal;

(e) report val[i] := diagonal; head.report :=report val;

3. (* final write *)

(a) head.message := a;

(b) write(Head(i);head).

FUNCTION READ

1. FORALL i(1 ≤ i ≤ N) CONCURRENTLY DO read(Head(i).report;rep[i]);

2. FOR i := 1 TO N DO (a) read(Head(i); h);

(b) basis[i] := h.trace;

(c) message[i] := h.message;

3. Let < be the order on [1..N] defined by:

i < j iff (rep[i] LEX (basis) rep[j]);

4. Let m ∈ [1..N] be the maximal index in the < order.

5. RETURN (message[m]).

6.3 The functions and their properties

Let H = (H, <_{H}, G) be a system-execution which includes events of type READ and WRITE, which are implemented in the lower-level system execution S = (E, <_{S}, F), where the implementation is induced by our protocol. ω ∈ F is the regular function defined on the read events in E (i.e., reads of the registers Head(i) etc.) Recall that each event in H can be viewed as a subset of E consisting of those events resulting from executing the protocol. For example, a READ event in H comprises 2N read events in E linearly ordered by <_{S} and corresponding in the READ protocol to the two reading cycles in lines 1 and 2. A WRITE event is an execution of the WRITE protocol, by some Writer_{i}. An Initialization event, Initialization_{i}, is assumed to be in Writer_{i} and it preceds each READ and WRITE event in H.

Definition 6.2 In the following L denotes a Writer_{i} event and R a READ event in H. Define the following functions: consider, reconsider, report, avoid, diagonal, message, <, Ω and diag order. Functions with names which appear in the protocol itself either as variables or as fields, are defined by the following convention: For a variable v and event X, the value of v at the end of X is denoted v(X). This takes care of diagonal, message and <.

consider: consider(R, i) = L iff for the read r ∈ R of Head(i) in the first reading cycle (line 1 of the protocol) ω(r) ∈ L.

reconsider: reconsider(R, i) = L iff for the read r ∈ R of Head(i) in the second reading cycle (line 2) ω(r) ∈ L. It is possible that consider(R) = Initialization_{i} or that reconsider(R) = Initialization_{i}.

For a Writer_{i} event, L, the function report(L, k) is defined for k ≤ i, and avoid(L, j) is defined for i < j as follows. For k = i, put L = report(L, i).

report(L, k), for k < i, and avoid(L, j), for j > i, may be defined as in Definition 5.3 by making the appropriate changes: Diagonal is changed to Head(k), and LL is changed to LL(j, i).

Alternatively (and equivalently) we may define report(L, k) and avoid(L, j) by looking at the resulting execution of the CHANGE/REPORT protocol as follows. For any k < i, define a restriction of H by only taking the following events: From Writer_{i} take the reads of Head(k) and writes on LL(i, k) executed in the down part of the protocol; and from Writer_{k} take the read of LL(i, k) in the up part of the protocol, and the write onto Head(k). The result is a restriction with lower-level S_{1} and higher-level H_{1} which are executions of the CHANGE-REPORT protocol. The functions report and avoid are defined in H_{1} and induce the functions report(L, k) and avoid(V, i) naturally. That is, for L ∈ Writer_{i}, V = report(L, k) if, when considered as events in H_{1}, V = report(L). And for V ∈ Writer_{k}, L = avoid(V, i) iff, when considered as events in H_{1}, L = avoid(V).

The ‘return’ function Ω is defined on any READ, R, in the obvious way: Let m = m(R) be the return index, and let r be the read in R of Head(m) executed for line 2. Then define

Ω(R) = [ω(r).

The diag order D =head.trace(L)isalinearorderof[1..N].T oobtaindiag order(L), werestrictDtothediagonalnumbersinthefollowingset : {diagonal(K) | K ∈ Writer_{i} itand K≤_{H}L}.

The results from the CHANGE/REPORT protocol can be immediately transfered to H, and in particular the Report Lemma holds in H (see Lemma 5.4).

Lemma 6.3 (The report Lemma) Let W_{1} be a Writer_{i} event, and k < i. Suppose

1. V_{1} = report(W_{1}, k)

2. V_{1}<_{H}V_{2}, V_{2} in Writer_{k},

3. diagonal(V_{1}) = diagonal(V_{2}), and

4. avoid(V_{2}, i) = W_{2}.

Then W_{1}^{++}<_{H}W_{2}.

The only ‘delicate’ point in the proof is that generally X<_{H}Y cannot be deduced from X<_{H_{1}}Y. That is, if X′ and Y′ are the events in H_{1} obtained by restrictions of X, Y ∈ H as defined above, then it is possible that X′<_{H_{1}}Y′, and yet, because X and Y are “fatter” than X′ and Y′, X<_{H}Y does not hold. In our case however, W_{1}^{++} and W_{2} belong to the same serial process, Writer_{i}, and hence the conclusion follows.

Another property lifted from S_{1} to S is that V = report(W, k)<_{H}end(W). This uses the fact that the write onto Head in V (seen as the write onto Diagonal in S_{1}) is the last event in V both when V ∈ S_{1} and whenV ∈ S.

In the following section we gather all the properties of the above higherlevel functions into an abstract setting called “higher-level specifications”, and then prove that these specifications imply atomicity.

7 Higher-level specifications for the READ-WRITE protocol.

This section defines what it means that a system-execution H = (H, <_{H}, G) meets the higher-level READ-WRITE specifications: It is required that H has the following:

[processes] H is partitioned into processes:

1. Writer_{i}, 1 ≤ i ≤ N, and each Writer_{i} is sequential. If X is a Writer_{i} event, then X^{+} and X^{−} are the events in Writer_{i} following and preceding X if they exist. That is X<_{H}X^{+} and there is no Writer_{i} event Y such that X<_{H}Y < X^{+}. Similarly, X^{−} is defined so that (X^{−})^{+} = X. Collectively, an event X in Writer_{i} is called a Writer event and i = index(X).

2. Reader_{i}, 1 ≤ i ≤ M, are collectively called the Reader process. An event in Reader is also called a READ event.

3. Each Writer_{i} event contains a special event called Initialization_{i}. It is assumed that Initialization_{i}<_{H}(X) for any event X which is not an Initialization event. Events in Writer which are not Initialization events are called WRITE events.

[constants] The following types (finite sets) are specified in H.

1. message type is the set of data values written by the Writer and read by the Reader.

2. index order is a linear (irreflexive) order on [1 … N].

3. diagonal number is the set of integers [1 … 4N].

4. diag order is the set of all linear orders on diagonal number, or on a subset of diagonal number.

[functions] The following functions exist in H:

1. For every Writer event, L: diag order(L) is a diag order; diagonal(L) is a diagonal number. Suppose that L is a WRITE event of index i. Then, for k ≤ i, report(L, k) is an event in Writer_{k}, and for the case k = i, report(L, k) = L. For j > i, avoid(L, j) is in Writer_{j}.

2. For any READ, R: consider(R, i) and reconsider(R, i) are in Writer_{i}; <(R ) is an index order; Ω(R) is a Writer event.

3. message(X) is in message type and is defined for any Reader or Writer event X.

Now the following definitions of functions are used as shorthand in the specifications which follow them.

1. report of (L) = (report(L, 1), …, report(L, i)), is defined for every WRITE L ∈ Writer_{i}.

2. For an i-tuple \overline{W} = (W_{1}, …, W_{i}), let diagonal(\overline{W}) = (diagonal(W_{1}), …, diagonal(W_{i})). So, diagonal(report of (L)) is an i-tuple of diagonal number for L ∈ Writer_{i}.

Let us repeat Definition 6.1: Definition [The LEXicographical order] If b = (≺_{1}, ..., ≺_{N}) is a sequence of diag order, then LEX(b) is an order defined on the sequences of length ≤ N of diagonal number by:

(s LEX (b) t)

iff either for some i, s[i] ≠ t[j]and for the least such i, s[i] ≺_{i} t[j], or else for all i ≤ min{length(s), length(t)}, s[i] = t[i] and length(s) > length(t).

It is a standard result that this defines a linear order on the ≤ N-sequences of diagonal number.

Finally the specifications can be expressed.

[regularity] The functions report(L, k), avoid(L, j), consider(R, i) and reconsider(R, i) are all regular. Also, report(L, k)<_{H}end(L).

[con1] consider(R, i) ≤_{H}reconsider(R, i) for any READ, R, and index i.

[con2] reconsider(R, i)<_{H}end(R) for any READ, R.

[con3] If i ≤ j ≤ N, if V is a Writer_{j} event and V<_{H}end(reconsider(R, i)), then V ≤_{H}reconsider(R, j). (It is for the sake of this property that the reads in the second reading cycle of the READ protocol are executed in order.)

[con4] If L = consider(R, i), k ≤ i, V = report(L, k), V^{∗} = reconsider(R, k), then V ≤_{H}V^{∗}.

[report] Let W_{1}, be a Writer_{i} event, and k < i. Suppose

1. V_{1} = report(W_{1}, k)

2. V_{1}<_{H}V_{2}, V_{2} in Writer_{k},

3. diagonal(V_{1}) = diagonal(V_{2}), and

4. avoid(V_{2}, i) = W_{2}.

Then W_{1}^{++}<_{H}W_{2}.

[diag] If V_{1}, V_{2} ∈ Writer_{i}, if diagonal(V_{1}) = diagonal(V_{2}), and V_{1}<_{H}V_{2}, then V_{1}^{++}<_{H}V_{2}.

[trace] For every WRITE, V, in Writer_{k}, ≺_{V} = diag order(V) is a linear order on the following subset of diagonal number: { diagonal(L) | L ∈ Writer_{k}, L≤_{H}V }. The following holds: d_{1} ≺_{V} d_{2} iff L_{1}<_{H}L_{2} where L_{i}, for i = 1, 2 is the ≤_{H}rightmost Writer_{k} event such that L_{i}≤_{H}V and diagonal(L_{i}) = d_{i}.

[lex] For a READ, R, put b = (≺_{1}, …, ≺_{N}) where ≺_{i}= diag order(reconsider(R, i)) for 1 ≤ i ≤ N. Then i < (R)j iff diagonal(report of (consider(R, i)))LEX (b)diagonal(report of (consider(R, j))).

[return] For any READ, R:

1. message(Ω(R)) = message(R)

2. Let m ∈ [1 … N] be the <(R) maximal index. Then

(a) m = index(Ω(R))

(b) reconsider(R, m)≤_{H}Ω(R)<_{H}end(R)

7.1 Consequences of the specifications: Atomicity

Theorem 7.1 Assume that the higher-level specifications hold in a system execution H. Then the READ-WRITE events form an atomic register.

The proof is carried on by showing that the four Axioms of Section 2.1 hold.

Definition 7.2 Using the fact that the events in each Writer process are linearly ordered, a Global-Order, ⇒, is defined on the WRITE events as follows. Suppose that report of (L) = (L_{1}, ..., L_{i}), report of (L′) = (L′_{1}, ..., L′_{i′}). Then L ⇒ L′ iff either there is some k, k ≤ min{i, i′}, such that L_{k} ≠ L′_{k}, and for the first such k L_{k}<_{H}L′_{k}, or else for all k ≤ min{i, i′} L_{k} = L′_{k} and i < i′.

First we show that ⇒ is a linear order on Writer which extends <_{H}. The fact that ⇒ is a linear order is a standard result on the lexicographical order of finite sequences, and the fact that each Writer_{i} is sequential is used here.

To see that ⇒ extends<_{H}, argue as follows: Assume L_{1}<_{H}L_{2}. Then for every k ≤ m = min{index(L_{1}), index(L_{2})}, by [regularity], report(L_{1}, k) ≤_{H} report(L_{2}, k). Because otherwise, V = report(L_{2}, k)<_{H}report(L_{1}, k)<_{H}end(L_{1}), implies report(L_{1}, k)<_{H}L_{2} in contradiction to the regularity of report. If strong precedence (<_{H}) holds for some k as above, then L_{1} ⇒ L_{2}. Otherwise, equality holds for all such k’s, and we have to show then that index(L_{1}) < index(L_{2}). Put i = index(L_{1}), j = index(L_{2}), and suppose towards a contradiction that j ≤ i. Then j = m and so report(L_{1}, j) = report(L_{2}, j) by our assumption that equality holds for all k ≤ m. Yet report(L_{2}, j) = L_{2}, and report(L_{1}, j)> |_{H}L_{1} by regularity of report. This contradicts L_{1}<_{H}L_{2}.

Axioms 3 and 4 are explicitely mentioned in [return]. To prove Axiom 2, we first need the following:

Lemma 7.3 (Main Lemma) Suppose R is a READ, L_{1} = consider(R, i), L_{2} = consider(R, j), and V = reconsider(R, i). Suppose that L_{1} ⇒ L_{2}, but j < (R) i. Then L_{1}^{+}<_{H}V. (L_{1}^{+} is the WRITE of index i succeeding L_{1}.)

Proof. There can be two reasons for L_{1} ⇒ L_{2}. Assume first the ‘else’ clause of Definition 7.1. i < j and r_{1} = report of (L_{1}) is an initial segment of r_{2} = report of (L_{2}). Then diagonal(r_{1}) is an initial sequence of diagonal(r_{2}), and, by [lex], i < (R)j.

Next assume that the reason for L_{1} ⇒ L_{2} is that for some k < min{i, j}, for V_{1} and V_{2} of index k, V_{1} = report(L_{1}, k), V_{2} = report(L_{2}, k), and V_{1}<_{H}V_{2}; and for all l < k, report(L_{1}, l) = report(L_{2}, l). So, the two sequences:

diagonal(report of (consider(R, i)))

and diagonal(report of (consider(R, j))),

do not differ before the k-th coordinates: diagonal(V_{1}) and diagonal(V_{2}). since j < (R)i, by [lex], diagonal(V_{2}) ⪯_{k} diagonal(V_{1}), for ≺_{k}= diag order(V^{∗}); where V^{∗} = reconsider(R, k). [con4] may be applied to L_{2} = consider(R, j), and V_{2} = report(L_{2}, k) to yield V_{2}≤_{H}V^{∗}. By [trace], it follows that for some V_{3} of index k, V_{2}≤_{H}V_{3}≤_{H}V^{∗} and diagonal(V_{1}) = diagonal(V_{3}). [report] applied to L_{1} and V_{1} = report(L_{1}, k), and V_{1}<_{H}V_{3}, implies that L_{1}^{++}<_{H}W_{2} where W_{2} = avoid(V_{3}). By regularity of avoid, W_{2}> |_{H}V_{3}, and hence W_{2}> |_{H}V^{∗}. This implies L_{1}^{++}<_{H}end(V^{∗}). Hence, by [con3], L_{1}^{++}≤_{H}reconsider(R, i). So L_{1}^{+}<_{H}V.

Corollary 7.4 Let R be a READ event. Suppose j <(R) i, and reconsider(R, i) = V. If L is in Writer_{j}, and L<_{H}R, then L ⇒ V.

Proof. Assume towards a contradiction that the Corollary does not hold. Since index(V) = i, and index(L) = j, and i ≠ j, V ≠ L. So, if L ⇏ V, then V ⇒ L. Since L<_{H}R is assumed, L≤_{H}consider(R, j) = L_{2} by the regularity of consider.

By [con1], L_{1} = consider(R, i)≤_{H}reconsider(R, i) = V. So we have: L_{1}<_{H}V, V ⇒ L, L<_{H}L_{2}; thus L_{1} ⇒ consider(R, j) = L_{2}. By the Main Lemma, applied to R, L_{1}^{+}<_{H}V. But V ⇒ L implies V > |_{H}L, and so we have L_{1}^{+}<_{H}V > |_{H}L<_{H}R. This implies L_{1}^{+}<_{H}R in contradiction to the regularity of consider.

Corollary 7.5 (Axiom 2) It is never the case that Ω(R) ⇒ L<_{H}R.

Proof. Put j = index(L), i = index(Ω(R)). In case i = j, as Writer_{j} is serial and ⇒ extends <_{H}, Ω(R) ⇒ L implies Ω(R)<_{H}L, and then L<_{H}R would contradict [return] and the regularity of reconsider.

In case i ≠ j, j < (R)i (by [return]). If L<_{H}R, then Corollary 7.4 implies L ⇒ reconsider(R, i). But reconsider(R, i)≤_{H}Ω(R) by [return], and so L ⇒ Ω(R).

8 An efficient READ/WRITE protocol

Analysing the READ/WRITE protocol of Section 6.2, we see that, even though the Writers are not interested in messages, they must read the registers Head(k) of their fellow (lower-indexed) Writers, including the messages found there. Likewise, the Reader has to read 2N messages in the two read cycles—even though it is interested in a single message, the one returned. How could this number of message reading be reduced? In the following ‘economical’ protocol, Writers do not read messages at all (but each WRITE is writing two messages— an old and a new message), and the number of message reading in a READ is reduced to four.

8.1 Changes to Data-types and registers

Only the changes made are described.

messages type = RECORD

old, new : message type;

diagonal : diagonal number;

END.

head type = RECORD

trace : diag order;

report : report type;

diagonal : diagonal number;

END.

The registers owned by Writer_{i} are the regular registers LL(i, k) for k < i that are read by Writer_{k}; and the atomic register Head(i) which is read by all Readers and by higher indexed Writers. And in the ‘economical’ protocol, Writer_{i} also has a regular register: Messages(i) which carry values of type messages type. Messages(i) is read by the Readers.

To the local variables used by the Writer we add old and new of type message type. To the Reader we add variables m and n of type messages type, and d of type diagonal.

The initial values of the registers and local variables is determined by fixing an initial message a_{0} and assigning it to all the message fields of the Head registers; and assigning some fixed diagonal number, say 4N, to all places where a diagonal number is required; the different orders (trace etc.) may be chosen to be the identity.

8.2 The protocol

WRITE (of message a by Writer_{i});

1. COBEGIN{FORALL k ≠ i, 1 ≤ k ≤ N };

down IF 1 ≤ k < i THEN (a) read(Head(k).diagonal;d_{1});

(b) write(LL(i, k)); {old report[k], report val[k], d_{1}};

(c) read(Head(k).diagonal;d_{2});

(d) IF d_{1} ≠ d_{2} THEN i. write(LL(i, k); {old report[k], report val[k], d_{1}, d_{2}}; ii. read(Head(k).diagonal;d_{3});

(e) (* Calculation of report val[k] *) i. old report[k] := report val[k]; ii. IF d_{1} = d_{2} OR (d_{1} ≠ d_{2} AND d_{2} ≠ d_{3}) THEN report val[k] :=

d_{1}; iii. IF d_{1} ≠ d_{2} AND d_{2} = d_{3} THEN report val[k] := d_{2};

up IF (i < k ≤ N) THEN read(LL(k, i); ll[k]); COEND

2. (* Calculation of head.diagonal *)

(a) evade := {old diagonal, diagonal} ∪ {ll[j] | i < j ≤ N};

(b) old diagonal := diagonal;

(c) Assign to diagonal some diagonal number not in evade;

(d) PUT LAST(diagonal; head.trace);

(e) report val[i] := diagonal; head.report :=report val;

(f) head.diagonal := diagonal;

3. (* final writes *)

(a) old:= new; new:= a;

(b) write(Messages(i); ⟨old; new; diagonal⟩)

(c) write(Head(i);head).

FUNCTION READ

1. FORALL i(1 ≤ i ≤ N) CONCURRENTLY DO read(Head(i).report;rep[i]); 2. FOR i := 1 TO N DO

(a) read(Head(i); h);

(b) basis[i] := h.trace;

3. Let < be the order on [1..N] defined by:

i < j iff (rep[i] LEX (basis) rep[j]);

4. Let r ∈ [1..N] be the maximal index in the < order.

5. read(Messages[r]; m);

6. IF m.diagonal ≠ basis[r][4N] THEN RETURN m.old ELSE

(a) read(Head(r).diagonal; d);

(b) IF m.diagonal = d THEN RETURN m.new ELSE

i. read(Messages[r]; n) ii. RETURN n.old.

The proof proceeds as for the previous protocol by defining the functions, and proving that the higher-level specifications of Section 7 hold. Only the definition of Ω is changed. We leave the details to the reader.

9 Bounded timestamps

This section contains an implementation of SCAN/LABEL operations which form an abstract timesstamp mechanizm. It is abstract in the sense of Dolev and Shavit, as formulated in the following subsection. Perhaps the algorithm of Israeli and Li [1988] achieves more than our algorithm in a certain sense, because it acomplishes real tags which are used as timestamps, while our algorithm only behaves as though it is using timestamped tags. Further research should elucidates this point.

9.1 The Dolev-Shavit abstract timestamp specification

We describe here the abstract approach to timestamps, proposed by A. Israeli and M. Li [1988], and pursued by D. Dolev and N. Shavit [1989]. The following discussion relates to a system execution H = (H, <_{H}, G).

Two (non sequential) processes are assumed: Labeler (used here interchangeably with Writer) and Scanner. Events in Scanner are called SCAN, and events in Labeler which are not Initialization are called LABEL (or WRITE). Labeler is partitioned into N sequential processes: Labeler_{i}, 1 ≤ i ≤ N.

The following functions and relation are assumed to be in G:

1. message(L) for a Labeler event L is in message type (a given data-type). message(L) is called “the message (data) written by L”.

2. messages(S) for a SCAN, S, is an N-tuple, ⟨messages(S)[1], …, messages(S)[N]⟩, of message type. messages(S) is called “the message sequence returned by S”.

3. <(S) for a SCAN event, S, is a linear order of the set of indices [1, …, N]. It is called “the index order returned by S”.

4. There are N functions, Ω_{i} : Scanner → Labeler_{i}, 1 ≤ i ≤ N.

5. There is a linear order, ⇒, on the events in Labeler. It is called “the global Labeler order”.

At the informal level, let us describe what it means that these form a timestamp scheme. A SCAN, S, is establishing in fact an order < (S) on the N LABEL events, Ω_{1}(S) … Ω_{N}(S), as follows. Ω_{i}(S) < (S) Ω_{j}(S) iff i < (S)j. Now the main point of a timestamp scheme is that the local orders, < (S), S ∈ Scanner, should be integrated into a global order, ⇒, on Labeler. Equivalently, what must be avoided is that for some LABEL events, L and M, both L < (S_{1}) M and M < (S_{2}) L for two SCAN events S_{1} and S_{2}.

Formally, we have the following specifications for a Timestamp Scheme to hold in a system execution H = (H, <_{H}, G). Timestamp Specification:

[processes] H is partitioned into Scanner and Labeler_{i}, 1 ≤ i ≤ N.

[functions and relation] The following functions and relation are in G:

1. message(L) for a Labeler event L is a data in message type.

2. messages(S) for a Scanner event, S, in an N-tuple of message type: ⟨messages(S)[1] … messages(S)[N]⟩.

3. <(S) for a Scanner event, S, in a linear order of the set [1 … N] of indexes.

4. For 1 ≤ i ≤ N, Ω_{i} : Scanner → Writer_{i}.

5. ⇒ is a linear order on Labeler.

[regularity] For each 1 ≤ i ≤ N, Ω_{i} is regular. that is:

1. Ω_{i}(S)> |_{H}S, and

2. there is no Writer_{i} event W such that Ω_{i}(S)<_{H}W <_{H}S.

[message] For every Scanner event, S, and index 1 ≤ i ≤ N, messages(S)[i] = message(Ω_{i}(S)).

[global coherence] For every Labeler events L and M, and Scanner event S, if L = Ω_{i}(S), and M = Ω_{j}(S), then i < (S)j iff L ⇒ M,

We are going to see next a protocol which implements operation LABEL and SCAN so that these Timestamp Specifications hold, but first we need the full READ*/WRITE protocol which is the basic module of our solution.

9.2 The full READ*/WRITE protocol

This protocol is a slight modification of the READ/WRITE protocol of Section 6 and will be an ingrediant in the Timestamp protocol brought next. The WRITE protocol is left unchanged. The READ protocol, now called READ* returns, not a single message as before, but the full array message together with the order < on [1 … N]. That is, line (e) in the READ protocol is changed into: (e)^{∗} RETURN (message, <).

The higher-level functions of section 6.3 should be changed accordingly. A new function, message^{∗}(R) : ARRAY [1 … N] OF message type, is defined on the READ^{∗} events: message^{∗}(R) = message(R) (that is, the value of this variable at the end of R). Define Ω_{i}^{∗} ∈ Writer_{i}, 1 ≤ i ≤ N, by Ω_{i}^{∗} = [ω(r_{i})] where r_{i} is the second read of Head(i) in R (done for the FOR loop of line (b)). The order ⇒ on Writer is defined as before.

9.3 The READ*/WRITE higher-level specifications

There are two processes in system execution H: Writer, which consists of the serial processes Writer_{i} for 1 ≤ i ≤ N, and Reader*. For a WRITE, W, in Writer Value(W) = message(W) is in message type; and for a READ*, R, Value(R) (the value ‘returned’ by R) consists of a pair (m, <), where m = message(R) is an N-tuple of data in message type, and < = <(R) is an order of the index set [1 … N].

1. For every Reader^{∗} event, R, Ω_{i}^{∗}(R) ∈ Writer_{i} satisfies:

(a) Ω_{i}^{∗}(R)<_{H}end(R),

(b) there is no W ∈ W riter_{i} such that Ω_{i}^{∗}(R)<_{H}W <_{H}R.

2. The function message(W) is in message type for every Writer event, and the function message^{∗}(R) is an array of size N in message type defined for every Reader event R. The following relation holds:

message^{∗}(R)[i] = message(Ω_{i}^{∗}(R)), 1 ≤ i ≤ N.

3. ⇒ is a linear order on Writer extending <_{H}. It satisfies the following: Let R be a READ* event. Suppose i < (R) j, and Ω_{j}^{∗}(R) = M. If L is in Writer_{i}, and L<_{H}R, then L ⇒ M. (See Corollary 7.4.)

9.4 The SCAN/LABEL protocol

We assume operations of type WRITE and READ*, satisfying the specifications above, are given in our system. Built on these operations the SCAN and LABEL procedures are defined. The LABEL is just the WRITE operation with no changes whatsoever. The SCAN is given as follows. The SCAN protocol is using the procedure MAX(<_{n}; I) which choses the <_{n}-maximal index among the indices in the nonempty set I ⊂ [1..N].

FUNCTION SCAN

1. FOR i := 1 TO N DO (m_{i}, <_{i}) := READ∗;

2. I := [1..N];

3. FOR n := N DOWNTO 1 DO

(a) l := MAX(<_{n}; I); k[l] := n;

(b) messages[l] := m_{n}[l];

(c) I := I \ {l};

4. Define: i < j iff k[i] < k[j];

5. RETURN (messages; <).

So the SCAN activates N times the READ* procedure, one after the other, and collects the values returned in variables m_{i}, and <_{i}. Then it calculates the N-tuple messages and the order < on the indexes to be returned. This calculation is done backwards (this idea is from the Dolev and Shavit’s paper). The procedure MAX(<_{n}; I) choses the <_{n}-maximal index among the indexes in the nonempty set I ⊂ [1..N]. Then this maximal index is thrown away from I, and the process is repeated. The order < on the index set is defined in such a way that the first index chosen is the < rightmost, and the last index is the leftmost.

We have to show that the Dolev-Shavit Timestamp specification given above in Section 9.1 holds for our protocol. The functions Ω_{l}(S), for a SCAN event S, are defined in the following way. For any 1 ≤ l ≤ N there is some n such that k[l] = n (k is k(S)). (This n is the place where l was choosen by MAX.) Let R^{∗} be the n-th READ* in S. Then set Ω_{l}(S) to be Ω_{l}^{∗}(R^{∗}).

The main point in the specification is the [global coherence]. So assume that L = Ω_{i}(S) and M = Ω_{j}(S) and i < (S)j. We have to prove that L ⇒ M. Since i < (S)j, k[i] < k[j] in S. Let R_{i} and R_{j} be, respectively, the k[i]-th and k[j]-th READ* events in S. So R_{i}<_{H}R_{j}. Now L = Ω_{i}^{∗}(R_{i})<_{H}end(R_{i}) by 1(a) of Section 9.3, and hence L<_{H}R_{j}. Also, if we denote by I_{j} the value of variable I at the (begining of the) k[j]-th execution of the FOR loop of line 3 in S, then i ∈ I_{j} (since at a later stage, in the execution of the FOR n := N DOWNTO 1 loop, i is in I). Hence i < (R_{j})j. Since M = Ω_{j}^{∗}(R_{j}), L ⇒ M now follows 3 of Section 9.3.

10 Conclusion

A theory of interprocess communication should be able to classify protocols according to structural properties. We ae still away from this aim, but some possible directions emerge. Let us take the question of implementing atomic multi-writer registers with single writer atomic registers (which is the main subject of this paper) and see how the different answers may be classified. Some of these answers are: Bloom [1987], Peterson and Burns [1987] which was corrected by Schaffer [1988], Li and Vitanyi [1987] and Abraham [.]. One dividing line is this: Do the reader processes also write? Other possible criteria is to look at the number of access to registers per protocol execution, the width of the registers, etc. Our investigation reported here has identified another dividing line explained in the following.

By definition, atomicity of a register R in a system execution H means that there is some augment of H in which the register is serial. Now the question is this: Does the linear order of Writer in the augment depends on all of H or only on the Writer’s events?

In the first type of registers, there may be two system executions, H_{1} and H_{2} of H, with the same restriction to the Writer process, but with augments that order the Writer in different linear orders. The protocols of Bloom [1987] and of Abraham [.] are of this type.

In the second type (which may be called “Writer’s definable augment” registers) the Reader process does not have any effect on the augment ordering of Writer. The unbounded timestamp READ/WRITE protocol is of this type, since the ordering depends only on the timestamps of the WRITE events and the Readers have no impact on this. Our bounded READ/WRITE protocol is also of this type—the augment only depends on the Writer process. I could not decide on the type of the other protocols.

Comparing the two types of protocols, it is not surprising that the second type requires heavier registers, but we have no proof for a lower bound which justifies this difference. Indeed, we do not know of any significant impossibility result in this area. For example, are the two data messages neccessary for an economical protocol in which Writers do not read messages and Readers do not write?

Another open question concerns the implementation of timestamps. Our implementation requires the order of N^{2} read events to execute a single SCAN; is there a way to implement timestamps with less reads?

References

U. Abraham . On Interprocess Communication and the Atomic Register Problem

U.Abraham and S.Ben-David and M. Magidor 1990 On Global-Time and Inter-process Communication. Semantics for Con-

currency, Proceedings of the International BCS-FACS Workshop, pp. 311 - 323.

B. Bloom 1987 constructing two-writer atomic registers. 6th ACM Symp. on Princi-

ples of Distributed Computing, pp. 249 - 259.

D. Dolev and N. Shavit 1989 Bounded Concurrent Time-Stamp systems Are Constructible ACM

A. Israeli and M. Li 1987 Bounded Time Stamps Proc. 28th annual IEEE Sym. on Foundation

of Computer Science, pp. 371-382.

A. Israeli and M. Li 1988 Bounded time-stamps. To be published.

L.Lamport 1986 On Interprocess Communication, Part I: Basic formalism, Part II:

Algorithms. Distributed Computing, Vol. 1, pp. 77 - 101.

M. Li and P.M.B. Vitanyi 1987 A very simple construction for atomic multiwriter register. Manuscript

from Harvard university.

M. Li, J. Tromp and P.M.B. Vitanyi 1989 How to Share Concurrent Wait-Free Variables. CWI publication

G.L Peterson and J.E. Burns 1987 Concurrent reading while writing II : the multiwriter case. FOCS-87.

V. Pratt 1986 Modeling Concurrency with Partial Orders. International J. of Parallel

Programming, Vol.15, pp. 33 - 71.

R. Schaffer 1988 On the correctness of atomic multi-writer registers MIT/LCS/TM-364.

P.M.B. Vitanyi and B. Awerbuch 1986 Atomic shared register access by asynchronous hardware. Proc. 27th

IEEE Symp. on Foundation of Computer Science, pp. 233 - 243. (Errata, FOCS-87).