Optimal deterministic task distribution for multiprocessors

Considers the problem of distributing tasks on a multiprocessor network. Some processors cannot accept any tasks, hence the problem is formulated as one of routing packets from an arbitrary subset S to an arbitrary subset T, where the exact target node for a particular packet is unspecified. The solution presented matches n2ⁿ tasks to target nodes in O(logn) time-on a butterfly, using a deterministic routing and with low (<10) constant factor. As a corollary, the paper also obtains a simple solution to the (n, K) token distribution problem