Abstract
Deadlock prevention is usually realized by imposing strong restrictions on packet transmissions in the network so that the resulting deadlock free routing algorithms are not optimal with respect to resources utilization. Optimality request can be satisfied by forbidding transmissions only when they would bring the network into a configuration that will necessarily evolve into a deadlock. Hence, optimal deadlock avoidance is closely related to deadlock prediction. In this paper it is shown that wormhole deadlock prediction is an hard problem. Such result is proved with respect to both static and dynamic routing.
Chapter PDF
References
C. Arbib, G. Italiano, A. Panconesi, “Predicting deadlock in Store-and-Forward networks”, Networks, 20, 861–882, 1990.
B. Awerbuch, S. Kutten, D. Peleg, “Efficient deadlock-free routing”, Proc. of the Tenth Annual ACM Symposium on principles of Distributed Computing, Montreal, Canada, 177–188, 1991.
F. Belik, “An efficient deadlock avoidance technique”, IEEE Trans. on Computers, 39, 882–888, 1990.
J. Blazewicz, J. Brzezinski, G. Gambosi, “Optimization aspects of deadlock prevention in packet-switching networks”, European Journal of Operational Research, 57, 1–12, 1992.
D.P. Bovet, P. Crescenzi, M. Di Ianni, “Deadlock prediction in the case of dynamic routing”, Int. Journal of Foundations of Computer Science, 1, 185–199, 1990.
W.J. Dally, C.L. Seitz, “The torus routing chip”, Journal of Distributed Systems, 1, 187–196, 1986.
M.R. Garey, D.S. Johnson, Computers and intractability: a guide to the theory of NP-completeness, Freeman, San Francisco, 1979.
X. Lin, P.K. McKinley, L.M. Ni, “The message flow model for routing in wormholerouted networks”, Proc. Int. Conf. Parallel Processing, 1993.
D.H. Linder, J.C. Harden, “An adaptive and fault-tolerant wormhole routing strategy for k-ary n-cubes”, IEEE Trans. Computers, 40, 2–12, 1991.
P.K. McKinley, L.M. Ni, “A survey of wormhole routing techniques; in direct networks”, IEEE Computer, 62–77, 1993.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Di Ianni, M. (1997). Wormhole deadlock prediction. In: Lengauer, C., Griebl, M., Gorlatch, S. (eds) Euro-Par'97 Parallel Processing. Euro-Par 1997. Lecture Notes in Computer Science, vol 1300. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0002733
Download citation
DOI: https://doi.org/10.1007/BFb0002733
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63440-9
Online ISBN: 978-3-540-69549-3
eBook Packages: Springer Book Archive