to its destination output. One problem with this algorithm (and hence the network) is that if some switch or edge along the unique path from input i to output j (say) becomes congested or fails, then communication between input i and output j will be disrupted.

Because message congestion is a common occurrence in real networks, the wires in butterfly networks are typically dilated, so that each wire is replaced by a channel consisting of two or more wires. In a d-dilated butterfly, each channel consists of d wires. Because it is harder to congest a channel than it is to congest a single wire in a butterfly, dilated butterflies are better routing networks than simple butterflies (e.g., Koch, 1988; Kruskal and Snir, 1983; Rettberg et al., 1990).

Butterfly and dilated butterfly networks belong to a larger class of networks called delta networks (see, e.g., Kruskal and Snir, 1986). The switches on each level of a delta network can be partitioned into blocks. All of the switches on level 0 belong to the same block. On level 1, there axe two blocks, one consisting of the switches that are in the upper N/2 rows and the other consisting of the switches that are in the lower N/2 rows. In general, the switches in a block B of size M on level l have neighbors in two blocks, B_u, and B_l, on level l + 1. The upper block, B_u, contains the switches on level l + 1 that are in the same rows as the upper M/2 switches

Front Matter (R1-R10)

1 Introduction (1-16)

2 Simulated Annealing (17-30)

3 Approximate Counting Via Markov Chains (31-38)

4 Probabilistic Algorithms for Speedup (39-52)

5 Probabilistic Algorithms for Defeating Adversaries (53-64)

6 Pseudorandom Numbers (65-86)

7 Probabilistic Analysis of Packing and Related Partitioning Problems (87-108)

8 Probability and Problems in Euclidean Combinatorial Optimization (109-130)

9 Probabilistic Analysis in Linear Programming (131-148)

10 Randomization in Parallel Algorithms (149-160)

11 Randomly Wired Multistage Networks (161-174)

12 Missing Pieces, Derandomization, and Concluding Remarks (175-178)