reference-request – ¿Es la linealización equivalente al problema de consenso?

Pregunta:

En la introducción de este artículo Eventually Linearizable Shared Objects (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 Linealización: una condición de corrección para objetos concurrentes .

Me confunde la declaración anterior debido a los siguientes argumentos:

En el artículo Compartir memoria de forma robusta en sistemas de paso de mensajes (JACM95) , sabemos que se puede lograr la linealización en el sistema de paso de mensajes asincrónico, mientras se tolera una minoría de bloqueos de procesos:

Cualquier algoritmo sin esperas basado en registros atómicos de múltiples lectores de un solo escritor se puede emular automáticamente en sistemas de paso de mensajes, siempre que al menos la mayoría de los procesadores no tengan fallas y permanezcan conectados.

Por otro lado, el documento Imposibilidad del consenso distribuido con un proceso defectuoso (JACM85) ha demostrado la imposibilidad del resultado del consenso incluso con un solo colapso del proceso:

El problema del consenso involucra un sistema asincrónico de procesos, algunos de los cuales pueden no ser confiables. El problema es que los procesos confiables se pongan de acuerdo en un valor binario. En este artículo, se muestra que cada protocolo para este problema tiene la posibilidad de no ser terminado, incluso con un solo proceso defectuoso.

Por 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? ¿Existen algunas referencias directas para la conclusión de equivalencia ?

Respuesta:

Lo que se equivoca es que "sabemos que la linealización se puede lograr en el sistema de paso de mensajes asincrónico, mientras se tolera una minoría de bloqueos de procesos". No lo sabemos y, de hecho, está mal.

Lo que muestra la cita del artículo JACM95 es que los registros de múltiples lectores de un solo escritor se pueden implementar mediante el paso de mensajes. Y solo este tipo de registros, o cualquier otro objeto que se pueda implementar (dada una minoría de bloqueos) desde dichos registros. Esto incluye, por ejemplo, registros de múltiples lectores y múltiples escritores (MWMR).

Por el contrario, la linealización no se limita a los objetos que se pueden implementar utilizando registros de un solo escritor y de varios lectores. Un ejemplo de tales objetos son los que admiten operaciones (atómicas) de lectura, modificación y escritura.

De hecho, como señalan Attiya et al (Sección 7), tales objetos no pueden ser implementados por registros MWMR de manera precisa porque permiten resolver el consenso (cf. Sincronización sin espera de Herlihy) y, por lo tanto, la implementabilidad contradeciría el resultado de FLP.

Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top

web tasarım