Pourquoi le nombre de consensus pour test-and-set, 2?

Selon Wikipedia ,

L'opération de test et de configuration peut résoudre le problème du consensus sans attente pour pas plus de deux processus simultanés.

Pourquoi ne peut-il pas résoudre le problème pour plus de deux processus?

Juste pour nous assurer que nous sommes sur la même page, considérons d'abord ces trois définitions:

Définition. Test-and-set est une instruction lecture-modification-écriture sur un registre binaire (disons simplement que 0 et 1 sont des valeurs possibles) où un thread obtient l'ancienne valeur et écrit 1.

Définition. Un consensus est atteint entre threads si tous les n threads décident de la même valeur (l'exigence de cohérence) et tous les threads décident d'une valeur réellement proposée par l'un des threads (l'exigence de validité).$n$$n$

Defintion. Un protocole de consensus est sans attente si chaque appel de méthode se termine en un nombre fini d'étapes.

Suivez maintenant deux croquis de preuve.

Allégation 1. Le nombre consensuel de test-et-set est d'au moins 2. Preuve. Supposons que nous ayons deux fils 0 et 1 qui doivent parvenir à un consensus. Nous pourrions le faire en laissant chaque fil suivre le protocole de consensus ci-dessous:

1. Écrivez la valeur que vous proposez dans , où t est l'ID du thread et A est un tableau de taille 2.$A[t]$$t$$A$
2. Exécutez l'instruction de test et de définition sur un registre , avec R initialisé à 0.$R$$R$
3. Si la valeur de retour est 0, vous étiez le premier: renvoyez . Sinon, vous étiez deuxième: renvoyez A [ | t - 1 | ] .$A[t]$$A[|t-1|]$

Vous pouvez vous vérifier que le consensus et la non-attente sont satisfaits. $\square$

(Pour la prochaine preuve, je vais imbriquer quelques preuves et définitions parce que je pense que cela facilitera leur suivi.)

Revendication 2. Le nombre consensuel de test-et-set est au plus 2. Preuve. Par contradiction. Supposons que nous ayons trois threads , B et C qui souhaitent décider des valeurs a , b et c , respectivement, et que nous avons un protocole de consensus sans attente valide qui est implémenté à l'aide de test-and-set (et de lectures et écritures atomiques ).$A$$B$$C$$a$$b$$c$

Nous pouvons visualiser le processus de consensus comme un arbre dirigé, où:

• La racine est l'état où aucun des threads n'a «bougé»;
• L'enfant gauche d'un nœud représente l'état qui résulte après un déplacement de , l'enfant du milieu représente l'état qui résulte après un déplacement de B et l'enfant droit représente l'état qui résulte après un déplacement de C ;$A$$B$$C$
• Un nœud feuille représente un état dans lequel tous les threads sont terminés. Un nœud feuille est associé à une valeur , b ou c , où la valeur dépend de la valeur qui a été décidée pour cette exécution particulière.$a$$b$$c$

Définition. Qu'un État soit multivalent si le résultat du processus de consensus n'est pas encore déterminé. En d'autres termes, tous les entrelacements possibles des mouvements restants ne conduisent pas au même résultat. Laissez un État être univalent lorsque le résultat du processus de consensus est déterminé.

La racine est multivalente. Preuve. Si un seul thread est actif et que les autres threads restent dormants pour toujours, alors X se terminera en un nombre fini d'étapes (garanti par l'hypothèse d'attente sans liberté) et il décidera de x (car il n'a accès qu'à cette valeur et à son décision satisfera à l'exigence de validité du consensus). Donc, pour notre situation, a , b et$X$$X$$x$$a$$b$ sont tous des résultats possibles. $c$$\square$

Définition. Soit un état critique un état qui est multivalent, avec la propriété supplémentaire qu'un mouvement de déterminera a , et un mouvement de$A$$a$ déterminera b .$B$$b$

Il existe un état critique. Preuve. D'en haut, nous savons que nous commençons dans un état multivalent. Que ne bouge pas du tout. Tant que A ou B ne force pas l'arbre dans un état univalent, laissez-le faire un mouvement. La non-attente garantit que l'arbre est fini, donc à un moment donné, un état critique doit être rencontré. $C$$A$$B$$\square$

Considérons maintenant un scénario où nous sommes dans un état critique. Il y a au moins deux possibilités:

1) se déplace (déterminant ainsi a ) et s'arrête. B fait alors son mouvement et s'arrête. Le C suivant s'exécute jusqu'à la fin, décidant finalement a .$A$$a$$B$$C$$a$

2) se déplace (déterminant ainsi b ) et s'arrête. Le C suivant s'exécute jusqu'à la fin, décidant finalement b . A ne bouge pas.$B$$b$$C$$b$$A$

Étant donné que les lectures et écritures atomiques ont le consensus numéro 1, les mouvements de et B devaient être des instructions de test et de réglage sur le même registre (si les registres sont différents, alors C ne serait pas en mesure de dire l'ordre dans lequel A et Les mouvements de B se sont produits). Du point de vue de C , donc, les scénarios 1 et 2 sont indiscernables, donc nous devons avoir que C décide à la fois a et b . C'est impossible. $A$$B$$C$$A$$B$$C$$C$$a$$b$$\square$

Le fait que l'instruction de test et de définition ait le consensus numéro 2 découle à la fois des revendications 1 et 2.

L'article de wikipedia a une référence qui répond à votre question, mais peut-être que vous ne voulez pas lire ce papier de 26 pages. Je vais donner une version simplifiée de la preuve (assez technique), montrant que test-and-set ne peut pas résoudre le consensus binaire pour 3 processus. Ce type d'argument est largement utilisé pour prouver les chiffres du consensus.

Supposons que nous ayons un algorithme de consensus utilisant des registres TAS pour 3 processus.

À tout moment, chaque processus aura un mouvement (instruction) prêt à être exécuté. Laquelle des trois instructions sera exécutée n'est pas déterministe.

Supposons que nous soyons dans un état bivalent (un état dans lequel une décision 0 ou 1 est toujours possible) et quel que soit le processus qui se déplace ensuite, l'état suivant sera univalent. Un tel état doit finalement être atteint en raison de la condition sans attente.

Supposons (wlg) que si le processus 1 se déplace, l'état sera 0-valent et que si le processus 2 se déplace, l'état sera 1-valent. Les deux mouvements doivent être une opération TAS (ou au moins: une sorte d'écriture) sur le même registre, car s'il s'agissait d'opérations TAS sur des registres distincts, nous ne pourrions pas dire si le processus 1 s'est déplacé en premier ou le processus 2 s'est déplacé en premier.

Examinons ces deux exécutions possibles:

• Le processus 1 se déplace en premier, puis le processus 2 se déplace, puis le processus 3 s'exécute seul
• Le processus 2 se déplace en premier, puis le processus 3 s'exécute seul

Du point de vue du processus 3, ces états sont indiscernables car il ne voit que la valeur écrite par le processus 2. Cependant, dans le premier cas, il doit donner 0 en sortie et dans le second 1 en sortie. Il s'agit clairement d'une contradiction.

Les processus 1 et 2 peuvent décider entre eux qui s'est déplacé en premier (car ils peuvent voir quelle valeur était dans le registre avant leur écriture) mais un troisième processus spectateur ne peut pas.

Une autre façon de prouver que test-and-set ne peut pas être utilisé pour résoudre le consensus des 3 processeurs est de montrer que le test-and-set peut être implémenté en utilisant le consensus des 2 processeurs. Ensuite, en supposant que test-and-set peut résoudre le consensus des 3 processeurs conduit à une contradiction: Supposons que test-and-set puisse résoudre le consensus des 3 processeurs; puis en remplaçant test-and-set par sa mise en œuvre en utilisant le consensus à 2 processeurs on obtient une implémentation du consensus à 3 processeurs en utilisant le consensus à 2 processeurs, ce qui est impossible. Ainsi, test-and-set ne peut pas résoudre le consensus des 3 processeurs.

Pour implémenter test-and-set pour n-processeurs en utilisant le consensus de 2 processeurs, laissez les processeurs déterminer un gagnant du test-and-set en utilisant un tournoi dans lequel chaque correspondance est implémentée en utilisant le consensus de 2 processeurs (dans une correspondance, les processeurs proposer leur identifiant et le résultat du consensus leur dit qui gagne).

En pratique, une définition de consensus moins stricte pourrait suffire (je l'appelle ici consensus léger):

Définition . Light-Consensus est atteint entre n threads ssi (a) chaque thread décide de la même valeur ou la valeur est inconnue pour elle, (b) au moins un thread connaît la valeur et (c) cette valeur a été effectivement proposée par l'un des les fils.

Par conséquent, ce consensus dans son sens le plus léger permet que certains threads ne connaissent pas le consensus, la valeur qui est décidée.

Corollaire : dans ce sens plus léger, le test et l'ensemble ont un nombre de consensus de lumière infini.

Allégation : ce sens plus léger est pratique. Par exemple, afin de sélectionner le fil pour entrer dans la section critique, il n'est pas nécessaire de créer un consensus au sens strict. C'est-à-dire: chaque thread doit savoir s'il a été sélectionné ou non, mais s'il n'est pas sélectionné, il n'aura pas à savoir lequel a été sélectionné. En d'autres termes, pour l'exclusion mutuelle, un consensus strict n'est pas nécessaire, la lumière suffit.