# k-Arbiter: A Safe and General Scheme for h-out of-k Mutual Exclusion Problems

1 ADP - Distributed Algorithms and Protocols
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, INRIA Rennes
Abstract : Mutual exclusion is a well-known problem that arise when multiple processes compete, in an uncoordinated way, for the acquisition of shared resources over a distributed system. In particular, k-mutual exclusion allows at most k processes to get one unit of the same resource simultaneously. These paradigms do not cover all the cases in which resource accesses must be serialized over a distributed system. There exist cases (e.g. the bandwidth of communication lines) where the amount of shared resource might differ from request to request (for example, audio and video communications). In this paper, we formalize this problem as the {h-out of-k mutual exclusion problem}, in which each request concerns some number h $(1 \le h \le k)$ of units of shared resource and no unit is allocated to multiple processes at the same time. We present a general scheme for a {\em quorum-based h-out of-k mutual exclusion algorithm} that relies on a collection of quorums called {\em $k$-arbiter}. Several examples of $k$-arbiters are discussed, two particular classes of k-arbiters are investigated and a metric to evaluate the resiliency with respect to failures of k-arbiters is also given.
Keywords :
Type de document :
Rapport
[Research Report] RR-2523, INRIA. 1995
Domaine :

https://hal.inria.fr/inria-00074154
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 14:37:49
Dernière modification le : mercredi 16 mai 2018 - 11:23:02
Document(s) archivé(s) le : lundi 5 avril 2010 - 00:06:04

### Identifiants

• HAL Id : inria-00074154, version 1

### Citation

Roberto Baldoni, Yoshifumi Manabe, Michel Raynal, Shigemi Aoyagi. k-Arbiter: A Safe and General Scheme for h-out of-k Mutual Exclusion Problems. [Research Report] RR-2523, INRIA. 1995. 〈inria-00074154〉

### Métriques

Consultations de la notice

## 223

Téléchargements de fichiers