Deadlock-freedom (and safety) of transactions in a distributed database (Q579973)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Deadlock-freedom (and safety) of transactions in a distributed database |
scientific article; zbMATH DE number 4016241
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Deadlock-freedom (and safety) of transactions in a distributed database |
scientific article; zbMATH DE number 4016241 |
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
0.8978151
0 references
