Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10331967 | Information Processing Letters | 2005 | 8 Pages |
Abstract
Hadzilacos in [Proc. 20th Annual Symp. on Principles of Distributed Computing, 2001, pp. 100-106] first introduced a fairness condition, called first-come-first-served (FCFS), for group mutual exclusion. The only known FCFS group mutual exclusion algorithm is due to Hadzilacos [Proc. 20th Annual Symp. on Principles of Distributed Computing, 2001, pp. 100-106], and requires Î(N2) bounded shared registers, where N is the number of processes. We present a FCFS group mutual exclusion algorithm that uses only Î(N) bounded shared registers. (The existence of such an algorithm was posed as an open problem by Hadzilacos.)
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Srdjan Petrovic,