Shared register

A SWSR atomic (linearizable) register can be implemented in an asynchronous message-passing system, even if processes may crash. There is no time limit for processes to deliver messages to receivers or to execute local instructions. In other words, processes can not distinguish between processes which respond slowly or simply crash.

Implementation of Atomic SWSR Register in MP System

The implementation given by Attiya, Bar-Noy and Dolev[3] requires n>2f, where n is the total number of processes in the system and f is the maximum number of processes that can crash during execution. The algorithm is as follows:

WRITE(v)
  t++
  send (v,t) to all processes
  wait until getting (n-f) acknowledgements

READ()
  send read request to all processes
  wait until getting (n-f) responses of them
  choose v with the biggest t

The linearization order of operations is: linearize writes in the order as they occur and insert the read after the write whose value it returns. We can check that the implementation is linearizable. We can check property 2 especially when op1 is write and op2 is read, and 'read is immediately after write. We can show by contradiction. Assume the read does not see the write, and then according to the implementation, we must have two disjoint sets of size (n-f) among the n processes. So 2*(n-f)≤ n leading to n≤2f, which contradicts the fact that n>2f. So the read must read at least one value written by that write.

A SWMR register can be written by only one process but can be read by multiple processes.

Implementation of SWMR register using SWSR registers

Readers Writers	${\displaystyle R_{1}}$	${\displaystyle R_{2}}$	⋯	${\displaystyle R_{1}}$
${\displaystyle R_{1}}$	A[1,1]	A[1,2]	⋯	A[1,n]
${\displaystyle R_{2}}$	A[2,1]	A[2,2]	⋯	A[2,n]
⋮	⋯	⋯	⋯	⋯
${\displaystyle R_{n}}$	A[n,1]	A[n,2]	⋯	A[n,n]
w	A[n+1,1]	A[n+1,2]	⋯	A[n+1,n]

Let n be the number of processes which can read the SWMR register. Let R_i, 0<i≤n, refer to the readers of the SWMR register. Let w be the single writer of the SWMR. The figure on the right shows a construction of a SWMR register using an array of n(n+1) SWSR registers. We denote the array by A. Each SWSR register A[i,j] is writable by R_i when 0<i≤n and is writable by w when i=n+1. Each SWSR register A[i,j] is readable by R_j. The implementations of read and write are shown below.

for j = i..n 
    t++
    write (v,t) in A[n+1,j]
end for

for k = 1..(n+1)
    (V[k],T[k]) <- read A[k,i]
end for
take k such that for all l, T[k] >= T[l]
r <- V[k]
t <- T[k]
for j=1..n
    write (r,t) in A[i,j]
end for
return r

The t-value of an operation is the value of t it writes and the operations are linearized by t-values. If write and read have the same t-value, order write before read. If several reads have the same t-values, order them by the start time.

We can use the a SW Snapshot object of size n to construct a MWMR register.

((v1,t1), …, (vn,tn)) <- V.SCAN()
let t = max(t1,…,tn)+1
V.UPDATE(i,(v,t))

V.SCAN
return value with largest timestamp, in the result of the scan

The linearization order is as follows. Order write operations by t-values. If several writes have the same t-value, order the operation with small process ID in front. Insert reads right after write whose value they return, breaking ties by process ID and if still tied, break tie by start time.