The DOI matches its Crossref record.
Axioms for concurrent objects
Open accessAbstract
Specification and verification techniques for abstract data types that have been successful for sequential programs can be extended in a natural way to provide the same benefits for concurrent programs. We propose an approach to specifying and verifying concurrent objects based on a novel correctness condition, which we call “linearizability.” Linearizability provides the illusion that each operation takes effect instantaneously at some point between its invocation and its response, implying that the meaning of a concurrent object's operations can still be given by pre- and post-conditions. In this paper, we will define and discuss linearizability, and then give examples of how to reason about concurrent objects and verify their implementations based on their (sequential) axiomatic specifications.
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
Cited by
Practical Byzantine fault tolerance
Castro, M., & Liskov, B. H. (1999) · Operating Systems Design and Implementation · doi:10.5555/296806.296824 · Cited by 3,205
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
Self-citationPractical byzantine fault tolerance and proactive recovery
Castro, M., & Liskov, B. (2002) · ACM Transactions on Computer Systems · doi:10.1145/571637.571640 · Cited by 2,475
Simple, fast, and practical non-blocking and blocking concurrent queue algorithms
Michael, M. M., & Scott, M. L. (1996) · Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing - PODC '96 · doi:10.1145/248052.248106 · Cited by 802
Secure routing for structured peer-to-peer overlay networks
Castro, M., Druschel, P., Ganesh, A., Rowstron, A., & Wallach, D. S. (2002) · ACM SIGOPS Operating Systems Review · doi:10.1145/844128.844156 · Cited by 743
The existence of refinement mappings
Abadi, M., & Lamport, L. (1991) · Theoretical Computer Science · doi:10.1016/0304-3975(91)90224-p · Cited by 737
HQ replication: a hybrid quorum protocol for byzantine fault tolerance
Cowling, J. A., Myers, D. S., Liskov, B. H., Rodrigues, R., & Shrira, L. (2006) · doi:10.5555/1298455.1298473 · Cited by 297
Metadata
- Authors
- Herlihy, M. P., & Wing, J. M.
- Venue
- Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages - POPL '87
- Publisher
- ACM Press
- Published
- 1987
- Pages
- 13-26
- OpenAlex
- W2015121269
- Cited by
- 173
- References
- 0
- FWCI
- 9.21
- Type
- conference paper
- Language
- en
- Open access
- green
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.