## Contention-Free Complexity of Shared Memory Algorithms

*Rajeev Alur and
Gadi Taubenfeld*
While the worst-case time complexity measures the maximum time needed to
solve a problem over all runs, the contention-free time complexity
indicates the maximum time needed when a process executes by itself without
competition from other processes.
Since contention should be rare in well-designed systems,
it is important to design algorithms which
perform well also in the absence of contention.
We study the contention-free time complexity of shared memory algorithms using
two measures: step complexity that counts the
number of accesses to shared registers, and register complexity that measures
the number of different registers accessed.
Depending on the architecture, one of the two measures more accurately
reflects the time taken.

We provide lower and upper bounds for the contention-free step and register
complexity of solving the mutual exclusion problem as a function of
the number of processes and the size of the biggest register that
can be accessed in one atomic step.
We also present bounds on the worst-case and contention-free step
and register complexities of solving the naming problem. These bounds illustrate
how the proposed definitions are useful in differentiating among the computational
powers of different primitives.

* Information and Computation* ** 126(1)**: 62--73, 1996.
A preliminary version appears in
Proceedings of the 13th ACM Symposium on Principles of Distributed Computing (PODC 1994), pp. 61-70.