Speedup of Vidyasankar's algorithm for the group k-exclusion problem
Vidyasankar introduced a combined problem of k-exclusion and group mutual exclusion, called the group k-exclusion problem, which occurs in a situation where philosophers with the same interest can attend a forum in a meeting room, and up to k meeting rooms are available. We propose an improvement to Vidyasankar's algorithm. Waiting times in the trying region in the original algorithm and in our algorithm are bounded by n(n - k)c + O(n(3)(n - k))l and (n - k)c + O(n(n - k)(2))l, respectively, where n is the number of processes, 1 is an upper bound on the time between successive two atomic steps, and c is an upper bound on the time that any philosopher spends in a forum. (C) 2004 Elsevier B.V. All rights reserved.
k-exclusion group mutual exclusion mutual exclusion distributed computing lockout avoidance shared memory