The scheduling algorithm from Section 2 can be used as a subroutine in algorithms for emulating shared-memory machines on bounded-degree networks. A shared-memory machine with a large address space can be emulated by randomly hashing the memory locations to the nodes of a butterfly as in  and . The hashing ensures that the congestion of the packets implementing each memory access step is small. The algorithm from Section 2 is used to schedule the movements of these packets.
Given a set of N packets whose paths have congestion c on a leveled network with depth L, a setting of ranks that ensures delivery in time can be found can be found off-line deterministically in time . The proof uses the Raghavan-Spencer technique [27, 33] to sequentially find a setting of the ranks so that no bad event corresponding to a delay sequence occurs.
One application is in preparing simulations by volume and area-universal networks off-line so that no random bits are needed. As before, the first step is to map the processors of the network to be simulated, B, to the processors of the area-universal network, U, from Section 7 using the recursive decomposition strategy from . Network U has N processors, and B has area . To simulate each step of B, network U must route a set of messages with load factor . The second step is to find paths for the messages. Since these messages link the same processors at every step of B, it is sufficient to find paths once off-line. They can be reused over and over during the simulation. Given a set of n messages with load factor , it is possible to find a set of paths with congestion and dilation in a fat-tree with root capacity M off-line deterministically in time polynomial in n and M. The final step is to find a set of ranks for the messages. These ranks can also be reused at each step of the simulation. Network U has root capacity . Thus, both the paths and the ranks for the packets can be determined off-line deterministically in time polynomial in N so that the time to simulate each step of B is .
By making minor modifications to the definition of a delay sequence, it is possible to prove that not only does the late arrival of some packet imply that a bad event occurs, but also if a bad event occurs then some packet is delayed. More precisely, some packet arrives at step L+w where w = m+qf if and only if a bad event corresponding to a delay sequence of length with m+qf packets occurs.