Connections between commutativity and concurrency are well known and well established in the computing literature. Often, commutativity is used to demonstrate the feasibility of executing instructions concurrently. Clements et al. introduce the idea of using commutativity as an interface design requirement to improve scalability. In their words, “whenever interface operations commute, they can be implemented in a way that scales.”

Concurrent operations commute if the aftermath is independent of their execution order. This means that it is not possible to tell a posteriori in which order they were executed. This is achieved by conflict-free implementation, the “holy grail” of scalability. This paper demonstrates that there are some opportunities out there for more scalable interfaces.

After presenting some definitions and proofs, the authors describe a tool for automatically developing test cases and testing if a particular implementation commutes. As an example, this tool is applied to a model of various POSIX file system and memory system calls to determine their commutativity. Those are compared and benchmarked against equivalent routines from an experimental operating system implemented according to the COMMUTE rules defined in the paper.

Though performance tradeoffs are only briefly discussed, these preliminary results look promising.