Determining Deadlock Exposure for a Class of Store and Forward Communication Networks
Vijay Ahuja · IBM Journal of Research and Development · 1980
Given a network design, is the network exposed to deadlock for message buffers? This problem is addressed for a class of networks called “routed networks.” A routed network is a store and forward communication network in which all transmissions follow predefined routes through the network. It is shown that a routed network is exposed to deadlock if and only if there exists a complete weighted matching of an appropriately defined bipartite graph for some subgraph of the network graph. An approach for determining whether a deadlock can occur is presented.