  We present a randomized approach for wait-free locks with strong bounds on
time and fairness in a context in which any process can be arbitrarily delayed.
Our approach supports a tryLock operation that is given a set of locks, and
code to run when all the locks are acquired. A tryLock operation, or attempt,
may fail if there is contention on the locks, in which case the code is not
run. Given an upper bound $\kappa$ known to the algorithm on the point
contention of any lock, and an upper bound $L$ on the number of locks in a
tryLock's set, a tryLock will succeed in acquiring its locks and running the
code with probability at least $1/(\kappa L)$. It is thus fair. Furthermore, if
the maximum step complexity for the code in any lock is $T$, the attempt will
take $O(\kappa^2 L^2 T)$ steps, regardless of whether it succeeds or fails. The
attempts are independent, thus if the tryLock is repeatedly retried on failure,
it will succeed in $O(\kappa^3 L^3 T)$ expected steps, and with high
probability in not much more.
