Premium
A self‐stabilizing token‐based k ‐out‐of‐ℓ exclusion algorithm
Author(s) -
Datta A. K.,
Hadid R.,
Villain V.
Publication year - 2003
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.781
Subject(s) - mutual exclusion , generalization , security token , ring (chemistry) , computer science , process (computing) , self stabilization , resource (disambiguation) , algorithm , token ring , suzuki kasami algorithm , unit (ring theory) , root (linguistics) , discrete mathematics , mathematics , combinatorics , parallel computing , theoretical computer science , distributed computing , computer network , distributed algorithm , operating system , chemistry , mathematical analysis , mathematics education , organic chemistry , linguistics , philosophy
In this paper, we present the first self‐stabilizing solution to the k ‐out‐of‐ℓ exclusion problem on a ring. The k ‐out‐of‐ℓ exclusion problem is a generalization of the well‐known mutual exclusion problem—there are ℓ units of the shared resources, any process can request k $(1 \leq k \leq \ell)$ units of the shared resources, and no resource unit can be allocated to more than one process at one time. The space requirement of the proposed algorithm is independent of ℓ for all processors except a special processor, called Root. The stabilization time is only 5 n , where n is the size of the ring. Copyright © 2003 John Wiley & Sons, Ltd.