Converting Lamport's regular register to atomic register
type: Item
instance of: scholarly article
title: Converting Lamport's regular register to atomic register
zbMATH Open document ID: 0662.68049
DOI: 10.1016/0020-0190(88)90175-5
author: K. Vidyasankar
published in: Information Processing Letters
publication date: 1988-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q05
zbMATH DE Number: 4082980
zbMATH Keywords: concurrent reading and writing
zbMATH Keywords: nonatomic operations
zbMATH Keywords: regular registers
zbMATH Keywords: atomic registers
zbMATH Keywords: Boolean registers
reviewed by: Andrea Maggiolo-Schettini
MaRDI profile type: Publication
full work available at URL: 0020-0190(88)90175-5
OpenAlex ID: W2049936847
cites work: On interprocess communication. II: Algorithms
description: scientific article; zbMATH DE number 4082980