  Transactional memory (TM) is an inherently optimistic abstraction: it allows
concurrent processes to execute sequences of shared-data accesses
(transactions) speculatively, with an option of aborting them in the future.
Early TM designs avoided using locks and relied on non-blocking synchronization
to ensure obstruction-freedom: a transaction that encounters no step contention
is not allowed to abort. However, it was later observed that obstruction-free
TMs perform poorly and, as a result, state-of-the-art TM implementations are
nowadays blocking, allowing aborts because of data conflicts rather than step
contention.
  In this paper, we explain this shift in the TM practice theoretically, via
complexity bounds. We prove a few important lower bounds on obstruction-free
TMs. Then we present a lock-based TM implementation that beats all of these
lower bounds. In sum, our results exhibit a considerable complexity gap between
non-blocking and blocking TM implementations.
