Shared register

{{Short description|Type of shared data structure}} In distributed computing, shared-memory systems and message-passing systems are two widely studied methods of interprocess communication. In shared-memory systems, processes communicate by accessing shared data structures. A '''shared''' (read/write) '''register''', sometimes just called a register, is a fundamental type of shared data structure which stores a value and has two operations: ''read'', which returns the value stored in the register, and ''write'', which updates the value stored. Other types of shared data structures include read–modify–write, test-and-set, compare-and-swap etc. The memory location which is concurrently accessed is sometimes called a register.

== Classification == Registers can be classified according to the consistency condition they satisfy when accessed concurrently, the domain of possible values that can be stored, and how many processes can access with the ''read'' or ''write'' operation, which leads to in total 24 register types.<ref name=DCFSA>{{cite book|last1=Kshemkalyani|first1=Ajay D.|last2=Singhal|first2=Mukesh|title=Distributed computing : principles, algorithms, and systems|url=https://archive.org/details/distributedsyste00ajay_336|url-access=limited|date=2008|publisher=Cambridge University Press|location=Cambridge|isbn=9780521876346|pages=[https://archive.org/details/distributedsyste00ajay_336/page/n452 435]–437}}</ref> {| class="wikitable" style="text-align:center;margin: 1em auto 1em auto;" |+ Shared Register Classification |- ! Consistency condition !! Domain !! ''Write'' !! ''Read'' |- | style="width: 100px;"|safe regular atomic|| style="width: 100px;"|binary integer|| style="width: 100px;"|single-writer multi-writer|| style="width: 100px;"|single-reader multi-reader |}

When ''read'' and ''write'' happen concurrently, the value returned by ''read'' may not be uniquely determined. Lamport defined three types of registers: safe registers, regular registers and atomic registers.<ref name=DCFSA /> A ''read'' operation of a safe register can return any value if it is concurrent with a Write operation, and returns the value written by the most recent ''write'' operation if the ''read'' operation does not overlap with any ''write''. A regular register differs from a safe register in that the read operation can return the value written by either the most recent completed Write operation or a Write operation it overlaps with. An atomic register satisfies the stronger condition of being linearizable.

Registers can be characterized by how many processes can access with a ''read'' or ''write'' operation. A single-writer (SW) register can only be written by one process and a multiple-writer (MW) register can be written by multiple processes. Similarly single-reader (SR) register can only be read by one process and multiple-reader (MR) register can be read by multiple processes. For a SWSR register, it is not necessary that the writer process and the reader process are the same.

== Constructions == The figure below illustrates the constructions stage by stage from the implementation of SWSR register in an asynchronous message-passing system to the implementation of MWMR register using a SW Snapshot object. This kind of construction is sometimes called simulation or emulation.<ref>{{cite book|last1=Attiya|first1=Hagit|author1-link=Hagit Attiya|last2=Welch|first2=Jennifer|author2-link=Jennifer L. Welch|title=Distributed computing: fundamentals, simulations, and advanced topics|date=Mar 25, 2004|publisher=John Wiley & Sons, Inc.|isbn=978-0-471-45324-6|url=http://ca.wiley.com/WileyCDA/WileyTitle/productCd-0471453242.html}}</ref> In each stage (except Stage 3), the object type on the right can be implemented by the simpler object type on the left. The constructions of each stage (except Stage 3) are briefly presented below. There is an article which discusses the details of constructing snapshot objects. {{image frame|align=center|caption=Shared Register Stages of Constructions|width=700 |content= <chem>{\operatorname{Message-passing} \atop (MP)\ System} ->[][\text{Stage 1}] SWSR\ atomic ->[][\text{Stage 2}] SWMR ->[][\text{Stage 3}] SW\ snapshot ->[][\text{Stage 4}] MWMR</chem>  }} An implementation is linearizable if, for every execution there is a linearization ordering that satisfies the following two properties: # if operations were done sequentially in order of their linearization, they would return the same result as in the concurrent execution. # If operation op1 ends before operation op2 begins, then op1 comes before op2 in linearization.

=== Implementing an atomic SWSR register in a message passing system === 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.

frame|center|Implementation of Atomic SWSR Register in MP System

The implementation given by Attiya, Bar-Noy and Dolev<ref>{{cite book|last1=Attiya|first1=Hagit|last2=Bar-Noy|first2=Amotz|last3=Dolev|first3=Danny|title=Proceedings of the ninth annual ACM symposium on Principles of distributed computing |chapter=Sharing memory robustly in message-passing systems |date=1990|volume=PODC '90|pages=363–375|doi=10.1145/93385.93441|isbn=089791404X|s2cid=1233774 }}</ref> requires {{math|''n'' > 2''f''}}, where {{mvar|n}} is the total number of processes in the system, and {{mvar|f}} is the maximum number of processes that can crash during execution. The algorithm is as follows: {| class="wikitable" width="100%" |- ! Writer ! Reader |- | <syntaxhighlight lang="text"> WRITE(v) t++ send (v,t) to all processes wait until getting (n-f) acknowledgements </syntaxhighlight> | <syntaxhighlight lang="text"> READ() send read request to all processes wait until getting (n-f) responses of them choose v with the biggest t </syntaxhighlight> |}

The linearization order of operations is: linearize ''write''s 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 {{math|(''n'' - ''f'')}} among the n processes. So {{math|2 * (''n'' - ''f'') ≤ ''n''}} leading to {{math|''n''≤ 2''f''}}, which contradicts the fact that {{math|''n'' > 2''f''}}. So the ''read'' must read at least one value written by that ''write''.

=== Implementing a SWMR register from SWSR registers === A SWMR register can be written by only one process but can be read by multiple processes. {| class="wikitable floatright" |+ Implementation of SWMR register using SWSR registers ! {{Diagonal split header|Writers|Readers}} !! {{tmath|R_1}} !! {{tmath|R_2}} !! ⋯ !! {{tmath|R_n}} |- style="font-family:monospace" ! {{tmath|R_1}} | A[1,1] || A[1,2] || style="text-align:center" | ... || A[1,n] |- style="font-family:monospace" ! {{tmath|R_2}} | A[2,1] || A[2,2] || style="text-align:center" | ... || A[2,n] |- style="font-family:monospace;text-align:center" ! ⋮ | ... || ... || ... || ... |- style="font-family:monospace" ! {{tmath|R_n}} | A[n,1] || A[n,2] || style="text-align:center" | ... || A[n,n] |- style="font-family:monospace" ! {{mvar|w}} | A[n+1,1] || A[n+1,2] || style="text-align:center" | ... || A[n+1,n] |} Let n be the number of processes which can read the SWMR register. Let {{mvar|Ri}}, {{math|0 < ''i'' ≤ ''n''}}, refer to the readers of the SWMR register. Let {{mvar|w}} be the single writer of the SWMR. The figure on the right shows a construction of a SWMR register using an array of {{math|''n''(''n'' + 1)}} SWSR registers. We denote the array by {{math|A}}. Each SWSR register {{math|A[''i'',''j'']}} is writable by {{mvar|Ri}} when {{math|0 < ''i''≤ ''n''}} and is writable by {{mvar|w}} when {{math|1=''i'' = ''n'' + 1}}. Each SWSR register {{math|A[''i'',''j'']}} is readable by {{mvar|Rj}}. The implementations of ''read'' and ''write'' are shown below. {| class="wikitable" |- ! Writer | w: WRITE(v) |<syntaxhighlight lang="text"> for j = i..n t++ write (v,t) in A[n+1,j] end for </syntaxhighlight> |- ! Readers | {{mvar|Ri}}: READ() |<syntaxhighlight lang="text"> 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 </syntaxhighlight> |}

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 ''read''s have the same t-values, order them by the start time.

=== Implementing a MWMR register from a SW Snapshot object === We can use the a SW Snapshot object of size n to construct a MWMR register. {| class="wikitable" |- ! Writer ! Readers |- valign="top" |Pi: WRITE(v) | Pi: READ() |- | <syntaxhighlight lang="text"> ((v1, t1), ..., (vn, tn)) <- V.SCAN() let t = max(t1, ..., tn) + 1 V.UPDATE(i, (v, t))</syntaxhighlight> | <syntaxhighlight lang="text"> V.SCAN return value with largest timestamp, in the result of the scan </syntaxhighlight> (break ties by using rightmost pair of largest timestamp) |} The linearization order is as follows. Order ''write'' operations by t-values. If several ''write''s have the same t-value, order the operation with small process ID in front. Insert ''read''s right after ''write'' whose value they return, breaking ties by process ID and if still tied, break tie by start time.

== References == {{reflist}}

Category:Distributed computing problems