Utilité du numéro de consensus

Question

Quelle information et l'utilité connaissent-ils le numéro consensus d'un objet partagé me donnent-ils?

Answer 1

Vous ne pouvez probablement pas faire beaucoup mieux que citer le résumé de Le papier original de Herlihy :

Une mise en œuvre sans attente d'un objet de données simultané est celle qui garantit que tout processus peut compléter toute opération dans un nombre fini d'étapes, quelles que soient les vitesses d'exécution des autres processus. Le problème de la construction d'une mise en œuvre sans attente d'un objet de données d'un autre réside dans le cœur d'un travail très récent dans des algorithmes simultanés, des structures de données simultanées et des architectures multiprocesseurs. Premièrement, nous introduisons une technique simple et générale, basée sur la réduction d'un protocole de consensus, pour prouver des déclarations de la forme, et # 8220; il n'y a pas de mise en œuvre sans attente de x par Y. " Nous tirons une hiérarchie d'objets tels qu'aucun objet à un niveau n'a de mise en œuvre sans attente en termes d'objets à des niveaux inférieurs. En particulier, nous montrons que les registres de lecture / écriture atomique, qui ont été au centre de l'attention beaucoup récente, sont au bas de la hiérarchie: elles ne peuvent pas être utilisées pour construire des implémentations sans attente de nombreux types de données simples et familiers. De plus, des primitives de synchronisation classique telles que Test & Set et Fetch & Ajouter, bien que plus puissantes que de lecture et d'écriture, sont également calculées de manière informelle, de même que les primitives standard de passage de message. Deuxièmement, néanmoins, nous montrons qu'il existe des objets universels simples à partir duquel on peut construire une implémentation sans attente de tout objet séquentiel.