Increasing the size of a network by a constant factor can increase performance by more than a constant factor

Abstract

In one routing scheme which has been implemented on a parallel architecture based on the butterfly graph, messages are sometimes destroyed. It is shown that if messages are sent to random destinations, the expected number of messages that reach their destinations is Theta (n(log n)-1/q), where n is the size of the butterfly graph and q is the number of messages that can move through one edge (or, equivalently, vertex) in one time step. In the analysis of this problem, interesting techniques for solving nonlinear systems of difference equations are developed that could have applications to other problems.<>