| Presentation | 2003/10/20 Speedup of Vidyasankar's Algorithm for the Group k-Exclusion Problem Masataka TAKAMURA, Tom ALTMAN, Yoshihide IGARASHI, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | The k-exclusion problem is a natural generalization of the mutual exclusion problem. Group mutual exclusion is also an interesting generalization of mutual exclusion. The latter problem was introduced by Joung, and some algorithms for the problem have been propoed by incorporating mutual exclusin algorithms. Recently 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, but not by philosophers with a different interest in the same meeting room, and up to k meeting rooms are available. Vidyasankar's algorithm is a simple modification of the n-process algorithm by Peterson for the mutual exclusion problem in the asynchronous multi-writer / multi-reader shared memory model. We propose an improvement to Vidyasanker's algorithm. By our modifications we can accelerate the original algorithm. Waiting times in the trying region of the original algorithm and 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 processed, l is 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. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | distributed algorithms / group mutual exclusion / k-exclusion / lockout avoidance / mutual exclusion / shared memory |
| Paper # | COMP2003-47 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2003/10/20(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Speedup of Vidyasankar's Algorithm for the Group k-Exclusion Problem |
| Sub Title (in English) | |
| Keyword(1) | distributed algorithms |
| Keyword(2) | group mutual exclusion |
| Keyword(3) | k-exclusion |
| Keyword(4) | lockout avoidance |
| Keyword(5) | mutual exclusion |
| Keyword(6) | shared memory |
| 1st Author's Name | Masataka TAKAMURA |
| 1st Author's Affiliation | Department of Computer Science, Gunma University() |
| 2nd Author's Name | Tom ALTMAN |
| 2nd Author's Affiliation | Department of Computer Science and Engineering, University of Colorado at Denver |
| 3rd Author's Name | Yoshihide IGARASHI |
| 3rd Author's Affiliation | Department of Computer Science, Gunma University |
| Date | 2003/10/20 |
| Paper # | COMP2003-47 |
| Volume (vol) | vol.103 |
| Number (no) | 394 |
| Page | pp.pp.- |
| #Pages | 7 |
| Date of Issue | |