Simple atomic snapshots: A linear complexity solution with unbounded time-stamps

Lefteris M. Kirousis, Paul Spirakis, Philippas Tsigas

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)47-53
Number of pages7
JournalInformation Processing Letters
Volume58
Issue number1
DOIs
StatePublished - 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

Fingerprint

Dive into the research topics of 'Simple atomic snapshots: A linear complexity solution with unbounded time-stamps'. Together they form a unique fingerprint.

Cite this