Simple Atomic Snapshots: A Linear Complexity Solution with Unbounded Time-Stamps

Lefteris M. Kirousis, Paul G. Spirakis, Philippas TsigasInf. Process. Lett 1996 · DOI · OpenReview

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...

Figure