Questions? Call 800-624-6242

| Items in cart [0]

PAPERBACK
price:\$52.75

## Probability and Algorithms (1992) Commission on Physical Sciences, Mathematics, and Applications (CPSMA)

### Citation Manager

. "11 Randomly Wired Multistage Networks." Probability and Algorithms. Washington, DC: The National Academies Press, 1992.

 Page 162

The following HTML text is provided to enhance online readability. Many aspects of typography translate only awkwardly to HTML. Please use the page image as the authoritative form to ensure accuracy.

Probability and Algorithms

FIGURE 11.1: An 8-input butterfly network. Reprinted, with permission, from Arora et al. (1990). Copyright © 1990 by ACM Press.

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.

#### 11.1.1Dilated Butterflies

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).

#### 11.1.2Delta Networks

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, Bu, and Bl, on level l + 1. The upper block, Bu, contains the switches on level l + 1 that are in the same rows as the upper M/2 switches

 Page 162
 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)