Converting Lamport's regular register to atomic register
atomic registersBoolean registersconcurrent reading and writingnonatomic operationsregular registers
The problem dealt with in the paper is that of constructing atomic multi- valued n-reader 1-writer registers from atomic Boolean n-reader 1-writer registers. A register is an abstraction of an asynchronous interface communication with senders (writers) and receivers (readers) and the state of the communication medium represented by the value of the register. Asynchronous communication implies that some operations may overlap. In the 1-writer case there cannot be overlapping of writers but a read may overlap a write. Now it is easy to implement in hardware Boolean 1-writer 1-reader registers which are safe (i.e., such that a read that does not overlap a write returns the most recently written value, but if it overlaps a write it may return any value from the domain of the register). One usually wants to construct a regular multi-valued register (i.e., a safe register in which a read that overlaps a write obtains either the old or the new value). The present paper takes the lead from a construction by Lamport which gives regular multi-valued registers from regular Boolean ones but it does not imply atomicity even though the Boolean registers are atomic (where atomic means that reads and writes behave as if they occur in some total order, such that a read obtains the value of the most recent ``essentially complete write and of two successive reads the first cannot obtain a newer value than the second). The main result of the paper is a construction which improves Lamport's one to insure atomicity.
- One-write algorithms for multivalued regular and atomic registers
- Almost optimal single reader, single writer atomic register
- Constructing two-writer atomic registers
- scientific article; zbMATH DE number 4096767 (Why is no real title available?)
- Bounds on the Costs of Multivalued Register Implementations
- The elusive atomic register
- Introduction à l'algorithmique des objets partagés
- Constructing 1-writer multireader multivalued atomic variables from regular variables
- Parallel Processing and Applied Mathematics
- Algorithms – ESA 2004
- Wait-free computing
- On implementing SWMR registers from SWSR registers in systems with Byzantine failures
- On interprocess communication and the implementation of multi-writer atomic registers
- History-independent concurrent objects
- A very simple construction of 1-writer multireader multivalued atomic variable
- Concurrent reading while writing revisited
This page was built for publication: Converting Lamport's regular register to atomic register
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1114404)
