Deadlock-freedom (and safety) of transactions in a distributed database (Q579973): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
| (4 intermediate revisions by 4 users not shown) | |||
| Property / review text | |||
We analyze the problem of determining freedom from deadlock of transactions which control concurrency by locking in a distributed database. We use a graph-theoretic formalization of the problem and show that it is NP-hard even for two transactions. The problem of determining safety (serializability of all schedules) and deadlock freedom is also examined. We show that this problem can be solved in polynomial time for any fixed number of transactions. | |||
| Property / review text: We analyze the problem of determining freedom from deadlock of transactions which control concurrency by locking in a distributed database. We use a graph-theoretic formalization of the problem and show that it is NP-hard even for two transactions. The problem of determining safety (serializability of all schedules) and deadlock freedom is also examined. We show that this problem can be solved in polynomial time for any fixed number of transactions. / rank | |||
Normal rank | |||
| Property / Mathematics Subject Classification ID | |||
| Property / Mathematics Subject Classification ID: 68P20 / rank | |||
Normal rank | |||
| Property / zbMATH DE Number | |||
| Property / zbMATH DE Number: 4016241 / rank | |||
Normal rank | |||
| Property / zbMATH Keywords | |||
concurrency control | |||
| Property / zbMATH Keywords: concurrency control / rank | |||
Normal rank | |||
| Property / zbMATH Keywords | |||
locking | |||
| Property / zbMATH Keywords: locking / rank | |||
Normal rank | |||
| Property / zbMATH Keywords | |||
distributed database | |||
| Property / zbMATH Keywords: distributed database / rank | |||
Normal rank | |||
| Property / zbMATH Keywords | |||
graph-theoretic formalization | |||
| Property / zbMATH Keywords: graph-theoretic formalization / rank | |||
Normal rank | |||
| Property / zbMATH Keywords | |||
NP-hard | |||
| Property / zbMATH Keywords: NP-hard / rank | |||
Normal rank | |||
| Property / zbMATH Keywords | |||
deadlock freedom | |||
| Property / zbMATH Keywords: deadlock freedom / rank | |||
Normal rank | |||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
| Property / full work available at URL | |||
| Property / full work available at URL: https://doi.org/10.1016/0022-0000(86)90017-6 / rank | |||
Normal rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W1973723007 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: The notions of consistency and predicate locks in a database system / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Q4198056 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: The NP-completeness column: An ongoing guide / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Is distributed locking harder? / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: A fast algorithm for testing for safety and detecting deadlocks in locked transaction systems / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Concurrency Control by Locking / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: The serializability of concurrent database updates / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Consistency in Hierarchical Database Systems / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Q3959469 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Optimal algorithms to compute the closure of a set of iso-rectangles / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: An algorithm for early unlocking of entities in database transactions / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: A Theory of Safe Locking Policies in Database Systems / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Freedom from Deadlock of Safe Locking Policies / rank | |||
Normal rank | |||
| links / mardi / name | links / mardi / name | ||
Latest revision as of 12:15, 18 June 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Deadlock-freedom (and safety) of transactions in a distributed database |
scientific article |
Statements
Deadlock-freedom (and safety) of transactions in a distributed database (English)
0 references
1986
0 references
We analyze the problem of determining freedom from deadlock of transactions which control concurrency by locking in a distributed database. We use a graph-theoretic formalization of the problem and show that it is NP-hard even for two transactions. The problem of determining safety (serializability of all schedules) and deadlock freedom is also examined. We show that this problem can be solved in polynomial time for any fixed number of transactions.
0 references
concurrency control
0 references
locking
0 references
distributed database
0 references
graph-theoretic formalization
0 references
NP-hard
0 references
deadlock freedom
0 references
0 references
