×

Converting Lamport’s regular register to atomic register. (English) Zbl 0662.68049

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.

MSC:

68Q05 Models of computation (Turing machines, etc.) (MSC2010)
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Awerbuch, B.; Kirousis, L.M.; Kranakis, E.; Vitanyi, P.M.B., On proving register atomicity, ()
[2] Lamport, L.; Lamport, L., On interprocess communication, part II: algorithms, Distributed comput., Distributed comput., 1, 77-101, (1986) · Zbl 0598.68023
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.