This paper presents adaptive algorithms for mutual exclusion using only read and write operations; the performance of the algorithms depends only on thepoint contention, i.e., the number of processes that are concurrently active during the algorithm execution (and not onn, the total number of processes). Our algorithm hasO(k) remote step complexity andO(logk) system response time, wherek is the point contention. Theremote step complexity is the maximal number of steps performed by a process where await is counted as one step. Thesystem response time 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 space complexity of this algorithm isO(N logn), whereN is the range of processes' names. We show how to make the space complexity of our algorithm depend solely onn, while preserving the other performance measures of the algorithm.

Authors and Affiliations

1. Department of Computer Science Technion, Haifa 32000, Israel (e-mail: hagit@cs.technion.ac.il, vita@versedge.com), , , , , , IL

   Hagit Attiya & Vita Bortnikov

Received: March 2001 / Accepted: November 2001

Reprints and permissions