Name
Title | ||
|---|---|---|
Deadlock models in distributed computation: foundations, design, and computational complexity. |
Abstract | ||
|---|---|---|
Distributed systems consist of a set of independent processors interconnected by a communication network that supports resource sharing. A deadlock occurs in a distributed system when a group of processes waits indefinitely for resources from each other. Distributed systems are usually represented by wait-for graphs, where the behavior of a process is determined by a deadlock model. In this paper, we revisit deadlock model concepts, and present a new deadlock model as a simpler alternative to the And/Or model. Using also computational complexity and circuit complexity aspects, we provide a novel analysis of the hierarchy of classical deadlock models, where we identify how expressive each model is from the point of view of polynomial computations. Finally we present a generic graph structure to characterize deadlock situations. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1145/2851613.2851880 | SAC |
Field | DocType | Citations |
Edge chasing,Concurrency control,Circuit complexity,Computer science,Deadlock,Theoretical computer science,Wait-for graph,Deadlock prevention algorithms,Shared resource,Computational complexity theory,Distributed computing | Conference | 1 |
PageRank | References | Authors |
0.35 | 8 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Valmir C. Barbosa | 1 | 350 | 56.76 |
| Alan Diêgo A. Carneiro | 2 | 1 | 0.69 |
| Fábio Protti | 3 | 357 | 46.14 |
| Uéverton S. Souza | 4 | 20 | 21.12 |