Teorema CAP
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: [1][2][3]
- 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.[4]
Història
[modifica]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.[4] 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.[5][6] 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.[1] Tanmateix, aquest darrer punt ha estat criticat.[7]
Referències
[modifica]- ↑ 1,0 1,1 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" Arxivat 2016-02-04 a Wayback Machine., royans.net
- ↑ 4,0 4,1 Eric Brewer, “CAP twelve years later: How the "rules" have changed”, IEEE Explore, Volume 45, Issue 2 (2012), pg. 23-29.
- ↑ 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"
- ↑ Mark Burgess, "Deconstructing the `CAP theorem' for CM and DevOps"
Enllaços externs
[modifica]- "A plain english introduction to CAP Theorem" Arxivat 2012-05-17 a Wayback Machine. Explains CAP and eventual consistency using examples.
- "Consistency Models in Non-Relational Databases" Arxivat 2015-05-10 a Wayback Machine. 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" Arxivat 2014-02-23 a Wayback Machine. 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.