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

被引：6

作者：

BLAZEWICZ, J

BOVET, DP

BRZEZINSKI, J

GAMBOSI, G

TALAMO, M

机构：

[1] UNIV ROMA LA SAPIENZA,DIPARTIMENTO SCI INFORMAZ,I-00198 ROME,ITALY

[2] UNIV ROMA TOR VERGATA,I-00173 ROME,ITALY

[3] UNIV ROMA LA SAPIENZA,DIPARTIMENTO INFORMAT & SISTEMIST,I-00198 ROME,ITALY

来源：

IEEE TRANSACTIONS ON COMPUTERS | 1994年 / 43卷 / 11期

关键词：

STORED-AND-FORWARD NETWORKS; DEADLOCK AVOIDANCE; CENTRALIZED APPROACH; BUFFER UTILIZATION; COMPLEXITY ANALYSIS;

D O I：

10.1109/12.324567

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

In this brief contribution, a problem of deadlock avoidance in store-and-forward networks with at least two buffers per node is considered for fixed as well as dynamic routing. For both cases polynomial time, centralized 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-complete, thus, unlikely to admit a polynomial-time algorithm. The presented results may be also interesting for other applications, some massively parallel computer systems being one of the examples.

引用

页码：1333 / 1338

页数：6

共 27 条

[1] PREDICTING DEADLOCK IN STORE-AND-FORWARD NETWORKS [J].

ARBIB, C ;

ITALIANO, GF ;

PANCONESI, A .

NETWORKS, 1990, 20 (07) :861-881

[2]

AWERBUCH B, 1991, 10 ANN ACM S PRINC D, P177

[3] DEADLOCK-RESISTANT FLOW-CONTROL PROCEDURES FOR STORE-AND-FORWARD NETWORKS [J].

BLAZEWICZ, J ;

BOVET, DP ;

GAMBOSI, G .

IEEE TRANSACTIONS ON COMMUNICATIONS, 1984, 32 (08) :884-887

[4] TIME-STAMP APPROACH TO STORE-AND-FORWARD DEADLOCK PREVENTION [J].

BLAZEWICZ, J ;

BRZEZINSKI, J ;

GAMBOSI, G .

IEEE TRANSACTIONS ON COMMUNICATIONS, 1987, 35 (05) :490-495

[5]

Blazewicz J., 1981, Performance '81. Proceedings of the 8th International Symposium on Computer Performance Modelling, Measurement and Evaluation, P503

[6]

Chan C., 1986, IEEE International Conference on Communications '86. ICC '86: `Integrating the World Through Communications'. Conference Record (Cat. No.86CH2314-3), P114

[7] DISTRIBUTED DEADLOCK DETECTION [J].

CHANDY, KM ;

MISRA, J ;

HAAS, LM .

ACM TRANSACTIONS ON COMPUTER SYSTEMS, 1983, 1 (02) :144-156

[8]

CIDON J, 1986, ICC 86, P124

[9]

COOK SA, 1971, 3RD P ANN ACM S THEO, P151

[10]

CYPHER B, 1992, 1UTH P ACM S PRINC D, P25

← 1 2 3 →