The problem of preventing deadlocks and livelocks in computer communication networks, in particular, those with wormhole routing, is considered. The method to prevent deadlocks is to prohibit certain turns (i.e., the use of certain pairs of connected edges) in the routing process, in such a way that eliminates all cycles in the graph. We propose a new algorithm that constructs a minimal (irreducible) set of turns that breaks all cycles and preserves connectivity of the graph. The algorithm is tree-free and is considerably simpler than earlier cycle-breaking algorithms. We prove its properties and present lower and upper bounds for minimum cardinalities of cycle-breaking connectivity preserving sets for graphs of general topology as well as for planar graphs. In particular, the algorithm guarantees that not more than 1/3 of all turns in the network become prohibited. We also present experimental results on the fraction of prohibited turns, the distance dilation, as well as on the message delivery times and saturation loads for the proposed algorithm in comparison with known tree-based algorithms. The proposed algorithm outperforms substantially the tree-based algorithms in all characteristics considered.

In this paper we consider the problem of constructing minimal cycle-breaking sets of turns for graphs that model communication networks, as a method to prevent deadlocks in the networks. We present a new cycle-breaking algorithm called simple cycle-breaking or SCB algorithm that is considerably simpler than earlier algorithms. The SCB algorithm guarantees that the fraction of prohibited turns does not exceed 1/3. Experimental simulation results for the SCB algorithm are shown.