Next: 8.4 Bounding the congestion Up: 8 Sorting on butterflies Previous: 8.2 Analysis

The first step in the analysis is to show that, with high probability, the number of splitter candidates chosen by each butterfly is within a constant factor of the expectation. We say that an M-input butterfly is well-partitioned if the number of splitter candidates chosen is between and . The upper bound ensures that the candidates can be sorted deterministically by the butterfly in time and the lower bound implies that the subbutterflies at the next level of recursion will have at most inputs. If all of the butterflies are well-partitioned, then the algorithm terminates after levels of recursion. (The choice of and as the coefficients of are not particularly important. Other constants would serve equally well.)

Proof: We begin by considering a single M-input butterfly that is to sort n packets. Since each packet chooses independently to be a candidate, the number of candidates has a binomial distribution. Let S be the number of successes in r independent Bernoulli trials where each trial has probability p of success. Then we have . We estimate the area under the tails of this binomial distribution using a Chernoff-type bound [8]. Following Angluin and Valiant [3] we have

for and . In our application r = n, , , and . For any fixed constant , there is a constant such that the right-hand sides of the two inequalities sum to at most for .

To bound the probability that any butterfly is not well-partitioned, we sum the probabilities for all of the individual butterflies. Over the course of the algorithm, the algorithm is invoked on at most individual butterflies. Thus, the sum is at most . For any , there is a such that this sum is at most .

to .667emto .667em

The next lemma shows that, with high probability, the number of packets in each interval is at most a constant factor times its expectation. We say that an M-input butterfly that is assigned n packets to sort is -split if every interval has size at most . As we shall see, if every butterfly is -split and there are levels of recursion, then by lightly loading the butterfly we can ensure that no butterfly is assigned too many packets to sort.

Proof: We begin by examining a single packet in a single M-input butterfly that is to sort n-packets. To show that a packet lies in an interval of size at most it is sufficient to show that both following and preceding it in the sorted order at least of the next packets are candidates.

First we consider the packets that follow in the sorted order. The number of candidates in a sequence of packets has a binomial distribution. For , , , , and , we have . For any we can make the right-hand side smaller than by choosing large enough.

The calculation for the packets that precede in the sorted order are identical. The probability that fewer of the preceding packets are candidates is at most . Thus, the probability that an individual packet lies in an interval of size greater than is at most .

To bound the probability that any interval in the butterfly is too large we sum the probabilities that each individual packet lies in an interval that is too large. Since there are at most packets, this sum is at most .

To bound the probability that any butterfly is not -split, we sum the probabilities that each individual butterfly is not. Over the course of the algorithm, the algorithm is invoked on at most butterflies. The sum of the probabilities is at most . For any constant , we can make this sum at most by making large enough.

to .667emto .667em

The remainder of the analysis is conditioned on the event that every subbutterfly is well-partitioned and -split, which occurs with high probability. Two technical points bear mentioning. First, Lemma 8.1 requires that the number of inputs to every subbutterfly be at least , where is some constant. Since the recursion terminates when the number of inputs is , N must be large enough that . Second, both Lemmas 8.1 and 8.2 hold independent of the number of packets to be sorted by each subbutterfly. Thus, as the following lemmas show, we can adjust the load on the butterfly in order to ensure that each M-input subbutterfly receives at most M packets to sort.

Proof: At each level of recursion the number of inputs drops from M to at most , until the number of inputs reaches .

to .667emto .667em

Proof: Since the ratio of packets to inputs is at the top level of the recursion, and increases by at most a constant factor at each of levels, it is possible to choose such that at the bottom level it will be at most one.

to .667emto .667em

Next: 8.4 Bounding the congestion Up: 8 Sorting on butterflies Previous: 8.2 Analysis

Bruce Maggs
Mon Jul 22 22:57:44 EDT 1996