The DOI matches its Crossref record; 37 of the 37 references it cites were found in a registry or an index.
Design and evaluation of a conit-based continuous consistency model for replicated services
Abstract
The tradeoffs between consistency, performance, and availability are well understood. Traditionally, however, designers of replicated systems have been forced to choose from either strong consistency guarantees or none at all. This paper explores the semantic space between traditional strong and optimistic consistency models for replicated services. We argue that an important class of applications can tolerate relaxed consistency, but benefit from bounding the maximum rate of inconsistent access in an application-specific manner. Thus, we develop a conit-based continuous consistency model to capture the consistency spectrum using three application-independent metrics, numerical error , order error , and staleness . We then present the design and implementation of TACT, a middleware layer that enforces arbitrary consistency bounds among replicas using these metrics. We argue that the TACT consistency model can simultaneously achieve the often conflicting goals of generality and practicality by describing how a broad range of applications can express their consistency semantics using TACT and by demonstrating that application-independent algorithms can efficiently enforce target consistency levels. Finally, we show that three replicated applications running across the Internet demonstrate significant semantic and performance benefits from using our framework.
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
Computer Architecture: A Quantitative Approach
Hennessy, J. L., & Patterson, D. A. (1989) · UCLA - Biblioteca de Ciencias y Tecnologia Felix Morales Bueno · Cited by 9,375
Time, clocks, and the ordering of events in a distributed system
Lamport, L. (1978) · Communications of the ACM · doi:10.1145/359545.359563 · Cited by 8,488
A relational model of data for large shared data banks
Codd, E. F. (1970) · Communications of the ACM · doi:10.1145/362384.362685 · Cited by 5,547
Computer architecture: a quantitative approach
Shute, M. (1993) · Microelectronics Journal · doi:10.1016/0026-2692(93)90111-q · Cited by 3,336
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
Hypertext Transfer Protocol (HTTP)
(2003) · The Hacker's Handbook · doi:10.1201/9780203490044-20 · Cited by 2,824
Implementing fault-tolerant services using the state machine approach: a tutorial
Schneider, F. B. (1990) · ACM Computing Surveys · doi:10.1145/98163.98167 · Cited by 2,387
A Relational Model of Data for Large Shared Data Banks
Codd, E. F. (2002) · Software Pioneers · doi:10.1007/978-3-642-59412-0_16 · Cited by 1,177
Disconnected operation in the Coda File System
Kistler, J. J., & Satyanarayanan, M. (1992) · ACM Transactions on Computer Systems · doi:10.1145/146941.146942 · Cited by 1,065
Computer Architecture: A Quantitative Approach, 2nd Edition
Hennessy, J. L., & Patterson, D. A. (1996) · Cited by 1,015
Extensibility safety and performance in the SPIN operating system
Bershad, B. N., Savage, S., Pardyak, P., Sirer, E. G., Fiuczynski, M. E., Becker, D., Chambers, C., & Eggers, S. (1995) · Proceedings of the fifteenth ACM symposium on Operating systems principles - SOSP '95 · doi:10.1145/224056.224077 · Cited by 955
Hellerstein, J. M., Haas, P. J., & Wang, H. J. (1997) · Proceedings - ACM-SIGMOD International Conference on Management of Data · doi:10.1145/253260.253291 · Cited by 902
Computer architecture (2nd ed.): a quantitative approach
Hennessy, J. L., & Patterson, D. A. (1996) · Morgan Kaufmann Publishers Inc. eBooks · Cited by 876
The process group approach to reliable distributed computing
Birman, K. P. (1993) · Communications of the ACM · doi:10.1145/163298.163303 · Cited by 729
Consistency in a partitioned network: a survey
Davidson, S. B., Garcia-Molina, H., & Skeen, D. (1985) · ACM Computing Surveys · doi:10.1145/5505.5508 · Cited by 550
Locality-aware request distribution in cluster-based network servers
Pai, V. S., Aron, M., Banga, G., Svendsen, M. S., Druschel, P., Willy Zwaenepoel, Y., & Nahum, E. (1998) · ACM SIGPLAN Notices · doi:10.1145/291006.291048 · Cited by 505
Flexible update propagation for weakly consistent replication
Petersen, K., Spreitzer, M. J., Terry, D. B., Theimer, M. M., & Demers, A. J. (1997) · Proceedings of the sixteenth ACM symposium on Operating systems principles · doi:10.1145/268998.266711 · Cited by 475
Session guarantees for weakly consistent replicated data
Terry, D., Demers, A. J., Petersen, K., Spreitzer, M., Theimer, M. M., & Welch, B. B. (2002) · International Conference on Parallel and Distributed Information Systems · doi:10.1109/pdis.1994.331722 · Cited by 430
Providing high availability using lazy replication
Ladin, R., Liskov, B. H., Shrira, L., & Ghemawat, S. (1992) · ACM Transactions on Computer Systems · doi:10.1145/138873.138877 · Cited by 383
Managing update conflicts in Bayou, a weakly connected replicated storage system
Terry, D. B., Theimer, M. M., Petersen, K., Demers, A. J., Spreitzer, M. J., & Hauser, C. H. (1995) · ACM SIGOPS Operating Systems Review · doi:10.1145/224057.224070 · Cited by 339
Data caching issues in an information retrieval system
Alonso, R. D. H., Barbará, D., & García-Molina, H. (1990) · ACM Transactions on Database Systems · doi:10.1145/88636.87848 · Cited by 319
Application performance and flexibility on exokernel systems
Kaashoek, M. F., Engler, D. R., Ganger, G. R., Briceño, H. M., Hunt, R., Mazières, D., Pinckney, T., Grimm, R., Jannotti, J., & Mackenzie, K. (1997) · Proceedings of the sixteenth ACM symposium on Operating systems principles · doi:10.1145/268998.266644 · Cited by 289
Replica control in distributed systems: as asynchronous approach
Pu, C., & Leff, A. (1991) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/115790.115856 · Cited by 194
Semantics-based concurrency control: beyond commutativity
Badrinath, B. R., & Ramamritham, K. (1992) · ACM Transactions on Database Systems · doi:10.1145/128765.128771 · Cited by 177
Generalized isolation level definitions
Adya, A., Liskov, B., & O'Neil, P. (2002) · Proceedings of 16th International Conference on Data Engineering (Cat. No.00CB37073) · doi:10.1109/icde.2000.839388 · Cited by 176
Read-only transactions in a distributed database
García-Molina, H., & Wiederhold, G. C. M. (1982) · ACM Transactions on Database Systems · doi:10.1145/319702.319704 · Cited by 174
Efficient optimistic concurrency control using loosely synchronized clocks
Adya, A., Gruber, R., Liskov, B., & Maheshwari, U. (1995) · Proceedings of the 1995 ACM SIGMOD international conference on Management of data - SIGMOD '95 · doi:10.1145/223784.223787 · Cited by 169
Weak-consistency group communication and membership
Golding, R. A. (1992) · Cited by 132
SSP: A semantics-based protocol for real-time data access
Kuo, T., & Mok, A. K. (2002) · IEEE Real-Time Systems Symposium (RTSS) · doi:10.1109/real.1993.393513 · Cited by 113
Saitō, Y., Bershad, B. N., & Levy, H. M. (1999) · doi:10.1145/319151.319152 · Cited by 103
Timed consistency for shared distributed objects
Torres-Rojas, F. J., Ahamad, M., & Raynal, M. (1999) · ACM Symposium on Principles of Distributed Computing (PODC) · doi:10.1145/301308.301350 · Cited by 92
Plausible clocks: constant size logical clocks for distributed systems
Torres-Rojas, F. J., & Ahamad, M. (1999) · Distributed Computing · doi:10.1007/s004460050065 · Cited by 85
Software write detection for a distributed shared memory
Zekauskas, M. J., Sawdon, W., & Bershad, B. N. (1994) · doi:10.5555/1267638.1267646 · Cited by 75
Bounded ignorance: a technique for increasing concurrency in a replicated system
Krishnakumar, N., & Bernstein, A. J. (1994) · ACM Transactions on Database Systems · doi:10.1145/195664.195670 · Cited by 65
A WEAK-CONSISTENCY ARCHITECTURE FOR DISTRIBUTED INFORMATION SERVICES
Golding, R. A. (1992) · Cited by 62
Consistency and orderability: semantics-based correctness criteria for databases
Agrawal, D., Abbadi, A. E., & Singh, A. K. (1993) · ACM Transactions on Database Systems · doi:10.1145/155271.155276 · Cited by 57
Noble, B. D., Fleis, B., & Kim, M. (1999) · Cited by 16
Cited by
A Survey on Distributed Machine Learning
Verbraeken, J., Wolting, M., Katzy, J., Kloppenburg, J., Verbelen, T., & Rellermeyer, J. S. (2021) · ACM Computing Surveys · doi:10.1145/3377454 · Cited by 872
A low-bandwidth network file system
Muthitacharoen, A., Chen, B., & Mazières, D. (2001) · Proceedings of the eighteenth ACM symposium on Operating systems principles · doi:10.1145/502034.502052 · Cited by 784
Saito, Y., & Shapiro, M. (2005) · ACM Computing Surveys · doi:10.1145/1057977.1057980 · Cited by 739
More Effective Distributed ML via a Stale Synchronous Parallel Parameter Server
Ho, Q., Cipar, J., Cui, H., Kim, J. K., Lee, S., Gibbons, P. B., Gibson, G. A., Ganger, G. R., & Xing, E. P. (2013) · PubMed · doi:10.1184/r1/6475898 · Cited by 506
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
Metadata
- Authors
- Yu, H., & Vahdat, A.
- Venue
- ACM Transactions on Computer Systems
- Published
- 2002-08
- Volume
- 20
- Issue
- 3
- Pages
- 239-282
- ISSN
- 0734-2071 (ISSN-L)
- 1557-7333
- OpenAlex
- W2115806861
- Cited by
- 289
- References
- 37
- FWCI
- 22.36
- 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.