Sequential Specification of Transactional Memory Semantics
Michael Lee Scott · UR Research (University of Rochester) · 2006
Transactional memory (TM) provides a general-purpose mech-anism with which to construct concurrent objects. Transactional memory can also be thought of as a concurrent object, but its se-mantics are less clear than those of the objects typically constructed on top of it. In particular, commit operations in a transactional memory may fail when transactions conflict. Under what circum-stances, exactly, is such behavior permissible? We offer candidate sequential specifications to capture the se-mantics of transactional memory. In all cases, we require that reads return consistent values in any transaction that succeeds. Each spec-ification embodies a conflict function, which specifies when two transactions cannot both succeed. Optionally, a specification may also embody an arbitration function, which specifies which of two conflicting transactions must fail. In the terminology of the STM