## Time-adaptive Algorithms for Synchronization

*Rajeev Alur, Hagit Attiya, and
Gadi Taubenfeld*
We consider concurrent systems in which there is an unknown
upper bound on memory access time.
Such a model is inherently different from asynchronous model where
no such bound exists, and also from timing-based models where such a
bound exists and is known a priori.
The appeal of our model lies in the fact that while it abstracts from
implementation details, it is a better approximation of real
concurrent systems compared to the asynchronous model.
Furthermore, it is stronger than the asynchronous model enabling us to
design algorithms for problems that are unsolvable in the asynchronous
model.

Two basic synchronization problems, consensus and mutual exclusion,
are investigated in a shared memory environment that supports atomic
registers.
We show that $\Theta(\Delta\frac{\log \Delta}{\log\log \Delta})$
is an upper and lower bound on the time complexity of any consensus
algorithm, where $\Delta$ is the (unknown) upper bound on memory
access time.
For the mutual exclusion problem, we design an efficient
algorithm that takes advantage of the fact that some upper bound on
memory access time exists.
The solutions for both problems are even more efficient in the absence
of contention, in which case their time complexity is a constant.

A preliminary version appeared in Proceedings of the 25th ACM
Symposium on Theory of Computing (STOC 1994), pp. 800-809.
To appear in *SIAM Journal of Computing.*