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

摘要

Let X_1,..., X_c be variables shared by a number of processors P_1,..., P_q 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 a_1,..., a_n (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.