Please enable JavaScript.
Coggle requires JavaScript to display documents.
4.Foundations of shared memory - Coggle Diagram
4.Foundations of shared memory
Сhicken and intuition
Turing machine
4.1 The space of registers
Two key properties of their design: safety, defined by consistency conditions, and liveness, defined by progress conditions.
A read–write register (or just a register) is an object that encapsulates a value that can be observed by a read() method and modified by a write() method (these methods are often called load and store).
An atomic register is a linearizable implementation of the sequential register class
Register differ
Range value
Number of readers/writers
Degree of consistency
An SRSW or MRSW register implementation is safe if:
A read() call that does not overlap a write() call returns the value written by the most recent write() call. (The “most recent write() call” is well defined because there is a single writer.)
A read() call that overlaps a write() call may return any value within the register’s allowed range of values (e.g., 0 to M − 1 for an M -valued register).
Kind of register
Safe
Regular - quiescently consistent
Atomic - linearizible
4.2 Register constructions
Lemma 4.2.6. The construction in Fig. 4.12 is an atomic MRSW register.
4.3 Atomic snapshots
4.3.1 An obstruction-free snapshot