OPTIMAL CENTRALIZED ALGORITHMS FOR STORE-AND-FORWARD DEADLOCK-AVOIDANCE

In this brief contribution, a problem of deadlock avoidance in store-a nd-forward networks with at least two buffers per node is considered f or fixed as well as dynamic routing. For both cases polynomial time, c entralized deadlock avoidance algorithms are proposed and shown to be optimal in a sense of possible buffer utilization. When the number of buffers is equal to one for each node the problem is known to be NP-co mplete, thus, unlikely to admit a polynomial-time algorithm. The prese nted results may be also interesting for other applications, some mass ively parallel computer systems being one of the examples.