Efficient algorithms for checking the atomicity of a run of read and write operations

Lefteris M. Kirousis, Andreas G. Veneris

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


Let X1,…, Xc be variables shared by a number of processors p1,…, Pq which operate in a totally asynchronous and wait-free manner. An operation by a processor is either a write to one of the variables or a read of the values of all variables. Operations are not assumed to be instantaneous and may arbitrarily overlap in time. A succession of possibly overlapping operations a1,…, an (i.e., a run) is said to be atomic, if these operations can be serialized in a way compatible with any existing precedences among them and so that any read operation returns for each variable the value of the most recent —with respect to the serialization— write operation on this variable. This paper examines the complexity of the combinatorial problem of testing a run for atomicity. First it is pointed out that when there is only one shared variable or when only one processor is allowed to write to each variable, known theorems lead to polynomial-time algorithms for checking the atomicity of a run (the variable of the time-complexity function is the number of operations in the run). It is then proved that checking atomicity has polynomial-time complexity in the general case of more than one variables and with all procesors allowed to read and write. For the proof, the atomicity problem is reduced to the problem of consecutive 1s in matrices. The reduction entails showing a combinatorial result which might be interesting on its own.

Original languageEnglish (US)
Title of host publicationDistributed Algorithms - 7th International Workshop, WDAG 1993, Proceedings
EditorsAndre Schipe
PublisherSpringer Verlag
Number of pages15
ISBN (Print)9783540572718
StatePublished - 1993
Event7th International Workshop on Distributed Algorithms, WDAG 1993 - Lausanne, Switzerland
Duration: Sep 27 1993Sep 29 1993

Publication series

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


Conference7th International Workshop on Distributed Algorithms, WDAG 1993

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Efficient algorithms for checking the atomicity of a run of read and write operations'. Together they form a unique fingerprint.

Cite this