A simple deterministic algorithm for guaranteeing the forward progress of transactions

A simple deterministic algorithm for guaranteeing the forward progress of transactions

This paper describes a remarkably simple deterministic (not probabilistic) contention-management algorithm for guaranteeing the forward progress of transactions - avoiding deadlocks, livelocks, and other anomalies. The transactions must be finite (no infinite loops), but on each restart, a transacti...

Full description

Bibliographic Details
Main Author:	Leiserson, Charles E
Other Authors:	Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory
Format:	Article
Published:	Elsevier 2018
Online Access:	http://hdl.handle.net/1721.1/114871 https://orcid.org/0000-0001-6386-5552

Similar Items

Transactions Everywhere
by: Kuszmaul, Bradley C., et al.
Published: (2003)

Deterministic and Randomized Actuator Scheduling With Guaranteed Performance Bounds
by: Siami, Milad, et al.
Published: (2023)

Simple deterministic wildcard matching
by: Clifford, P, et al.
Published: (2007)

Hardware Transactional Memory
by: Lie, Sean, et al.
Published: (2003)

Progressive equilibration algorithms : the case of linear transaction costs
Published: (2004)

Deterministic parallel random-number generation for dynamic-multithreading platforms
by: Leiserson, Charles E., et al.
Published: (2016)

LiTM: A Lightweight Deterministic Software Transactional Memory System
by: Xia, Yu, et al.
Published: (2021)

Deep deterministic uncertainty: a new simple baseline
by: Mukhoti, J, et al.
Published: (2023)

Executing dynamic data-graph computations deterministically using chromatic scheduling
by: Leiserson, Charles E., et al.
Published: (2016)

Forward/progress
by: Chan, Wesley Jie Sheng
Published: (2019)

Forward/progress
by: Yoon, Nicholas Joo Kuang
Published: (2019)

Executing Dynamic Data-Graph Computations Deterministically Using Chromatic Scheduling
by: Kaler, Timothy, et al.
Published: (2018)

Deterministic algorithms for the Lovász Local Lemma
by: Haeupler, Bernhard
Published: (2010)

Deterministic Algorithms for the Lovász Local Lemma
by: Chandrasekaran, Karthekeyan, et al.
Published: (2014)

ProSecCo: progressive sequence mining with convergence guarantees
by: Servan-Schreiber, Sacha, et al.
Published: (2021)

Adaptive Finite Element Simulation of Currents at Microelectrodes to Guaranteed Accuracy: Application to a Simple Model Problem
by: Harriman, K, et al.
Published: (2000)

Efficient scheduling algorithms for quality-of-service guarantees in the Internet
by: Kam, Anthony C. (Anthony Chi-Kong)
Published: (2005)

STABLE GENERALIZED PREDICTIVE CONTROL - AN ALGORITHM WITH GUARANTEED STABILITY
by: Kouvaritakis, B, et al.
Published: (1992)

A Survey of Algorithms for Integrating Wafer-scale Systolic Arrays
by: Leighton, Tom, et al.
Published: (2023)

Distributed asynchronous deterministic and stochastic gradient optimization algorithms
Published: (2002)

Parallel and Deterministic Algorithms for MRFs: Surface Reconstruction and Integration
by: Geiger, Davi, et al.
Published: (2004)

Adaptative finite element simulation of currents at microelectrodes to a guaranteed accuracy. Application to a simple model problem
by: Harriman, K, et al.
Published: (2000)

Communication-efficient Parallel Graph Algorithms
by: Leiserson, Charles E., et al.
Published: (2023)

A Space-efficient Algorithm for Finding the Connected Components of Rectangles in the Plane
by: Leiserson, Charles E., et al.
Published: (2023)

Sampling-Based Approximation Algorithms for Reachability Analysis with Provable Guarantees
by: Liebenwein, Lucas, et al.
Published: (2018)

Consistency Guarantees for Greedy Permutation-Based Causal Inference Algorithms
by: Solus, L, et al.
Published: (2022)

QoS guaranteed resource block allocation algorithm in LTE downlink
by: Zhao, Liqun, et al.
Published: (2013)

A greedy, deterministic sampling-based path planning algorithm for AGV
by: Liu, Zhenqi
Published: (2024)

Nearly optimal deterministic algorithm for sparse Walsh-Hadamard transform
by: Cheraghchi, Mahdi, et al.
Published: (2018)

Location determination using radio frequency RSSI and deterministic algorithm
by: Hussin, A.G., et al.
Published: (2008)

Evaluation of deterministic and statistical failure detection algorithms for aircraft applications
by: Nusawardhana, 1969-
Published: (2009)

A work-efficient parallel breadth-first search algorithm (or how to cope with the nondeterminism of reducers)
by: Leiserson, Charles E., et al.
Published: (2016)

Deterministic Chance
by: Eagle, A
Published: (2011)

Is the Universe deterministic?
by: Vedral, V
Published: (2006)

A deterministic approximation algorithm for computing the permanent of a 0, 1 matrix
by: Gamarnik, David, et al.
Published: (2017)

Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size
by: Moitra, Ankur
Published: (2010)

Outlier-Robust Spatial Perception: Hardness, General-Purpose Algorithms, and Guarantees
by: Tzoumas, Vasileios, et al.
Published: (2021)

NUMERICAL ROBUSTNESS AND EFFICIENCY OF GENERALIZED PREDICTIVE CONTROL ALGORITHMS WITH GUARANTEED STABILITY
by: Rossiter, J, et al.
Published: (1994)

An adaptive algorithm for online time series segmentation with error bound guarantee
by: Xu, Z, et al.
Published: (2012)

Computationally efficient algorithms for constraint handling with guaranteed stability and near optimality
by: Rossiter, J, et al.
Published: (2001)