Is distributed locking harder?

DOI10.1016/0022-0000(84)90078-3MaRDI QIDQ1061510zbMATH OpenOpenAlexFDO

Authors Paris C. Kanellakis, Christos Papadimitriou

Publication date 1984

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0022-0000(84)90078-3

zbMATH Keywords

concurrency controlcoNP-completedistributed databasegraph-theoretic techniquelocked transactionsserializable schedules

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Information storage and retrieval of data (68P20) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

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.

Recommendations

• On the power of safe locking
• Deadlock-freedom (and safety) of transactions in a distributed database
• The Complexity of Distributed Concurrency Control
• Problems in transaction concurrency control algorithms
• scientific article; zbMATH DE number 4033153

Cites work

• A fast algorithm for testing for safety and detecting deadlocks in locked transaction systems
• A locking protocol for resource coordination in distributed databases
• A theorem in database concurrency control
• A Theory of Safe Locking Policies in Database Systems
• Concurrency Control and Consistency of Multiple Copies of Data in Distributed Ingres
• Concurrency Control by Locking
• Consistency in Hierarchical Database Systems
• Freedom from Deadlock of Safe Locking Policies
• scientific article; zbMATH DE number 3648167 (Why is no real title available?)
• On the complexity of some two-person perfect-information games
• The notions of consistency and predicate locks in a database system
• Transactions and consistency in distributed database systems

Cited in

(10)

• Concurrent execution of transaction copies
• A note on the transaction backout problem
• Locking based on a pairwise decomposition of the transaction system
• Safe locking policies for dynamic databases
• Scalable hierarchical locking for distributed systems
• An algorithm for early unlocking of entities in database transactions
• scientific article; zbMATH DE number 4049029 (Why is no real title available?)
• Distributed Computing - IWDC 2003
• Deadlock-freedom (and safety) of transactions in a distributed database
• Multiserialization of iterated transactions

Describes a project that uses

Uses Software

• INGRES

This page was built for publication: Is distributed locking harder?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1061510)