id: 01012889
dt: j
an: 01012889
au: Alur, Rajeev; Attiya, Hagit; Taubenfeld, Gadi
ti: Time-adaptive algorithms for synchronization.
so: SIAM J. Comput. 26, No.2, 539-556 (1997).
py: 1997
pu: Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA
la: EN
cc: 
ut: distributed computing; consensus; mutual exclusion; timing-based algorithms
ci: 
li: doi:10.1137/S0097539794265244
ab: Summary: We consider concurrent systems in which there is an unknown upper
    bound 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 appeal of our model lies in the fact that while it abstracts from
    implementation details, it is a better approximation of real concurrent
    systems than 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
    read/write registers. We show that $Θ(Δ\frac{\log Δ}{\log\log Δ})$
    is an upper and lower bound on the time complexity of consensus, where
    $Δ$ 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.
rv: