document: Adaptive and efficient mutual exclusion The paper presents adaptive algorithms for mutual exclusion using only read and write operations ; the performance of the algorithms depends only on the point contention , i.e. , the number of processes that are concurrently active during algorithm execution -LRB- and not on n , the total number of processes -RRB- . Our algorithm has O -LRB- k -RRB- remote step complexity and O -LRB- log k -RRB- system response time , where k is the point contention . The remote step complexity is the maximal number of steps performed by a process where a wait is counted as one step . The system 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 is O -LRB- N log n -RRB- , where N is the range of process names . We show how to make the space complexity of our algorithm depend solely on n , while preserving the other performance measures of the algorithm
doc_bio_tags: O O O O O O O O B I O O O O O O O B I O O O O O O O O O O B I O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O B I I O O O O O O B I I O O O O O B I O O B I I O O O O O O O O O O O O O O O O O O O O B I I O O O O O O O O O B I O O O O O O O B I O O O B I O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O B I O O O