DEADLOCK PREDICTION IN THE CASE OF DYNAMIC ROUTING

作     者：DANIEL P. BOVET MIRIAM DI IANNI PIERLUIGI CRESCENZI 

作者机构：Dipartimento di Matematica Università di Roma “La Sapienza” 00185 Roma Italy Dipartimento di Matematica Università de L’Aquila 67010 L’Aquila Italy 

出 版 物：《International Journal of Foundations of Computer Science》 

年 卷 期：1990年第1卷第3期

页      面：185-199页

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Store-and-Forward Networks Deadlock prediction Polynomial algorithms NP-completeness 

摘      要：One of the main issues in flow control problems is deadlock of messages caused by a limited amount of resources. In this paper, the problem of predicting whether a deadlock will necessarily occur in a Store-and-Forward Network is analyzed. We show that, in the case of dynamic routing, the deadlock prediction problem can be decided in polynomial time if tokens are allowed to transit more than once through the same vertex, in contrast with an NP-completeness result in the case where they are allowed to transit at most once.