ComputingComputer ScienceComputer SystemsData StructuresDistributed SystemsFormal MethodsConcurrency AnalysisConcurrency ControlConcurrent ProgrammingData SynchronizationTransaction ManagementTransaction Processing SystemsFine-grained SynchronizationGranularityLinearizabilityTransaction ProcessingTransactional SynchronizationTransactions
We describe a methodology for transforming a large class of highly-concurrent linearizable objects into highly-concurrent transactional objects. As long as the linearizable implementation satisfies certain regularity properties (informally, that every method has an inverse), we define a simple wrapper for the linearizable implementation that guarantees that concurrent transactions without inherent conflicts can synchronize at the same granularity as the original linearizable implementation.
37
V. J. Rayward‐Smith, Thomas H. Cormen, Charles E. Leiserson et al. · Journal of the Operational Research Society · 1991 · 17K citations
Maurice Herlihy, J. Eliot B. Moss · 1993 · 2.2K citations
Nir Shavit, Dan Touitou · 1995 · 1.2K citations · Full text
Skip lists: a probabilistic alternative to balanced trees
William Pugh · Communications of the ACM · 1990 · 1.2K citations · Full text