Deadlock models in distributed computation
Valmir Carneiro Barbosa, Alan Diêgo Aurélio Carneiro, Fábio Protti, Uéverton S. Souza · 2016
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.