En informàtica teòrica, el teorema CAP, també conegut com a teorema de Brewer, formula que és impossible garantir simultàniament les tres característiques següents en una aplicació distribuïda: Seth Gilbert and Nancy Lynch, “Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services”, ACM SIGACT News, Volume 33 Issue 2 (2002), pg. 51-59."Brewer's CAP Theorem", julianbrowne.com, Retrieved 02-Mar-2010"Brewers CAP theorem on distributed systems" , royans.net Consistència (tots els nodes veuen la mateixa dada al mateix temps) Disponibilitat (la garantia que cada petició a un node rep una resposta de si ha tingut èxit o a fallat) Tolerància a la partició (el sistema continua operant malgrat la partició arbitrària a causa d'errors en la xarxa) El 2012 Brewer va aclarir alguna de les seves posicions com que el concepte "dos de tres" ("two out of three") pot ser malentès o pot induir a error i també el perquè de la definició de consistència CAP divergeix respecte a la de ACID.Eric Brewer, “CAP twelve years later: How the "rules" have changed”, IEEE Explore, Volume 45, Issue 2 (2012), pg. 23-29.
Història El teorema va ser formulat per primer cop per l'informàtic Eric Brewer de la Universitat de Califòrnia durant la tardor de 1998. Va ser publicat com a principi CAP a l'any següent i va ser presentat per Brewer com a conjectura en el Symposium on Principles of Distributed Computing (PODC) de l'any 2000.Armando Fox and Eric Brewer, “Harvest, Yield and Scalable Tolerant Systems”, Proc. 7th Workshop Hot Topics in Operating Systems (HotOS 99), IEEE CS, 1999, pg. 174-178.Eric Brewer, "Towards Robust Distributed Systems" El 2002, Seth Gilbert i Nancy Lynch del MIT van publicar una demostració formal de la conjectura de Brewer, fet que la convertia en teorema. Tanmateix, aquest darrer punt ha estat criticat.Mark Burgess, "Deconstructing the `CAP theorem' for CM and DevOps"
Explicació No hi ha cap sistema distribuït a prova de fallades de xarxa, per tant la tolerància a la partició -errors de xarxa- generalment ha de ser tolerada. En presència d'una partició, s'ha d'escollir una de les dues opcions: consistència o disponibilitat.
A l'hora d'escollir consistència sobre disponibilitat, el sistema retornarà un error, o un temps d'espera indeterminat, si no es pot garantir, a causa de la partició de la xarxa, que la informació estigui actualitzada a tots els nodes.
En triar la disponibilitat per sobre de la consistència, el sistema sempre processarà la consulta i intentarà retornar la versió més recent disponible de la informació, encara que no pugui garantir que estigui actualitzada a tots els nodes, a causa de la partició de la xarxa.
En absència de partició, tant la disponibilitat com la consistència es poden satisfer.
Referències
Enllaços externs "A plain english introduction to CAP Theorem" Explains CAP and eventual consistency using examples. "Consistency Models in Non-Relational Databases" Explains CAP Theorem and eventual consistency in distributed environments. "Problems with CAP, and Yahoo's little known NoSQL system" Discusses PACELC, an alternative to CAP. "Returning Transactions to Distributed Data Stores" Discusses the CAP Theorem as it applies to NoSQL systems. "You can't sacrifice partition tolerance, by Codahale" Discusses practical implications of CAP Theorem in real world systems. Categoria:Aplicació distribuïda