##
Adaptive and Efficient Mutual Exclusion

###
Hagit Attiya and Vita Bortnikov

**To appear at Nineteenth Annual
ACM SIGACT-SIGOPS Symposium on PRINCIPLES OF DISTRIBUTED COMPUTING (PODC
2000), Portland, Oregon, 16-19 July 2000**

##
Abstract

A distributed algorithm is *adaptive* if its performance depends on
*k*, the number of processes that are concurrently active during the
algorithm execution (rather than a function of n, the total number of processes).
This paper presents adaptive algorithm for mutual exclusion using only
read and write operations. The worst case *step complexity* cannot
be a measure for the performance of mutual exclusion algorithms, because
it is always unbounded in the presence of contention. Therefore, a number
of different parameters such as *remote step complexity* and *time
complexity* are used to measure the algorithm's performance. The *remote
step complexity* is the maximal number of steps performed by a process
where a *wait* is counted as one step. The *time complexity*
is the time interval between subsequent entries to the critical section,
where one time unit is the minimal interval in which every active process
performs at least one step. The algorithm presented here has O(log *k*)
time complexity and O(*k*) remote step complexity, where *k*
is the point contention. The space complexity of this algorithm is O(*nN*),
where *N* is the range of processes' names. The space complexity of
all the previously known adaptive algorithms for various long-lived problems
depends on *N*. We present a technique that reduces the space complexity
of our algorithm to be a function of *n*, while preserving the other
performance measures of the algorithm.