Différence entre le numéro de consensus N et le numéro de consensus infini

Question

Dans le livre Programmation simultanée: algorithmes, principes et fondations de Michel Raynal, à la section 16.5.1, le théorème 75 dit

Les objets de comparaison et de swap ont un numéro de consensus infini.

et à la section 16.5.2, Lemma 40 dit

Le type d'objet Mem-to-Mem-Swap a un numéro de consensus N dans un système de n processus.

Puis, dans la section 16.1, l'auteur met dans la table à la fois comparer et échanger et échanger des hommes à l'échange comme des objets avec un numéro de consensus infini.

Donc, quelle est la différence entre les objets avec le numéro de consensus N et les objets avec un numéro de consensus infini?

Answer 1

Le numéro de consensus d'un objet est le nombre maximal de processus concurrents que vous pouvez synchroniser avec un tel objet de manière sans attente (je n'entrerai pas dans quels moyens sans attente ici). Par exemple, un registre avec uniquement des opérations de lecture et d'écriture n'aident pas le tout à la synchronisation sans attente, il a donc un numéro de consensus 1. Un registre avec une opération de test et défini peut être utilisé pour synchroniser deux processus dans une attente -free de manière, mais pas trois ou plus, le numéro de consensus d'essai et de l'ensemble est 2.

N $ N $ -register affectation, où un processus peut écrire atomé de multiples registres, permet de $ 2N- 2 $ Processus Pour synchroniser sans attente s'il y a N $ N $ registres. Plus de processus nécessitent plus de registres. Par conséquent, le numéro de consensus d'un objet constitué de $ N $ registres pouvant être attribués atomiquement est $ 2n-2 $ .

Un registre unique avec une opération de comparaison-et-swap est suffisant pour synchroniser tout nombre de processus sans attente. Par conséquent, le numéro de consensus de comparaison-et-échange est infini.

lemma 40 stipule qu'un objet Mem-and-Swap permet la synchronisation sans attente de tous les processus d'un système de $ N $ processus concurrents, pour tout Numéro N $ N $ . Cela signifie que pour n'importe quel nombre $ n $ , le numéro de consensus de MEM-and-Swap est au moins $ n $ < / span>. (Indiquant que le nombre de consensus est $ n $ dans un système de $ n $ Les processus sont un peu mal informés car la définition du numéro de consensus ne dépend pas du nombre total de processus.) Depuis le numéro de consensus de Mem-and-Swap est au moins $ N $ pour tout $ n $ , c'est infini.

Si vous préférez une autre source que le livre de Raynal, vous pouvez lire l'original Papier de Maurice Herlihy .