Reading many variables in one atomic operation solutions with linear or sublinear complexity

Lefteris M. Kirousis, Paul Spirakis, Philippas Tsigas

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We address the problem of reading more than one variables (components) X1,…, Xc, all in one atomic operation, by a process called the reader, while each of these variables are being written by a set of writers. All operations (i.e. both reads and writes) are assumed to be totally asynchronous and wait-free. The previous algorithms for this problem require at best quadratic time and space complexity (the time complexity of a construction is the number of sub-operations of a high-level operation and its space complexity is the number of atomic shared variables it needs). We provide a (deterministic) solution which has linear (in the number of processes) space complexity, linear time complexity for a read operation and constant time complexity for a write. Our solution does not make use of time-stamps. Rather, it is the memory location where a write writes that differentiates it from the other writes. Now, introducing randomness in the location where a reader gets the value it returns, we get a conceptually very simple probabilistic algorithm. This is the first probabilistic algorithm for the problem. Its space complexity as well as the time complexity of a read operation are both sublinear. The time complexity of a write is still constant. On the other hand, under the Archimedean assumption, we get a protocol whose both time and space complexity do not depend on the number of writers but are linear in the number of components only (the time complexity of a write operation is still constant).

Original languageEnglish (US)
Title of host publicationDistributed Algorithms - 5th International Workshop, WDAG 1991, Proceedings
EditorsPaul G. Spirakis, Lefteris Kirousis, Sam Toueg
PublisherSpringer Verlag
Number of pages13
ISBN (Print)9783540552369
StatePublished - 1992
Event5th International Workshop on Distributed Algorithms, WDAG 1991 - Delphi, Greece
Duration: Oct 7 1991Oct 9 1991

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume579 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference5th International Workshop on Distributed Algorithms, WDAG 1991

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Reading many variables in one atomic operation solutions with linear or sublinear complexity'. Together they form a unique fingerprint.

Cite this