Diferencia entre el número de consenso N y el número de consenso infinito

Question

En el libro Programación concurrente: algoritmos, principios y fundaciones de Michel Raynal, en la Sección 16.5.1, Theorem 75 dice

Los objetos de comparación y swap tienen un número de consenso infinito.

y en la sección 16.5.2, LEMMA 40 dice

El tipo de objeto MEM-TO-MEM-SWAP tiene número de consenso N en un sistema de procesos N.

Luego, en la Sección 16.1, Autor coloca en la tabla Compare & Swap y Men-t-Mem-swaps como objetos con número de consenso infinito.

Entonces, ¿cuál es la diferencia entre objetos con número de consenso y objetos con número de consenso infinito?

Answer 1

El número de consenso de un objeto es el número máximo de procesos simultáneos que puede sincronizar con uno de esos objetos de una manera sin esperar (no entraré en lo que los medios sin esperar aquí). Por ejemplo, un registro con solo las operaciones de lectura y escritura no ayuda con la sincronización sin esperar, por lo que tiene un número de consenso 1. Se puede usar un registro con una operación de prueba y conjunto para sincronizar dos procesos en una espera. -Free de manera, pero no tres o más, por lo que el número de consenso de prueba y conjunto es 2.

$ n $ -Register Asignación, donde un proceso puede escribir atómicamente a múltiples registros, permite hasta $ 2N- 2 $ procesos para sincronizar sin esperar si hay $ n $ Registros. Más procesos requieren más registros. Por lo tanto, el número de consenso de un Objet que consiste en $ n $ Registros que pueden asignarse atómicamente es $ 2N-2 $ .

Un solo registro con una operación de comparación y intercambio es suficiente para sincronizar cualquier número de procesos sin esperar. Por lo tanto, el número de consenso de comparación y intercambio es infinito.

LEMMA 40 afirma que un objeto MEM y SWAP permite la sincronización sin esperar de todos los procesos en un sistema de $ n $ procesos concurrentes, para cualquier Número $ n $ . Esto significa que para cualquier número $ n $ , el número de consenso de mem-and-swap es al menos $ n $ < / span>. (Afirmando que el número de consenso es $ n $ en un sistema de $ n $ Los procesos son un poco de nombre inapropiado, ya que la definición del número de consenso en realidad no depende del número total de procesos). Dado que el número de consenso de MEM-and-swap es al menos $ n $ para cualquier $ n $ , es infinito.

Si prefiere otra fuente que el libro de Raynal, puede leer el original Papel por Maurice Herlihy .