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.