On the Complexity of Commutativity Analysis

Two operations commute if they generate the same result regardless of the orderin which they execute. Commutativity is an important property --- commutingoperations enable significant optimizations in the fields of parallelcomputing, optimizing compilers, parallelizing compilers and databaseconcurrency control. Algorithms that statically decide if operations commutecan be an important component of systems in these fields because they enablethe automatic application of these optimizations. In this paper we define thecommutativity decision problem and establish its complexity for a variety ofbasic instructions and control constructs. Although deciding commutativity is,in general, undecidable or computationally intractable, we believe thatefficient algorithms exist that can solve many of the cases that arise inpractice.