On the flattest common supersequence method for deadlock-free routing in arbitrary networks

In this paper we consider the problem of deadlock-free routing in arbitrary parallel and distributed computers. We focus on asynchronous routing algor ithms which continuously receive new packets to route and which do not disc ard packets that encounter congestion. Specifically, we examine what we cal l the deadlock-free routing (DFR) problem. The input to the DFR problem con sists of an arbitrary network and an arbitrary set of paths in the network. The output consists of a routing algorithm, which is a list of the buffers used along each of the paths. The routing algorithm is required to be free from deadlock and the goal is to minimize the number of buffers required i n any one node. We study the DFR problem by converting it into an equivalent problem which we call the flattest common supersequence (FCS) problem. The input to the F CS problem consists of a set of sequences and the output consists of a sing le sequence that contains all of the input sequences as (possibly noncontig uous) subsequences. The goal of the FCS problem is to minimize the maximum frequency of any symbol in the output sequence. We present three main results. First, we prove that the decision version of the FCS problem is NP-complete, and has no polynomial-time approximation s cheme unless P = NP. An alternative proof is presented which shows that unl ike the shortest common supersequence (SCS) problem, the FCS problem is sti ll NP-complete for two input sequences. This implies that approximation alg orithms for FCS based on an exact pairwise merge are not possible. Next, we propose and experimentally evaluate a range of heuristics for FCS. Our exp erimental results show that one of these heuristics performs very well over a wide range of inputs. Lastly, we prove that this heuristic is in fact op timal for certain restricted classes of inputs.