Technical Report CS0806

Authors: R. Alur, H. Attiya, G. Taubenfeld
PDFNot Available

We consider concurrent systems in which there is an unknown upper bound on memory access time. Such a model is inherently different from asynchronous models 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.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1994
To the main CS technical reports page

Computer science department, Technion