PARTITIONING MESSAGE PATTERNS FOR BUNDLED OMEGA NETWORKS

In this paper, we consider a strategy for dealing with communication c onflicts in omega networks. Specifically, we consider the problem of p artitioning a set of conflicting messages into a minimum number of sub sets, called rounds, each free of communication conflicts. In addition to standard omega networks, we consider this problem for a more gener al class of networks called bundled omega networks, where interconnect ion links in the network are replaced by bundles of wires. Although th e partitioning problem has previously been considered in the literatur e, its computational complexity has remained open. We show that for a number of cases, the problem is NP-complete, but for certain special c ases, it is solvable in polynomial time. In addition, we present a cla ss of distributed, on-line heuristics for the problem. Finally, we giv e a lower bound of OMEGA(log N) on the performance ratio for one of th ese heuristics.