adaptive and efficient mutual exclusion (extended 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 on 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 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 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 algorithm presented here has O ( k ) remote step complexity and O (log k ) system response time, 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 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.
adapt efficiency mutual exclusion abstraction distributed algorithms algorithm performance process activation paper adaptive algorithm read writing operability case complexity measurement presence contention systems response time response timing interval critical section minimal log point space functional performance measurement