z-logo
Premium
Predicting deadlock in store‐and‐forward networks
Author(s) -
Arbib Claudio,
Italiano Gluseppe F.,
Panconesl Alessandro
Publication year - 1990
Publication title -
networks
Language(s) - English
Resource type - Book series
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
ISBN - 3-540-50517-2
DOI - 10.1002/net.3230200705
Subject(s) - bipartite graph , combinatorics , vertex (graph theory) , deadlock , computer science , network packet , simple (philosophy) , mathematics , discrete mathematics , deadlock prevention algorithms , theoretical computer science , graph , distributed computing , computer network , philosophy , epistemology
Abstract 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(pn) time and space complexity, whereas the latter runs in O(n log n ) 1 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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here