Predicting deadlock in store-and-forward networks

✍ Scribed by Claudio Arbib; Gluseppe F. Italiano; Alessandro Panconesl

• Book ID: 102961600
• Publisher: John Wiley and Sons
• Year: 1990
• Tongue: English
• Weight: 987 KB
• Volume: 20
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/net.3230200705

✦ Synopsis

We consider the problem of predicting whether a deadlock will necessarily occur in a store-and-forward network. We define two versions of this problem, depending on whether or not the routes to be followed by packets are fixed. For networks with only one buffer per vertex, both versions of this problem are shown to be NP-complete even for simple classes of graphs (among others bipartite graphs, two terminal series-parallel [TTSP] graphs and therefore planar graphs). On the other hand, the same problems are shown to be polynomially solvable for treelike networks. In this case, two efficient algorithms for checking whether a treelike network with n vertices and p packets is bound to deadlock are proposed. The former has an O b n ) time and space complexity, whereas the latter runs in O(n log n)' time and requires O(n) space. In the case of multibuffered networks, both versions of the problem are shown to be NP-complete even on treelike networks.