97:
123:. When choosing consistency over availability, the system will return an error or a time out if particular information cannot be guaranteed to be up to date due to network partitioning. When choosing availability over consistency, the system will always process the query and try to return the most recent available version of the information, even if it cannot guarantee it is up to date due to network partitioning.
1149:
1159:
1169:
658:... Brewer now describes the "2 out of 3" axiom as somewhat misleading. He notes that designers only need sacrifice consistency or availability in the presence of partitions, and that advances in partition recovery techniques have made it possible for designers to achieve high levels of both consistency and availability.
208:, introduced in 2010, builds on CAP by stating that even in the absence of partitioning, there is another trade-off between latency and consistency. PACELC means, if partition (P) happens, the trade-off is between availability (A) and consistency (C); Else (E), the trade-off is between latency (L) and consistency (C).
192:
In 2012, Brewer clarified some of his positions, including why the often-used "two out of three" concept can be somewhat misleading because system designers only need to sacrifice consistency or availability in the presence of partitions; partition management and recovery techniques exist. Brewer
60:
Every request received by a non-failing node in the system must result in a response. This is the definition of availability in CAP theorem as defined by
Gilbert and Lynch. Note that availability as defined in CAP theorem is different from
200:
A similar theorem stating the trade-off between consistency and availability in distributed systems was published by Birman and
Friedman in 1996. Birman and Friedman's result restricted this lower bound to non-commuting operations.
104:
Thus, if there is a network partition, one has to choose between consistency or availability. Note that consistency as defined in the CAP theorem is quite different from the consistency guaranteed in
119:
No distributed system is safe from network failures, thus network partitioning generally has to be tolerated. In the presence of a partition, one is then left with two options: consistency or
759:
742:
170:
754:
134:
1193:
1152:
278:
Gilbert, Seth; Lynch, Nancy (2002). "Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services".
825:
714:
391:
366:
217:
162:
1172:
647:
88:
proceed with the operation and thus provide availability but risk inconsistency. Note this doesn't necessarily mean that system is
73:
The system continues to operate despite an arbitrary number of messages being dropped (or delayed) by the network between nodes.
878:
1129:
1198:
776:
138:
1068:
1094:
813:
490:
519:
1017:
1007:
783:
549:
1104:
837:
637:
233:
408:
193:
also noted the different definition of consistency used in the CAP theorem relative to the definition used in
165:, the theorem first appeared in autumn 1998. It was published as the CAP principle in 1999 and presented as a
1063:
1053:
707:
238:
158:
32:
766:
1134:
1089:
36:
339:
1109:
863:
1162:
1099:
981:
951:
820:
771:
448:
142:
108:
68:
1119:
1012:
997:
924:
749:
243:
222:
619:
174:
1114:
1058:
1027:
976:
808:
700:
577:
464:
438:
303:
248:
868:
934:
788:
643:
569:
387:
362:
295:
89:
78:
62:
47:
1124:
971:
961:
929:
675:
600:
599:. Proc. 7th Workshop Hot Topics in Operating Systems (HotOS 99). IEEE CS. pp. 174–178.
561:
456:
321:
287:
1032:
1002:
956:
737:
96:
20:
452:
1084:
1022:
966:
939:
832:
793:
228:
205:
434:
1187:
903:
888:
307:
468:
126:
In the absence of a partition, both availability and consistency can be satisfied.
120:
55:
16:
Need to sacrifice consistency or availability in the presence of network partitions
581:
893:
671:
654:
In
February 2012, Eric Brewer provided an updated perspective on his CAP theorem
178:
1037:
946:
908:
883:
692:
604:
166:
85:
cancel the operation and thus decrease the availability but ensure consistency
573:
299:
291:
898:
853:
723:
253:
40:
520:"DBMS Musings: Problems with CAP, and Yahoo's little known NoSQL system"
81:
failure happens, it must be decided whether to do one of the following:
565:
460:
186:
560:(2). Institute of Electrical and Electronics Engineers (IEEE): 23–29.
803:
679:
443:
798:
146:
95:
858:
194:
185:
published a formal proof of Brewer's conjecture, rendering it a
130:
105:
696:
182:
672:"Trading Consistency for Availability in Distributed Systems"
149:
movement for example, choose availability over consistency.
437:(Report). Apollo - University of Cambridge Repository.
286:(2). Association for Computing Machinery (ACM): 51–59.
141:
over availability, whereas systems designed around the
550:"CAP twelve years later: How the "rules" have changed"
52:
Every read receives the most recent write or an error.
1077:
1046:
990:
917:
846:
730:
171:Symposium on Principles of Distributed Computing
273:
271:
269:
708:
543:
541:
539:
8:
597:Harvest, Yield and Scalable Tolerant Systems
340:"Brewers CAP Theorem on distributed systems"
636:Carpenter, Jeff; Hewitt, Eben (July 2016).
129:Database systems designed with traditional
715:
701:
693:
442:
513:
511:
491:"Please stop calling databases CP or AP"
670:Ken Birman; Roy Friedman (April 1996).
265:
7:
620:"Towards Robust Distributed Systems"
409:"The confusing CAP and ACID wording"
1168:
218:Fallacies of distributed computing
163:University of California, Berkeley
14:
595:Armando Fox; Eric Brewer (1999).
1167:
1157:
1148:
1147:
642:(2nd ed.). O'Reilly Media.
433:Kleppmann, Martin (2015-09-18).
157:According to computer scientist
1158:
639:Cassandra: The Definitive Guide
1:
435:A Critique of the CAP Theorem
518:Abadi, Daniel (2010-04-23).
1194:Database management systems
724:Database management systems
133:guarantees in mind such as
1215:
1130:Object–relational database
145:philosophy, common in the
41:two of the following three
1143:
1105:Federated database system
838:Blockchain-based database
605:10.1109/HOTOS.1999.798396
100:CAP theorem Euler diagram
65:in software architecture.
31:after computer scientist
234:Paxos (computer science)
495:Martin Kleppmann's Blog
239:Raft (computer science)
1135:Transaction processing
1090:Database normalization
1033:Query rewriting system
322:"Brewer's CAP Theorem"
169:by Brewer at the 2000
101:
37:distributed data store
1199:Distributed computing
1110:Referential integrity
548:Brewer, Eric (2012).
382:Fowler, Adam (2015).
357:Fowler, Adam (2015).
292:10.1145/564585.564601
109:database transactions
99:
1100:Distributed database
1120:Relational calculus
998:Concurrency control
489:Martin, Kleppmann.
453:2015arXiv150905393K
223:Lambda architecture
69:Partition tolerance
1115:Relational algebra
1059:Query optimization
864:Armstrong's axioms
566:10.1109/mc.2012.37
461:10.17863/CAM.13083
407:Liochon, Nicolas.
249:Inconsistent triad
102:
35:, states that any
1181:
1180:
789:Wide-column store
784:Document-oriented
384:NoSQL For Dummies
359:NoSQL For Dummies
173:(PODC). In 2002,
79:network partition
63:high availability
39:can provide only
1206:
1171:
1170:
1161:
1160:
1151:
1150:
1125:Relational model
1095:Database storage
972:Stored procedure
717:
710:
703:
694:
684:
683:
667:
661:
660:
657:
633:
627:
626:
624:
615:
609:
608:
592:
586:
585:
545:
534:
533:
531:
530:
515:
506:
505:
503:
501:
486:
480:
479:
477:
475:
446:
430:
424:
423:
421:
419:
404:
398:
397:
379:
373:
372:
354:
348:
347:
336:
330:
329:
326:julianbrowne.com
318:
312:
311:
275:
244:Zooko's triangle
90:highly available
29:Brewer's theorem
1214:
1213:
1209:
1208:
1207:
1205:
1204:
1203:
1184:
1183:
1182:
1177:
1139:
1085:Database models
1073:
1042:
1028:Query optimizer
1003:Data dictionary
986:
957:Transaction log
913:
869:Codd's 12 rules
842:
772:Column-oriented
738:Object-oriented
726:
721:
690:
688:
687:
669:
668:
664:
655:
650:
635:
634:
630:
622:
617:
616:
612:
594:
593:
589:
547:
546:
537:
528:
526:
517:
516:
509:
499:
497:
488:
487:
483:
473:
471:
432:
431:
427:
417:
415:
406:
405:
401:
394:
386:. For Dummies.
381:
380:
376:
369:
361:. For Dummies.
356:
355:
351:
338:
337:
333:
320:
319:
315:
280:ACM SIGACT News
277:
276:
267:
262:
214:
155:
117:
21:database theory
17:
12:
11:
5:
1212:
1210:
1202:
1201:
1196:
1186:
1185:
1179:
1178:
1176:
1175:
1165:
1155:
1144:
1141:
1140:
1138:
1137:
1132:
1127:
1122:
1117:
1112:
1107:
1102:
1097:
1092:
1087:
1081:
1079:
1078:Related topics
1075:
1074:
1072:
1071:
1066:
1061:
1056:
1054:Administration
1050:
1048:
1044:
1043:
1041:
1040:
1035:
1030:
1025:
1023:Query language
1020:
1015:
1010:
1005:
1000:
994:
992:
988:
987:
985:
984:
979:
974:
969:
964:
959:
954:
949:
944:
943:
942:
937:
932:
921:
919:
915:
914:
912:
911:
906:
901:
896:
891:
886:
881:
876:
871:
866:
861:
856:
850:
848:
844:
843:
841:
840:
835:
830:
829:
828:
818:
817:
816:
806:
801:
796:
791:
786:
781:
780:
779:
769:
764:
763:
762:
757:
747:
746:
745:
734:
732:
728:
727:
722:
720:
719:
712:
705:
697:
686:
685:
662:
648:
628:
610:
587:
535:
507:
481:
425:
399:
393:978-8126554904
392:
374:
368:978-8126554904
367:
349:
331:
313:
264:
263:
261:
258:
257:
256:
251:
246:
241:
236:
231:
229:PACELC theorem
226:
220:
213:
210:
206:PACELC theorem
154:
151:
116:
113:
94:
93:
92:to its users.
86:
75:
74:
71:
66:
58:
53:
50:
15:
13:
10:
9:
6:
4:
3:
2:
1211:
1200:
1197:
1195:
1192:
1191:
1189:
1174:
1166:
1164:
1156:
1154:
1146:
1145:
1142:
1136:
1133:
1131:
1128:
1126:
1123:
1121:
1118:
1116:
1113:
1111:
1108:
1106:
1103:
1101:
1098:
1096:
1093:
1091:
1088:
1086:
1083:
1082:
1080:
1076:
1070:
1067:
1065:
1062:
1060:
1057:
1055:
1052:
1051:
1049:
1045:
1039:
1036:
1034:
1031:
1029:
1026:
1024:
1021:
1019:
1016:
1014:
1011:
1009:
1006:
1004:
1001:
999:
996:
995:
993:
989:
983:
980:
978:
975:
973:
970:
968:
965:
963:
960:
958:
955:
953:
950:
948:
945:
941:
938:
936:
933:
931:
928:
927:
926:
923:
922:
920:
916:
910:
907:
905:
904:Surrogate key
902:
900:
897:
895:
892:
890:
889:Candidate key
887:
885:
882:
880:
877:
875:
872:
870:
867:
865:
862:
860:
857:
855:
852:
851:
849:
845:
839:
836:
834:
831:
827:
824:
823:
822:
819:
815:
812:
811:
810:
807:
805:
802:
800:
797:
795:
792:
790:
787:
785:
782:
778:
775:
774:
773:
770:
768:
765:
761:
758:
756:
753:
752:
751:
748:
744:
741:
740:
739:
736:
735:
733:
729:
725:
718:
713:
711:
706:
704:
699:
698:
695:
691:
681:
677:
673:
666:
663:
659:
651:
649:9781491933657
645:
641:
640:
632:
629:
621:
618:Eric Brewer.
614:
611:
606:
602:
598:
591:
588:
583:
579:
575:
571:
567:
563:
559:
555:
551:
544:
542:
540:
536:
525:
521:
514:
512:
508:
496:
492:
485:
482:
470:
466:
462:
458:
454:
450:
445:
440:
436:
429:
426:
414:
413:This long run
410:
403:
400:
395:
389:
385:
378:
375:
370:
364:
360:
353:
350:
346:. 2010-02-14.
345:
341:
335:
332:
328:. 2009-01-11.
327:
323:
317:
314:
309:
305:
301:
297:
293:
289:
285:
281:
274:
272:
270:
266:
259:
255:
252:
250:
247:
245:
242:
240:
237:
235:
232:
230:
227:
224:
221:
219:
216:
215:
211:
209:
207:
202:
198:
196:
190:
188:
184:
180:
176:
172:
168:
164:
160:
152:
150:
148:
144:
140:
136:
132:
127:
124:
122:
114:
112:
110:
107:
98:
91:
87:
84:
83:
82:
80:
72:
70:
67:
64:
59:
57:
54:
51:
49:
46:
45:
44:
42:
38:
34:
30:
27:, also named
26:
22:
873:
689:
665:
653:
638:
631:
613:
596:
590:
557:
553:
527:. Retrieved
524:DBMS Musings
523:
498:. Retrieved
494:
484:
472:. Retrieved
428:
416:. Retrieved
412:
402:
383:
377:
358:
352:
343:
334:
325:
316:
283:
279:
203:
199:
191:
175:Seth Gilbert
156:
128:
125:
121:availability
118:
103:
76:
56:Availability
43:guarantees:
28:
24:
18:
1173:WikiProject
1064:Replication
952:Transaction
894:Foreign key
874:CAP theorem
821:Multi-model
500:24 November
474:24 November
179:Nancy Lynch
159:Eric Brewer
139:consistency
115:Explanation
48:Consistency
33:Eric Brewer
25:CAP theorem
1188:Categories
1038:Query plan
991:Components
909:Unique key
826:comparison
760:comparison
750:Relational
743:comparison
529:2018-01-23
444:1509.05393
418:1 February
344:royans.net
260:References
225:(solution)
167:conjecture
1047:Functions
982:Partition
809:In-memory
767:Key–value
680:1813/7235
574:0018-9162
300:0163-5700
1153:Category
1069:Sharding
925:Relation
899:Superkey
854:Database
847:Concepts
554:Computer
308:15892169
254:Trilemma
212:See also
1163:Outline
962:Trigger
918:Objects
469:1991487
449:Bibcode
187:theorem
161:of the
153:History
137:choose
77:When a
977:Cursor
935:column
804:NewSQL
656:
646:
582:890105
580:
572:
467:
390:
365:
306:
298:
23:, the
967:Index
930:table
833:Cloud
799:NoSQL
794:Graph
731:Types
623:(PDF)
578:S2CID
465:S2CID
439:arXiv
304:S2CID
147:NoSQL
135:RDBMS
1018:ODBC
1008:JDBC
947:View
884:Null
879:CRUD
859:ACID
814:list
777:list
755:list
644:ISBN
570:ISSN
502:2019
476:2019
420:2019
388:ISBN
363:ISBN
296:ISSN
204:The
195:ACID
177:and
143:BASE
131:ACID
106:ACID
1013:XQJ
940:row
676:hdl
601:doi
562:doi
457:doi
288:doi
183:MIT
181:of
19:In
1190::
674:.
652:.
576:.
568:.
558:45
556:.
552:.
538:^
522:.
510:^
493:.
463:.
455:.
447:.
411:.
342:.
324:.
302:.
294:.
284:33
282:.
268:^
197:.
189:.
111:.
716:e
709:t
702:v
682:.
678::
625:.
607:.
603::
584:.
564::
532:.
504:.
478:.
459::
451::
441::
422:.
396:.
371:.
310:.
290::
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.