En la introducción de este documento Objetos compartidos eventualmente linealizables (PODC'10) , los autores han presentado la siguiente declaración sin referencias:
Sin embargo, la linealización se puede lograr si y solo si se puede resolver el consenso.
Aquí, la linealización es la propiedad de consistencia más fuerte conocida de los objetos compartidos, que se propone en el artículo Linealizabilidad: una condición de corrección para objetos concurrentes .
Me confundo acerca de la declaración anterior debido a los siguientes argumentos:
En el documento Compartiendo memoria de manera sólida en sistemas de transmisión de mensajes (JACM95) , sabemos que se puede lograr la linealización en el sistema de transmisión de mensajes asíncrono, al tiempo que tolera una minoría de fallas del proceso:
Cualquier algoritmo sin esperas basado en registros atómicos de múltiples lectores de un solo escritor puede emularse automáticamente en sistemas de paso de mensajes, siempre que al menos la mayoría de los procesadores no estén defectuosos y permanezcan conectados.
Por otro lado, el documento Imposibilidad de consenso distribuido con un proceso defectuoso (JACM85) ha demostrado el resultado imposible de consenso incluso con un solo bloqueo del proceso:
El problema del consenso involucra un sistema asíncrono de procesos, algunos de los cuales pueden no ser confiables. El problema es que los procesos confiables acuerden un valor binario. En este documento, se muestra que cada protocolo para este problema tiene la posibilidad de no terminación, incluso con un solo proceso defectuoso.
Por lo tanto, podemos llegar a la siguiente conclusión:
El consenso es más fuerte que la linealización?
¿Qué hay de malo en mis argumentos? ¿Hay algunas referencias directas para la conclusión de equivalencia ?
fuente
Respuestas:
Lo que se equivoca es "sabemos que se puede lograr la linealización en el sistema de paso de mensajes asíncrono, al tiempo que toleramos una minoría de fallas en el proceso". No lo sabemos, y de hecho está mal.
Lo que muestra la cita del documento JACM95 es que se pueden implementar registros de un solo escritor con varios lectores mediante el paso de mensajes. Y solo este tipo de registros, o cualquier otro objeto que pueda implementarse (dada una minoría de bloqueos) desde dichos registros. Esto incluye, por ejemplo, registros multi-escritor multi-lector (MWMR).
Por el contrario, la capacidad de linealización no se limita a los objetos que pueden implementarse utilizando registros de múltiples lectores de escritor único. Un ejemplo de tales objetos son aquellos que admiten operaciones (atómicas) de lectura-modificación-escritura.
De hecho, como lo señalan Attiya et al (Sección 7), tales objetos no pueden ser implementados por registros MWMR precisamente porque permiten resolver el consenso (cf. Sincronización sin esperas de Herlihy) y, por lo tanto, la implementabilidad contradiría el resultado FLP.
fuente
atomicity of operations on a single objectconsequential specifications are not violated?Eventually Linearizable Shared Objects (PODC'10)y noté que se consideraban objetos arbitrarios (en lugar de solo registros SWMR).