  Commutativity of data structure methods is of ongoing interest, with roots in
the database community. In recent years commutativity has been shown to be a
key ingredient to enabling multicore concurrency in contexts such as
parallelizing compilers, transactional memory, speculative execution and, more
broadly, software scalability. Despite this interest, it remains an open
question as to how a data structure's commutativity specification can be
verified automatically from its implementation.
  In this paper, we describe techniques to automatically prove the correctness
of method commutativity conditions from data structure implementations. We
introduce a new kind of abstraction that characterizes the ways in which the
effects of two methods differ depending on the order in which the methods are
applied, and abstracts away effects of methods that would be the same
regardless of the order. We then describe a novel algorithm that reduces the
problem to reachability, so that off-the-shelf program analysis tools can
perform the reasoning necessary for proving commutativity. Finally, we describe
a proof-of-concept implementation and experimental results, showing that our
tool can verify commutativity of data structures such as a memory cell,
counter, two-place Set, array-based stack, queue, and a rudimentary hash table.
We conclude with a discussion of what makes a data structure's commutativity
provable with today's tools and what needs to be done to prove more in the
future.
