Distributed algorithms for the detection and resolution of deadlocks in store-and-forward computer communication networks are presented and validated. The algorithms find and resolve buffer deadlocks using only a fixed number of buffers per node plus a fixed number of buffers per adjacent link. The detection algorithm is much simpler than other algorithms, but requires network-wide coordination. The resolution algorithm is based on earlier approaches, but uses the network-wide coordination to address certain synchronization problems. When the detection and resolution algorithms are merged, it is guaranteed that packets will arrive at their destinations in finite time.
展开▼
