| Presentation | 2000/11/10 A Lockout Avoidance Algorithm for the κ-Exclusion Problem Kumiko Obokata, Michiko Omori, Yoshihide Igarashi, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | We propose a κ-lockout avoidance algorithm without using time-stamps on asynchronous multi-writer/reader shared memory model for the κ-exclusion problem. This algorithm is a modification of the n-process algorithm by Peterson or a variation of the algorithm accelerated by Igarashi and Nishitani. The correctness and efficiency of the algorithm are shown. The running time for the trying region of any faultless process is bounded by(n-κ)c+O(n(n-κ)^2l)even if there exist at most κ-1 process failures of the stopping type, where n is the number of processes, l is an upper bound on the time between successive two atomic steps for faultless processes, and c is is an upper bound on the time that any user spends in the critical region. When κ=O(1), we can improve the running time for the trying region to(n-κ)c+O(nl)by using the group tournament technique. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | asynchronous processes / concurrent computation / κ-exclusion / lockout avoidance / shared memory |
| Paper # | COMP2000-54 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2000/11/10(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) | A Lockout Avoidance Algorithm for the κ-Exclusion Problem |
| Sub Title (in English) | |
| Keyword(1) | asynchronous processes |
| Keyword(2) | concurrent computation |
| Keyword(3) | κ-exclusion |
| Keyword(4) | lockout avoidance |
| Keyword(5) | shared memory |
| 1st Author's Name | Kumiko Obokata |
| 1st Author's Affiliation | Department of Computer Science, Gunma University() |
| 2nd Author's Name | Michiko Omori |
| 2nd Author's Affiliation | Department of Computer Science, Gunma University |
| 3rd Author's Name | Yoshihide Igarashi |
| 3rd Author's Affiliation | Department of Computer Science, Gunma University |
| Date | 2000/11/10 |
| Paper # | COMP2000-54 |
| Volume (vol) | vol.100 |
| Number (no) | 449 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |