Structures de quorum

Plusieurs auteurs ont défini les structures de quorums pouvant être utilisées dans une va- riété de protocoles distribués [BGM86, Fu90, GMB85, IK90]. Dans cette section, ces struc- tures sont définies. Soit U un ensemble non vide de noeuds. Le terme noeud fait référence à une machine dans un réseau ou une copie d’une certaine donnée dans une base de données répliquée.Un quorum Q peut être représenté par l’ensemble de tous les sous-ensembles de U conte- nant un quorum de Q. Un tel ensemble est appelé acceptance set correspondant à Q, et il est noté par A(Q).Soit Q un quorum sur U. Un transversal de Q est un sous-ensemble de U qui a une intersection avec tous les quorums dans Q, c’est-à-dire, H ⊆ U est un transversal de Q sités du théorème 4.1. Officieusement, on dit que H domine Q2. Notons que Q2 est dominée par Q1 = {{a, b}, {a, c}, {b, c}}. La coterie Q1 est non dominée. La coterie Q2 est aussi do-Soit Q un ensemble de quorums sur U. Soit Qc un ensemble quorum complémentaire. La paire B = (Q, Qc) est appelé un quorum agreement si Qc = T r(Q). Il est facile de montrer que les quorums agreement sont les mêmes que les bicoteries dominées.

Pour éviter une confusion, nous allons utiliser le terme bicoteries non dominées dans le reste de du chapitre. Pour toute bicoterie non dominée (Q, Qc), il existe seulement trois possibilités [BGM86, IK90] : Les systèmes de quorums sont des constructions bien connus qui permettent d’améliorer les performances et la disponibilité des systèmes distribués. Ils sont aussi utilisés comme un moyen pour améliorer le temps de réponse de services déployés sur des grilles de calcul.Ils ont été employés pour mettre en applicaton beaucoup de problèmes de coordination dans les systèmes répartis tels que l’exclusion mutuelle, la réplication des données etc.Nous avons présenté dans ce chapitre les définitions formelles des structures de quorums. Nous allons utiliser ces définitions dans le but de proposer dans la suite des algorithmes pour le problème de l’exclusion mutuelle de groupe basé sur les quorums.tés du théorème 4.1. Officieusement, on dit que H domine Q2. Notons que Q2 est dominée par Q1 = {{a, b}, {a, c}, {b, c}}. La coterie Q1 est non dominée. La coterie Q2 est aussi do-Soit Q un quorum sur U. Un transversal de Q est un sous-ensemble de U qui a une intersection avec tous les quorums dans Q, c’est-à-dire, H ⊆ U est un transversal de Q sisous-ensemble de H n’est pas un transversal. L’ensemble de tous les transversaux minimaux de Q noté Tr(Q), est un quorum complémentaire.Tr=min{H ⊆ U | (∀G ∈ Q)[G ∩ H 6= ∅])}).Un quorum Q sur U est dominé s’il existe un autre quorum sur U qui domine Q. Si un tel quorum n’existe pas, alors Q est non dominé.les définitions est que l’ensemble vide est une une famille de Sperner. Pour tout ensemble S, soit |S| la cardinalité de S. Sperner a prouvé que le nombre de quorums dans une famille deUn quorum Q peut être représenté par l’ensemble de tous les sous-ensembles de U conte- nant un quorum de Q. Un tel ensemble est appelé acceptance set correspondant à Q, et il est noté par A(Q).