Simple Atomic Snapshots: A Linear Complexity Solution with Unbounded Time-Stamps
Lists
Only you see this
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: 1.(i) Both the protocol and its formal correctness proof are easy to understand.2.(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.
BibTeX
@article{kirousis1996simple,
author = {Lefteris M. Kirousis and Paul G. Spirakis and Philippas Tsigas},
title = {{Simple Atomic Snapshots: A Linear Complexity Solution with Unbounded Time-Stamps}},
journal = {Inf. Process. Lett.},
year = {1996},
doi = {10.1016/0020-0190(95)00198-0},
}Loading related content...