TY - GEN

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

AU - Kirousis, Lefteris M.

AU - Veneris, Andreas G.

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1993.

PY - 1993

Y1 - 1993

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

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

UR - http://www.scopus.com/inward/record.url?scp=5944258703&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=5944258703&partnerID=8YFLogxK

U2 - 10.1007/3-540-57271-6_27

DO - 10.1007/3-540-57271-6_27

M3 - Conference contribution

AN - SCOPUS:5944258703

SN - 9783540572718

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 54

EP - 68

BT - Distributed Algorithms - 7th International Workshop, WDAG 1993, Proceedings

A2 - Schipe, Andre

PB - Springer Verlag

T2 - 7th International Workshop on Distributed Algorithms, WDAG 1993

Y2 - 27 September 1993 through 29 September 1993

ER -