En informática teórica , el teorema CAP , también llamado teorema de Brewer en honor al científico informático Eric Brewer , establece que cualquier almacén de datos distribuidos puede proporcionar sólo dos de las tres garantías siguientes: [1] [2] [3]
Cuando ocurre una falla en la partición de la red , se debe decidir si se realiza una de las siguientes acciones:
Por tanto, si hay una partición de red, hay que elegir entre coherencia o disponibilidad. Tenga en cuenta que la coherencia definida en el teorema CAP es bastante diferente de la coherencia garantizada en las transacciones de la base de datos ACID . [4]
Ningún sistema distribuido está a salvo de fallas en la red, por lo que generalmente se debe tolerar la partición de la red. [5] [6] En presencia de una partición, uno queda con dos opciones: coherencia o disponibilidad . Al elegir coherencia sobre disponibilidad, el sistema devolverá un error o un tiempo de espera si no se puede garantizar que una información particular esté actualizada debido a la partición de la red. Al elegir disponibilidad sobre 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 una partición, se pueden satisfacer tanto la disponibilidad como la coherencia. [7]
Los sistemas de bases de datos diseñados teniendo en cuenta las garantías ACID tradicionales, como RDBMS, prefieren la coherencia a la disponibilidad, mientras que los sistemas diseñados en torno a la filosofía BASE , común en el movimiento NoSQL , por ejemplo, eligen la disponibilidad a la coherencia. [8]
Según el informático Eric Brewer de la Universidad de California, Berkeley , el teorema apareció por primera vez en otoño de 1998. [8] Fue publicado como principio CAP en 1999 [9] y presentado como una conjetura por Brewer en el Simposio sobre Principios de 2000. de Computación Distribuida (PODC). [10] En 2002, Seth Gilbert y Nancy Lynch del MIT publicaron una prueba formal de la conjetura de Brewer, convirtiéndola en un teorema . [1]
En 2012, Brewer aclaró algunas de sus posiciones, incluido por qué el concepto "dos de tres" de uso frecuente puede ser algo engañoso porque los diseñadores de sistemas solo necesitan sacrificar la coherencia o la disponibilidad en presencia de particiones; Existen técnicas de recuperación y gestión de particiones. Brewer también señaló la diferente definición de consistencia utilizada en el teorema CAP en relación con la definición utilizada en ACID . [8] [11]
Birman y Friedman publicaron en 1996 un teorema similar que establece el equilibrio entre coherencia y disponibilidad en sistemas distribuidos. [12] El resultado de Birman y Friedman restringió este límite inferior a operaciones sin conmutación.
El teorema PACELC , introducido en 2010, [7] se basa en CAP al afirmar que incluso en ausencia de partición, existe otra compensación entre latencia y coherencia. PACELC significa que, si se produce la partición (P), el equilibrio es entre disponibilidad (A) y coherencia (C); De lo contrario (E), el equilibrio es entre latencia (L) y consistencia (C).
En febrero de 2012, Eric Brewer proporcionó una perspectiva actualizada sobre su teorema CAP [...] Brewer ahora describe el axioma "2 de 3" como algo engañoso. Señala que los diseñadores sólo necesitan sacrificar la coherencia o la disponibilidad en presencia de particiones, y que los avances en las técnicas de recuperación de particiones han hecho posible que los diseñadores alcancen altos niveles de coherencia y disponibilidad.