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 [11] and [29]. 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 [21]. 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.