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

Lefteris M. Kirousis, Andreas G. Veneris

Research output: Contribution to journalArticlepeer-review


Let X1,..., Xc be variables shared by a number of processors P1,..., Pq that 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 processors allowed to read and write each variable. For the proof, the atomicity problem is reduced to the problem of consecutive 1s in matrices. The reduction entails showing a combinatorial result that might be interesting on its own.

Original languageEnglish (US)
Pages (from-to)155-170
Number of pages16
JournalActa Informatica
Issue number2
StatePublished - Feb 1995

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Computer Networks and Communications


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