Title :
A distributed algorithm for detecting and resolving store-and-forward deadlocks in networks with minimum exchange buffers
Author :
Luo, Kenneth C K ; Klostermeyer, W.F. ; Chow, Yuan-Chieh
Author_Institution :
Dept. of Comput. & Inf. Sci., Florida Univ., Gainesville, FL, USA
Abstract :
The store-and-forward deadlock problem in packet switching networks is considered. Most of the previous work addressed this issue using reserved buffers, and most algorithms, with the exception of that given by J. Blazewicz et al. (1987) (the BBG algorithm), use more reserved buffers than necessary, implying that each node does not have the maximum flexibility in message routing. It is shown that the BBG deadlock prevention algorithm can generate an unbounded number of backtracked messages. A deadlock detection and resolution algorithm that allows a minimum number of buffers to be reserved and minimizes the number of backtracked messages at the end of each detection and resolution is presented. It is shown that in the worst case, only O (|E|) backtracked messages can be generated as a result of this algorithm, and that each backtracked message is backtracked only one hop
Keywords :
buffer storage; computer networks; distributed algorithms; packet switching; system recovery; BBG deadlock prevention algorithm; backtracked messages; deadlock detection; deadlock resolution; distributed algorithm; minimum exchange buffers; packet switching networks; store-and-forward deadlocks; Buffer storage; Clocks; Computer science; Distributed algorithms; Intelligent networks; Resource management; Routing; Statistical distributions; Synchronization; System recovery;
Conference_Titel :
INFOCOM '93. Proceedings.Twelfth Annual Joint Conference of the IEEE Computer and Communications Societies. Networking: Foundation for the Future, IEEE
Conference_Location :
San Francisco, CA
Print_ISBN :
0-8186-3580-0
DOI :
10.1109/INFCOM.1993.253266