Abstract
Let X1, . . ., Xc be variables which together constitute a composite register. These variables are shared by a number of processes which operate in a totally asynchronous and wait-free manner. An operation by a process on the composite register is either a write to one of the variables or a read of the values of all variables. All operations are required to be atomic, i.e. an execution of any number of them (including reads) must be linearizable, in a way consistent with the values returned by the reads. In a single reader composite register no two reads can concurrently access the composite register. We give a new protocol implementing a single reader composite register for the case when there is a single writer per variable. Our construction uses time-stamps that may take values as large as the number of operations performed. The advantages of our construction over previous (bounded time-stamps) solutions are: (i) Both the protocol and its formal correctness proof are easy to understand. (ii) The time complexity of an operation of our construction (i.e. the number of its sub-operations) and the number of the subregisters used in our construction are at most equal to the number of processes that can concurrently access the composite register.
Original language | English (US) |
---|---|
Pages (from-to) | 47-53 |
Number of pages | 7 |
Journal | Information Processing Letters |
Volume | 58 |
Issue number | 1 |
DOIs | |
State | Published - Apr 8 1996 |
Keywords
- Distributed computing
- Snapshot problem
- Wait-free registers
ASJC Scopus subject areas
- Theoretical Computer Science
- Signal Processing
- Information Systems
- Computer Science Applications