TIME-ADAPTIVE ALGORITHMS FOR SYNCHRONIZATION

We consider concurrent systems in which there is an unknown upper boun d on memory access time. Such a model is inherently different from the asynchronous model, where no such bound exists, and also from timing- based models, where such a bound exists and is known a priori. The app eal of our model lies in the fact that while it abstracts from impleme ntation details, it is a better approximation of real concurrent syste ms than the asynchronous model. Furthermore, it is stronger than the a synchronous model, enabling us to design algorithms for problems that are unsolvable in the asynchronous model. Two basic synchronization pr oblems, consensus and mutual exclusion, are investigated in a shared-m emory environment that supports atomic read/write registers. We show t hat Theta(Delta log Delta/log log Delta) is an upper and lower bound o n the time complexity of consensus, where Delta is the (unknown) upper bound on memory access time. For the mutual exclusion problem, we des ign an efficient algorithm that takes advantage of the fact that some upper bound on memory access time exists. The solutions for both probl ems are even more efficient in the absence of contention, in which cas e their time complexity is a constant.