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.