Is distributed locking harder?
type: Item
instance of: scholarly article
title: Is distributed locking harder?
zbMATH Open document ID: 0571.68083
DOI: 10.1016/0022-0000(84)90078-3
author: Paris C. Kanellakis
author: Christos Papadimitriou
published in: Journal of Computer and System Sciences
publication date: 1984-01-01T00:00:00Z
review text: The problem of determining whether a set of locked transactions, accessing a distributed database, is guaranteed to produce only serializable schedules is examined. For a pair of transactions, with n steps, it is proved that this concurrency control problem, which is polynomially solvable for centralized databases, is in general coNP- complete. A new graph-theoretic technique is employed and an \(O(n^ 2)\) test for the special case of databases distributed between two sites is provided.
Mathematics Subject Classification ID: 68P20
Mathematics Subject Classification ID: 68M20
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 3911758
zbMATH Keywords: locked transactions
zbMATH Keywords: distributed database
zbMATH Keywords: serializable schedules
zbMATH Keywords: concurrency control
zbMATH Keywords: coNP-complete
zbMATH Keywords: graph-theoretic technique
describes a project that uses: INGRES
MaRDI profile type: Publication
full work available at URL: 0022-0000(84)90078-3
OpenAlex ID: W1963591123
cites work: The notions of consistency and predicate locks in a database system
cites work: A fast algorithm for testing for safety and detecting deadlocks in locked transaction systems
cites work: A locking protocol for resource coordination in distributed databases
cites work: Concurrency Control by Locking
cites work: A theorem in database concurrency control
cites work: On the complexity of some two-person perfect-information games
cites work: Consistency in Hierarchical Database Systems
cites work: Concurrency Control and Consistency of Multiple Copies of Data in Distributed Ingres
cites work: Transactions and consistency in distributed database systems
cites work: Q3206351
cites work: Freedom from Deadlock of Safe Locking Policies
cites work: A Theory of Safe Locking Policies in Database Systems
description: scientific article; zbMATH DE number 3911758