Actualizar:
Martin Glimmerveen se dio cuenta de que Gilbert y Lynch abordaron el tema recientemente en un artículo muy legible e ilustrativo en la revista ACM Computer Magazine (febrero de 2012) llamado Perspectivas sobre el teorema de la PAC [1].
Como el artículo no está disponible de forma gratuita, permítame citar la parte que aborda la relación de FLP y CAP:
Acuerdo es imposible
Comprender la relación entre las propiedades de seguridad y vida ha sido un desafío de larga data en la informática distribuida. El tema alcanzó una gran prominencia en 1985 cuando Michael Fischer, Nancy Lynch y Michael Paterson mostraron que un acuerdo tolerante a fallas es imposible en un sistema asincrónico.
Su investigación se centró en el problema del consenso, en el que cada proceso [math] p_i [/ math] comienza con un valor inicial [math] v_i [/ math], y todos los procesos deben coincidir en uno de esos valores. Hay tres requisitos para el consenso:
- ¿Cuál es el significado de los algoritmos de aproximación? ¿Cómo debo estudiarlos?
- Si [math] \ mathbf F [/ math] no es un campo vectorial conservador, ¿eso significa que no hay una función [math] f [/ math] tal que [math] \ nabla f = \ mathbf F [/ math] ?
- ¿Alguien sabe de una prueba de acceso público de que la poda alfa beta funciona?
- ¿Qué tan bien un título en matemáticas aplicadas prepararía a alguien para la ciencia de datos?
- ¿Cómo puede una máquina lógica como una computadora generar un número aleatorio?
- acuerdo: cada proceso debe generar el mismo valor;
- validez: cada salida de valor debe haberse proporcionado como entrada para algún proceso; y
- terminación: cada proceso eventualmente debe generar un valor.
El acuerdo y la validez son propiedades de seguridad, mientras que la terminación es una propiedad vital. La imposibilidad de consenso es, por lo tanto, un ejemplo importante de la compensación inherente entre seguridad y vida.
Los requisitos de seguridad del consenso son más difíciles de cumplir que los que hemos considerado con respecto al CAP: lograr un acuerdo es (probablemente) más difícil que simplemente implementar un registro de lectura / escritura atómica. Por lo tanto, CAP también implica que es imposible lograr el consenso en un sistema sujeto a particiones.
Fischer, Lynch y Paterson no consideraron un sistema con particiones; estaban preocupados por el problema más benigno de fallas de choque. Específicamente, asumieron que un proceso desconocido puede dejar de funcionar mientras que la mayoría de los procesos en el sistema continúan comunicándose de manera confiable. Su sorprendente conclusión fue que el consenso es imposible en tal sistema. De hecho, para cada supuesto protocolo de consenso que garantiza el acuerdo y la validez, hay alguna ejecución en la que no hay fallas y, sin embargo, el algoritmo nunca termina. En el caso del consenso, la seguridad y la vida son imposibles si el sistema es potencialmente un poco defectuoso.
Este resultado ha tenido implicaciones significativas. Por ejemplo, el problema del consenso está en el corazón del paradigma de máquina de estado replicado, uno de los enfoques más comunes para construir servicios distribuidos confiables. Este paradigma logra disponibilidad al replicar el servicio en un conjunto de servidores. Los servidores luego acuerdan cada operación realizada por el servicio. La imposibilidad de un consenso tolerante a fallas implica que los servicios construidos de acuerdo con el paradigma de máquina de estado replicado no pueden lograr tanto la disponibilidad como la corrección en una red asincrónica.
Lo más interesante es su afirmación “ lograr un acuerdo es (probablemente) más difícil que simplemente implementar un registro de lectura / escritura atómica” . Si eso es cierto, el paso 2 del bosquejo de prueba a continuación también está mal. El ingenuo ‘El proponente escribe un valor para el sistema. La consistencia exige que todos los nodos lean el mismo valor después, la disponibilidad garantiza que la lectura tenga éxito ‘. no funciona de acuerdo con ellos. Es una pena que no hayan dado una referencia para esa declaración. Porque para mí, esa solución ingenua parece una forma válida de implementar un acuerdo utilizando un registro de lectura / escritura atómica.
El resto del artículo también es muy interesante, ya que analiza el progreso en la investigación de las compensaciones de seguridad / vida por consenso y estrategias (de alto nivel) para hacer frente a la PAC.
[1] http://ieeexplore.ieee.org/xpl/l…
Actualizar:
Como señaló Emin, la prueba no funciona. Lo que sigue es mi comprensión de por qué no. El documento de FLP dice [1]:
No consideramos las fallas bizantinas, y suponemos que el sistema de mensajes es confiable: entrega todos los mensajes correctamente y exactamente una vez .
Si el modelo de falla de detención de falla de la prueba FLP implicaba la posibilidad de pérdida de mensajes ( = posibles particiones de red ), consulte el paso 1 a continuación. Pero no lo hace! La entrega de mensajes con una semántica exacta una vez es una suposición mucho más fuerte sobre la red que la del teorema CAP.
Por lo tanto, un algoritmo hipotético de consenso FLP con garantía de terminación no se puede utilizar para llevar a cabo una operación de escritura coherente en tiempo limitado en una red con suposiciones más débiles sobre la entrega de mensajes (la tolerancia de partición de CAP significa solidez a la pérdida de mensajes arbitrarios).
[1] http://discolab.rutgers.edu/clas…
Boceto de prueba informal antiguo (el paso 1 es incorrecto ) :
Intentaré resolver mi propia pregunta resumiendo la gran respuesta de Henry:
- Ambos teoremas comparten el mismo modelo de red : entrega asincrónica + posible pérdida de mensajes (que es equivalente a una parada por falla en el momento de la llegada del mensaje)
- Tener consenso implica tener CAP : cada operación de escritura se resuelve utilizando un consenso sobre el valor escrito.
- Tener CAP implica tener consenso : el proponente escribe un valor para el sistema. La consistencia exige que todos los nodos lean el mismo valor después, la disponibilidad garantiza que la lectura tenga éxito.
- Consecuencia : dado que ambos teoremas implican que son equivalentes.
Mi intento de visualizar lo que a mis ojos es el conflicto central equivalente que impide la PAC / consenso: 
Entonces, probablemente el eslabón perdido es un teorema más general: en una red poco confiable, las propiedades de terminación y seguridad de un cierto patrón son generalmente irreconciliables. Tal vez alguien finalmente detecte el patrón común de esos patrones de seguridad y los Cientos de Resultados de Imposibilidad para la Computación Distribuida que mencionó Henry serán solo uno.
