Teorema CAP

En Ciencias de la computación, el teorema CAP, también llamado Conjetura de Brewer, enuncia que es imposible para un sistema de cómputo distribuido garantizar simultáneamente:^[1]^[2]

La consistencia (Consistency), es decir, cualquier lectura recibe como respuesta la escritura más reciente o un error.
La disponibilidad (Availability), es decir, cualquier petición recibe una respuesta no errónea, pero sin la garantía de que contenga la escritura más reciente.
La tolerancia al particionado (Partition Tolerance), es decir, el sistema sigue funcionando incluso si un número arbitrario de mensajes son descartados (o retrasados) entre nodos de la red.

Según el teorema, un sistema no puede asegurar más de dos de estas tres características simultáneamente.^[3]

Historia

El teorema comenzó como una conjetura, presentada por Eric Brewer, de la Universidad de Berkeley en el año 2000 durante el Simposio de Principios de Computación Distribuida (PODC, en inglés).^[4] En 2002, Seth Gilbert y Nancy Lynch, del MIT, publicaron una demostración formal de la conjetura, convirtiéndola en un teorema.^[1]

Explicación

Ningún sistema distribuido está a salvo de las fallas de la red, por lo tanto , la partición de la red generalmente tiene que ser tolerada. En presencia de una partición, una se queda con dos opciones: consistencia o disponibilidad . Al elegir la consistencia sobre la disponibilidad, el sistema devolverá un error o un tiempo de espera si no se puede garantizar que la información particular esté actualizada debido a la partición de la red. Al elegir la disponibilidad sobre la coherencia, el sistema siempre procesará la consulta e intentará devolver la versión disponible más reciente de la información, incluso si no puede garantizar que esté actualizada debido a la partición de la red.

En ausencia de falla de la red, es decir, cuando el sistema distribuido se está ejecutando normalmente, se puede satisfacer tanto la disponibilidad como la consistencia.

Con frecuencia, la CAP se malinterpreta como si uno tuviera que elegir abandonar una de las tres garantías en todo momento. De hecho, la elección es realmente entre la consistencia y la disponibilidad solo cuando ocurre una partición de red o falla; en cualquier otro momento, no hay que hacer concesiones. Bases de datos relacionales como YugabyteDB, CockroachDB, LeanXcale, NuoDB o Google Spanner son ejemplos de esta falacia.

Los sistemas de base de datos diseñados teniendo en cuenta las garantías tradicionales de ACID , como RDBMS, eligen la consistencia sobre la disponibilidad, mientras que los sistemas diseñados en torno a la filosofía BASE , comunes en el movimiento NoSQL , por ejemplo, eligen la disponibilidad sobre la consistencia.

Muchos proveedores de bases de datos NoSQL han utilizado el teorema CAP como justificación para no proporcionar consistencia ACID transaccional, alegando que el teorema CAP "demuestra" que es imposible proporcionar escalabilidad y consistencia ACID al mismo tiempo. Sin embargo, un examen más detallado del teorema CAP y, en particular, de la formalización de Gilbert y Lynch, revela que el teorema CAP no se refiere en absoluto a la escalabilidad, sino sólo a la disponibilidad (la A de CAP).^[5]

El teorema de CAPELC se basa en CAP al afirmar que, incluso en ausencia de partición, se produce otra compensación entre la latencia y la consistencia.