Coarser Equivalences for Concurrent Program Runs

Trace theory is a framework for designing equivalence relations for concurrent program runs based on a commutativity relation over the set of atomic steps taken by individual program threads. It is simple and elegant, and it yields efficient algorithms that are broadly useful in many different contexts. In this paper, we study relaxations of trace equivalence with the goal of maintaining its algorithmic advantages. We first prove that the largest appropriate relaxation of trace equivalence, an equivalence relation that preserves the order of steps taken by each thread and what write operation each read operation observes, does not yield efficient algorithms. Specifically, we prove a linear space lower bound for the problem of checking if two arbitrary steps of a concurrent program run are causally concurrent (i.e. they can be reordered in an equivalent run) or causally ordered. The same problem can be decided in constant space for trace equivalence. Second, we propose a new commutativity-based notion of equivalence that is strictly more relaxed than trace equivalence, and yet yields a constant space algorithm for the same problem. This notion of equivalence uses commutativity of certain blocks of atomic steps in addition to the standard commutativity from trace theory. We define a new partial order and prove that it faithfully represents the new equivalence classes. The definition of the partial order relies on a novel technical contribution: a new notion of atomicity, called liberal atomicity that is more relaxed than the well-known conflict-serializability. We demonstrate that liberal atomicity can be checked as efficiently as conflict-serializability, i.e. in constant space, and use this efficient monitor as part of our constant-space algorithm for deciding the status of causal concurrency of two steps in a concurrent program run.