Utilidad del número de consenso

Question

¿Qué información y utilidad conoce el número de consenso de un objeto compartido me da?

Answer 1

Probablemente no pueda hacerlo mucho mejor que citar el resumen de Papel original de Herlihy :

Una implementación sin esperar de un objeto de datos concurrentes es uno que garantiza que cualquier proceso pueda completar cualquier operación en un número finito de pasos, independientemente de las velocidades de ejecución de los otros procesos. El problema de construir una implementación sin esperar de un objeto de datos de otra mentira en el corazón de un trabajo mucho reciente en algoritmos concurrentes, estructuras de datos concurrentes y arquitecturas multiprocesadoras. Primero, introducimos una técnica simple y general, basada en la reducción a un protocolo de consenso, para probar declaraciones de la forma, “ no hay una implementación sin esperar de x por y ". Derivamos una jerarquía de objetos, de modo que ningún objeto en un nivel tiene una implementación sin esperar en términos de objetos en niveles más bajos. En particular, mostramos que los registros de lectura / escritura atómicos, que han sido el foco de mucha atención reciente, están en la parte inferior de la jerarquía: no se pueden usar para construir implementaciones sin esperar de muchos tipos de datos simples y familiares. Además, las primitivas de sincronización clásica, como la prueba y el conjunto y la recuperación, mientras que más potentes de lo que leen y escriben, también son computacionalmente débiles, al igual que las primitivas estándar que pasan por mensaje. Segundo, sin embargo, mostramos que existen objetos universales simples de los cuales se puede construir una implementación sin esperar de cualquier objeto secuencial.