article

Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services

Authors:

Seth Gilbert,

Nancy LynchAuthors Info & Claims

ACM SIGACT News, Volume 33, Issue 2

Pages 51 - 59

https://doi.org/10.1145/564585.564601

Published: 01 June 2002 Publication History

Get Access

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.

References

[1]

Hagit Attiya, Amotz Bar-Noy, Danny Dolev, Daphne Koller, David Peleg, and Rüdiger Reischuk. Achievable cases in an asynchronous environment. In 28th Annual Symposium on Foundations of Computer Science, pages 337-346, Los Angeles, California, October 1987.

Digital Library

Google Scholar

[2]

Eric A. Brewer. Towards robust distributed systems. (Invited Talk) Principles of Distributed Computing, Portland, Oregon, July 2000.

Digital Library

Google Scholar

[3]

Maurice P. Herlihy and Jeannette M. Wing. Linearizability: A correctness condition for concurrent objects. ACM Transactions on Programming Languages and Systems, 12(3):463-492, July 1990.

Digital Library

Google Scholar

[4]

Leslie Lamport. On interprocess communication --- parts I and II. Distributed Computing, 1(2):77-101, April 1986.

Crossref

Google Scholar

[5]

Nancy Lynch. Distributed Algorithms. Morgan Kaufman, 1996.

Digital Library

Google Scholar

Cited By

View all

Johansson BPourvatan BMoezkarimi ZPapadopoulos ASirjani M(2024)Formal Verification of Consistency for Systems with Redundant ControllersElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.399.8399(169-191)Online publication date: 27-Mar-2024
https://doi.org/10.4204/EPTCS.399.8
Camilleri CVella JNezval V(2024)Horizontally Scalable Implementation of a Distributed DBMS Delivering Causal Consistency via the Actor ModelElectronics10.3390/electronics1317336713:17(3367)Online publication date: 24-Aug-2024
https://doi.org/10.3390/electronics13173367
Ni ZYou JLi Y(2024)An ICN-Based On-Path Computing Resource Scheduling Architecture with User Preference Awareness for Computing NetworkElectronics10.3390/electronics1305093313:5(933)Online publication date: 29-Feb-2024
https://doi.org/10.3390/electronics13050933
Show More Cited By

Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services
1. Software and its engineering
  1. Software organization and properties
    1. Software system structures

Recommendations

AUTOMATIC REPLICATION FOR HIGHLY AVAILABLE SERVICES
Using Paxos to build a scalable, consistent, and highly available datastore

Spinnaker is an experimental datastore that is designed to run on a large cluster of commodity servers in a single datacenter. It features key-based range partitioning, 3-way replication, and a transactional get-put API with the option to choose either ...
Local Recovery for High Availability in Strongly Consistent Cloud Services

Emerging cloud-based network services must deliver both good performance and high availability. Achieving both of these goals requires content replication across multiple sites. Many cloud-based services either require or would benefit from the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ACM SIGACT News Volume 33, Issue 2

June 2002

79 pages

ISSN:0163-5700

DOI:10.1145/564585

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 2002

Published in SIGACT Volume 33, Issue 2

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1,047
Total Citations
View Citations
11,610
Total Downloads

Downloads (Last 12 months)496
Downloads (Last 6 weeks)63

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Johansson BPourvatan BMoezkarimi ZPapadopoulos ASirjani M(2024)Formal Verification of Consistency for Systems with Redundant ControllersElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.399.8399(169-191)Online publication date: 27-Mar-2024
https://doi.org/10.4204/EPTCS.399.8
Camilleri CVella JNezval V(2024)Horizontally Scalable Implementation of a Distributed DBMS Delivering Causal Consistency via the Actor ModelElectronics10.3390/electronics1317336713:17(3367)Online publication date: 24-Aug-2024
https://doi.org/10.3390/electronics13173367
Ni ZYou JLi Y(2024)An ICN-Based On-Path Computing Resource Scheduling Architecture with User Preference Awareness for Computing NetworkElectronics10.3390/electronics1305093313:5(933)Online publication date: 29-Feb-2024
https://doi.org/10.3390/electronics13050933
Li TWan ZWu B(2024)Blockchains: Fusing Platform Functionalities Under the CAP TradeoffSSRN Electronic Journal10.2139/ssrn.4748826Online publication date: 2024
https://doi.org/10.2139/ssrn.4748826
Alsheikh RFadel EAkkari N(2024)Distributed Software-Defined Networking ManagementARO-THE SCIENTIFIC JOURNAL OF KOYA UNIVERSITY10.14500/aro.1146812:2(157-166)Online publication date: 30-Sep-2024
https://doi.org/10.14500/aro.11468
Almeida P(2024)Approaches to Conflict-free Replicated Data TypesACM Computing Surveys10.1145/369524957:2(1-36)Online publication date: 9-Sep-2024
https://dl.acm.org/doi/10.1145/3695249
D'Amato FLosa GZanolini LKuznetsov PGelles ROlivetti D(2024)Asynchrony-Resilient Sleepy Total-Order Broadcast ProtocolsProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662779(247-256)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662779
Geng CBlanas SBond MWang Y(2024)IsoPredict: Dynamic Predictive Analysis for Detecting Unserializable Behaviors in Weakly Isolated Data Store ApplicationsProceedings of the ACM on Programming Languages10.1145/36563918:PLDI(343-367)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656391
Liu SMultazzu LWei HBasin D(2024)NOC-NOC: Towards Performance-optimal Distributed TransactionsProceedings of the ACM on Management of Data10.1145/36392642:1(1-25)Online publication date: 26-Mar-2024
https://dl.acm.org/doi/10.1145/3639264
Wang HLi HSmahi AXiao MLi S(2024)GBT-CHAIN: A System Framework for Solving the General Trilemma in Permissioned BlockchainsDistributed Ledger Technologies: Research and Practice10.1145/36158713:2(1-15)Online publication date: 18-Jun-2024
https://dl.acm.org/doi/10.1145/3615871
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Recommendations

AUTOMATIC REPLICATION FOR HIGHLY AVAILABLE SERVICES

Using Paxos to build a scalable, consistent, and highly available datastore

Local Recovery for High Availability in Strongly Consistent Cloud Services