The transactional approach to contention management guarantees
atomicity by making sure that whenever two transactions have a
conflict on a resource, only one of them proceeds. A major
challenge in implementing this approach lies in guaranteeing
progress, since transactions are often restarted.
Inspired by the paradigm of \emph{non-clairvoyant} job scheduling,
we analyze the performance of a contention manager by comparison
with an \emph{optimal}, clairvoyant contention manager that knows
the list of resource accesses that will be performed by each
transaction, as well as its release time and duration. The
realistic, non-clairvoyant contention manager is evaluated by the
\emph{competitive ratio} between the last completion time
(makespan) it provides and the makespan provided by an optimal
contention manager.
Assuming that the amount of exclusive accesses to the resources is
non-negligible, we present a simple proof that every work
conserving contention manager guaranteeing the pending commit
property achieves an $O(s)$ competitive ratio, where $s$ is the
number of resources. This bound holds for the \ag{} contention
manager studied by Guerraoui et al.~\cite{GuerraouiHP05} and is a
significant improvement over the $O(s^2)$ bound they prove for the
competitive ratio of \ag{}. We show that this bound is tight for
any deterministic contention manager, and under certain
assumptions about the transactions, also for randomized contention
managers.
When transactions may fail, we show that a simple adaptation of
\ag{} has a competitive ratio of at most $O(ks)$, assuming that a
transaction may fail at most $k$ times. If a transaction can
modify its resource requirements when re-invoked, then any
deterministic algorithm has a competitive ratio $\Omega(ks)$. For
the case of unit length jobs, we give (almost) matching lower and
upper bounds.