The DOI matches its Crossref record; 4 of the 4 references it cites were found in a registry or an index.
Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services
Abstract
When designing distributed web services, there are three properties that are commonly desired: consistency, availability, and partition tolerance. It is impossible to achieve all three. In this note, we prove this conjecture in the asynchronous network model, and then discuss solutions to this dilemma in the partially synchronous model.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
(1992) · Lecture Notes in Computer Science · doi:10.1007/bfb0022433 · Cited by 3,955
Linearizability: a correctness condition for concurrent objects
Herlihy, M. P., & Wing, J. M. (1990) · ACM Transactions on Programming Languages and Systems · doi:10.1145/78969.78972 · Cited by 3,176
On interprocess communication: Part I: Basic formalism
Lamport, L. (1986) · Distributed Computing · doi:10.1007/bf01786227 · Cited by 861
Towards robust distributed systems (abstract)
Brewer, E. A. (2000) · Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing · doi:10.1145/343477.343502 · Cited by 809
Cited by
Benchmarking cloud serving systems with YCSB
Cooper, B. F., Silberstein, A., Tam, E., Ramakrishnan, R., & Sears, R. (2010) · Proceedings of the 1st ACM symposium on Cloud computing · doi:10.1145/1807128.1807152 · Cited by 3,716
Chen, M., Mao, S., & Liu, Y. (2014) · Mobile Networks and Applications · doi:10.1007/s11036-013-0489-0 · Cited by 2,913
A Secure Sharding Protocol For Open Blockchains
Luu, L., Narayanan, V., Zheng, C., Baweja, K., Gilbert, S., & Saxena, P. (2016) · Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/2976749.2978389 · Cited by 1,428
Self-citationScalable SQL and NoSQL data stores
Cattell, R. (2011) · ACM SIGMOD Record · doi:10.1145/1978915.1978919 · Cited by 1,358
Toward Scalable Systems for Big Data Analytics: A Technology Tutorial
Hu, H., Wen, Y., Chua, T.-S., & Li, X. (2014) · IEEE Access · doi:10.1109/access.2014.2332453 · Cited by 1,099
The Quest for Scalable Blockchain Fabric: Proof-of-Work vs. BFT Replication
Vukolić, M. (2016) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-39028-4_9 · Cited by 1,051
“Distributed consensus, infamous for its limited scalability, was for decades perceived as a synchronization primitive that is to be used only in applications in desperate need of consistency and only among few nodes (see e.g., [8, 28]).”
Vogels, W. (2009) · Communications of the ACM · doi:10.1145/1435417.1435432 · Cited by 1,013
Security and Privacy on Blockchain
Zhang, R., Xue, R., & Liu, L. (2020) · ACM Computing Surveys · doi:10.1145/3316481 · Cited by 959
CloudCmp: comparing public cloud providers
Li, A., Yang, X., Kandula, S., & Zhang, M. (2010) · Proceedings of the 10th ACM SIGCOMM conference on Internet measurement · doi:10.1145/1879141.1879143 · Cited by 882
Conflict-Free Replicated Data Types
Shapiro, M., Preguiça, N., Baquero, C., & Zawirski, M. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-24550-3_29 · Cited by 736
Solutions to scalability of blockchain: a survey
Zhou, Q., Huang, H., Zheng, Z., & Bian, J. (2020) · IEEE Access · doi:10.1109/access.2020.2967218 · Cited by 689
Don't settle for eventual: scalable causal consistency for wide-area storage with COPS
Lloyd, W., Freedman, M. J., Kaminsky, M., & Andersen, D. G. (2011) · Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles · doi:10.1145/2043556.2043593 · Cited by 565
Calvin: fast distributed transactions for partitioned database systems
Thomson, A., Diamond, T., Weng, S.-C., Ren, K., Shao, P., & Abadi, D. J. (2012) · Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data · doi:10.1145/2213836.2213838 · Cited by 533
(2010) · Springer eBooks · doi:10.1007/978-1-4419-6524-0 · Cited by 519
Peer-to-peer support for massively multiplayer games
Knutsson, B., Lu, H., Xu, W., & Hopkins, B. (2004) · IEEE INFOCOM 2004 · doi:10.1109/infcom.2004.1354485 · Cited by 501
On scalability of software-defined networking
Yeganeh, S. H., Tootoonchian, A., & Ganjali, Y. (2013) · IEEE Communications Magazine · doi:10.1109/mcom.2013.6461198 · Cited by 500
A Vademecum on Blockchain Technologies: When, Which, and How
Belotti, M., Bozic, N., Pujolle, G., & Secci, S. (2019) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2019.2928178 · Cited by 498
Context-Aware Computing, Learning, and Big Data in Internet of Things: A Survey
Sezer, O. B., Dogdu, E., & Ozbayoglu, A. M. (2018) · IEEE Internet of Things Journal · doi:10.1109/jiot.2017.2773600 · Cited by 453
Data-intensive text processing with MapReduce
Lin, J., & Dyer, C. (2009) · Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics, Companion Volume: Tutorial Abstracts on - NAACL '09 · doi:10.3115/1620950.1620951 · Cited by 445
A Survey of Large Scale Data Management Approaches in Cloud Environments
Sakr, S., Liu, A., Batista, D. M., & Alomari, M. (2011) · IEEE Communications Surveys & Tutorials · doi:10.1109/surv.2011.032211.00087 · Cited by 424
Pbft Vs Proof-Of-Authority: Applying The Cap Theorem To Permissioned Blockchain
Angelis, S. D., Aniello, L., Baldoni, R., Lombardi, F., Margheri, A., & Vladimiro Sassone, C. (2017) · ePrints Soton (University of Southampton) · doi:10.5281/zenodo.1169272 · Cited by 394
Transactional storage for geo-replicated systems
Sovran, Y., Power, R., Aguilera, M. K., & Li, J. (2011) · Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles · doi:10.1145/2043556.2043592 · Cited by 390
Analysis of the main consensus protocols of blockchain
Zhang, S., & Lee, J.-H. (2020) · ICT Express · doi:10.1016/j.icte.2019.08.001 · Cited by 383
On Patterns for Decentralized Control in Self-Adaptive Systems
Weyns, D., Schmerl, B., Grassi, V., Malek, S., Mirandola, R., Prehofer, C., Wuttke, J., Andersson, J., Giese, H., & Göschka, K. M. (2013) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-35813-5_4 · Cited by 370
When things matter: A survey on data-centric internet of things
Qin, Y., Sheng, Q. Z., Falkner, N. J. G., Dustdar, S., Wang, H., & Vasilakos, A. V. (2016) · Journal of Network and Computer Applications · doi:10.1016/j.jnca.2015.12.016 · Cited by 331
Data management in cloud environments: NoSQL and NewSQL data stores
Grolinger, K., Higashino, W. A., Tiwari, A., & Capretz, M. A. (2013) · Journal of Cloud Computing: Advances, Systems and Applications · doi:10.1186/2192-113x-2-22 · Cited by 318
Amazon Aurora: Design Considerations for High Throughput Cloud-Native Relational Databases
Verbitski, A., Gupta, A., Saha, D., Brahmadesam, M., Gupta, K., Mittal, R., Krishnamurthy, S., Maurice, S., Kharatishvili, T., & Bao, X. (2017) · Proceedings of the 2017 ACM International Conference on Management of Data · doi:10.1145/3035918.3056101 · Cited by 290
Brantner, M., Florescu, D., Graf, D., Kossmann, D., & Kraska, T. (2008) · Proceedings of the 2008 ACM SIGMOD international conference on Management of data · doi:10.1145/1376616.1376645 · Cited by 259
Survey of Vector Database Management Systems
Pan, J. J., Wang, J., & Li, G. (2023) · arXiv · doi:10.48550/arxiv.2310.14021 · Cited by 184
eHealth integrity model based on permissioned blockchain
Hyla, T., & Pejaś, J. (2019) · Future Internet · doi:10.3390/fi11030076 · Cited by 49
“However, according to analysis using the CAP theorem [34] carried out by De Angelis et al.”
MethodA survey of structured P2P systems for RDF data storage and retrieval
Filali, I., Bongiovanni, F., Huet, F., & Baude, F. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-23074-5_2 · Cited by 19
Want to scale in centralized systems? Think P2P
Kermarrec, A.-M., & Taïani, F. (2015) · Journal of Internet Services and Applications · doi:10.1186/s13174-015-0029-1 · Cited by 18
“…are very likely to execute increasingly on multiple data centers, at a global scale, while taking into account scalability, performance, and the inherent limitations of the FLP (Fischer, Lynch, Paterson) [29] and CAP (Consistency, Availability, and Partition Tolerance) [30] impossibility results.”
BackgroundComputing Education Research Today
Fincher, S. A., Tenenberg, J., Dorn, B., Hundhausen, C., McCartney, R., & Murphy, L. (2019) · The Cambridge Handbook of Computing Education Research · doi:10.1017/9781108654555.003 · Cited by 7
ACID Encountering the CAP Theorem: Two Bank Case Studies
Kong, C., Gao, M., Qian, W., Zhou, M., Gong, X., Zhang, R., & Zhou, A. (2015) · 2015 12th Web Information System and Application Conference (WISA) · doi:10.1109/wisa.2015.63 · Cited by 4
Metadata
- Authors
- Gilbert, S., & Lynch, N.
- Venue
- ACM SIGACT News
- Published
- 2002-06
- Volume
- 33
- Issue
- 2
- Pages
- 51-59
- ISSN
- 0163-5700 (ISSN-L)
- OpenAlex
- W2054584570
- Cited by
- 1,727
- References
- 4
- FWCI
- 6.79
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.