# On Contention Resolution Protocols and Associated Probabilistic Phenomena.

Abstract. Consider an on-line scheduling problem in which a set of abstract processes are competing for the use of a number of resources. Further assume that it is either prohibitively expensive or impossible for any two of the processes to directly communicate with one another. If several processes simultaneously attempt to allocate a particular resource (as may be expected to occur, since the processes cannot easily coordinate their allocations), then none succeed. In such a framework, it is a challenge to design efficient contention resolution protocols.Two recently-proposed approaches to the problem of PRAM emulation give rise to scheduling problems of the above kind. In one approach, the resources (in this case, the shared memory cells) are duplicated and distributed randomly. We analyze a simple and efficient deterministic algorithm for accessing some subset of the duplicated resources. In the other approach, we analyze how quickly we can access the given (nonduplicated) resource using a simple randomized strategy. We obtain precise bounds on the performance of both strategies. We anticipate that our results will find other applications.

Categories and Subject Descriptors: F.1.2 [Computation by Abstract Devices]: Models of Computation--parallelism and concurrency; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems

General Terms: Algorithms, Theory

Additional Key Words and Phrases: Parallel computation, hash functions, emulation protocols

1. Introduction

Let k balls be thrown independently and uniformly at random into n bins, and let random variable X denote the maximum number of balls landing in any single bin. If k = [Theta](n), it is well known that X = [Theta](lg n/lg lg n) wvhp. (Throughout this paper, we use "wvhp" to mean "with probability at least 1 - [n.sup.-c] for any positive constant c", and we use "whp" to mean "with probability at least 1 - [n.sup.-c] for some positive constant c".) If k = [Theta](n lg n), it is similarly well known that X = [Theta](lg n) wvhp. (These claims are straightforward to prove using standard bounds on the tail of the binomial distribution [Chernoff 1952].) These sharp threshold phenomena have important consequences in a wide variety of hashing-related applications. In this paper, we explore two similar (but more complex) threshold phenomena, one arising in each of two fundamental families of contention resolution protocols.

To make our discussion of contention resolution protocols more concrete, we will focus our attention primarily on a single application, namely that of efficiently emulating an EREW PRAM on a c-collision crossbar network. We begin by reviewing the definitions of these two computational models. An EREW PRAM is a collection of n processors along with a global shared memory. Input and output are provided in the shared memory. In a single computational step, each processor can read or write one memory location. The sole restriction is that no two processors are allowed to access the same memory location in a single step. (If two processors attempt to access the same memory location in a single step, then the machine halts.)

A c-collision crossbar network (or simply, a c-collision crossbar) is a more realistic model of parallel computation in which the global shared memory is distributed over n disjoint memory modules. Input and output are provided in the distributed memory. Each computational step consists of a read/write phase followed by an acknowledgment phase. During the read/write phase each processor can issue one read or write request for a specific memory location. If the total number of read/write requests involving memory locations stored in any particular memory module M is less than or equal to c, then all requests involving M succeed and are acknowledged during the acknowledgment phase. On the other hand, if more than c processors attempt to access memory locations stored in the same memory module M, then all requests involving M fail and no corresponding acknowledgements are sent. A c-arbitrary crossbar is defined in the same manner as a c-collision crossbar, except that if more than c processors attempt to access some memory module M, then an arbitrary subset of c of the requests succeed and are acknowledged.

The c-collision and c-arbitrary crossbar models have been studied previously under different names. (Our terminology is new.) The local memory PRAM model of Anderson and Miller [1988], later studied under the name OCPC (optical communication parallel computer) in Gereb-Graus and Tsantilas [1992], Goldberg and Jerrum [1992] and Goldberg et al. [1993], corresponds to the 1-collision crossbar model. Valiant's S*PRAM model [Valiant 1990] corresponds to the 1-arbitrary crossbar model. Assuming a complete interconnection between processors and memory modules, the c-collision (respectively, c-arbitrary) DMM model of Dietzfelbinger and Meyer auf der Heide [1993] corresponds to the c-collision (respectively, c-arbitrary) crossbar model.

We now return to the question of efficiently emulating an EREW PRAM on a c-collision crossbar. More specifically, assume that we wish to emulate a k-processor EREW PRAM on an n-processor c-collision crossbar, where k is some multiple of n. If we map k/n EREW PRAM processors to each processor of the crossbar, and employ a random hash function to map each location of the EREW PRAM shared memory to some memory module of the crossbar, we can easily see the connection between the random "balls and bins" experiment stated at the outset and the desired emulation: Each of the at most k read or write requests generated in a single step of the EREW PRAM computation corresponds to a ball, and each memory module corresponds to a bin.

If k = n and c = O(1), we can conclude that any scheme based on a single hash function requires [Omega](lg n/lg lg n) time to emulate one step of the EREW PRAM. On the other hand, Dietzfelbinger and Meyer auf der Heide [1993] have recently shown that a bound of O(lg lg n) time per EREW PRAM step is attainable for the same settings of k and c. They present a contention resolution protocol that minimizes the effect of the inevitable "hot-spot" memory modules (e.g., those memory modules receiving [Theta](lg n/lg lg n) requests under a given hash function) by employing three different hash functions. Thus, at the expense of increasing the total storage requirement by a factor of 3, the running time of the emulation is exponentially decreased. The fast performance of the Dietzfelbinger and Meyer auf der Heide emulation relies on a sharp threshold phenomenon that is the focus of Section 2. An overview of our results in this area is given in Section 1.1.

If k = n lg n and c = O(1), the second "balls in bins" claim made at the outset of the paper shows that the emulation of a single EREW PRAM step will correspond to a [Theta](lg n)-relation routing problem wvhp. (An h-relation routing problem is one in which each processor is the source of at most h packets and each memory module is the destination of at most h packets.) Thus, a variety of authors have considered the complexity of h-relation routing on the 1-collision crossbar. We are particularly interested in a natural randomized h-relation routing algorithm employed by Gereb-Graus and Tsantilas [1992]. (This algorithm is essentially the same as a previous algorithm proposed by Greenberg and Leiserson [1985] for routing on a fat tree network.) The idea of this algorithm is to use randomization to break the symmetry between sets of processors with packets to be sent to the same memory module: In a given "round" a processor with p packets left to send attempts to send a randomly chosen packet with probability roughly p/h, and does nothing with probability roughly 1 - p/h. The resulting running time is [Theta](h + lg n lg h). (Remark: The running time is stated as [Theta](h + lg n lg lg n) in Gereb-Graus and Tsantilas [1992], since they only considered the case h [is greater than or equal to] log n.) Thus, the algorithm leads to a work-optimal EREW PRAM emulation only for h = [Omega](lg n lg lg n).

The symmetry-breaking idea employed by Gereb-Graus and Tsantilas is central to many other randomized algorithms and communication protocols (e.g., the standard Ethernet protocol [Metcalfe and Boggs 1976] and the classic ALOHA packet radio network protocol [Abramson 1973]). As we have seen, such randomized symmetry-breaking does not always lead to performance that is obviously optimal (i.e., that matches a trivial lower bound). (For example, we might have hoped that the algorithm of Gereb-Graus and Tsantilas would run in [Theta](lg n) time for the case h = [Theta](lg n).) The main result of the Section 3 is a tight lower bound on the running time of certain randomized symmetry-breaking procedures. In particular, with respect to the problem of randomized h-relation routing on the 1-collision crossbar, we have completely characterized the power of the natural symmetry-breaking paradigm. An overview of our results in this area is given in Section 1.2.

1.1. REDUNDANCY-BASED PROTOCOLS. In this section, we give a brief overview of our emulation results related to protocols employing multiple hash functions. As mentioned earlier, Dietzfelbinger and Meyer auf der Heide [1993] have presented a protocol using three hash functions that emulates an n-processor EREW PRAM in O(lg lg n) time on an n-processor c-collision crossbar. Under their protocol, a read or write operation of memory location x by EREW PRAM processor i is emulated by having processor i of the c-collision crossbar access 2 out of the 3 copies corresponding to memory location x. (A similar protocol was presented in Karp et al. [1992]; the idea that accessing 2 out of 3 copies is sufficient for the purposes of such an emulation was first used by Upfal and Wigderson [1987].) The analysis presented in Dietzfelbinger and Meyer auf der Heide [1993] requires some slack in the constants; in particular, they require c [is greater than or equal to] 3, and are only able to analyze the protocol when it is used to emulate [Epsilon]n processors at a time, where [Epsilon] is a sufficiently small positive constant. (Thus, the overall running time of the protocol is increased by a factor of 1/[Epsilon].)

The protocol of Dietzfelbinger and Meyer auf der Heide [1993] is easily generalized to the case where b hash functions are used, and each processor of the c-collision crossbar is required to access a out of b copies of a particular memory location, a [is less than] b. In Section 2.3, we focus on the case a = 1, and pinpoint the asymptotic complexity of the resulting protocol for all possible choices of the parameters b and c. (Furthermore, our analysis goes through with [Epsilon] = 1, that is, we consider the most basic form of the protocol in which the action of all n EREW PRAM processors is emulated at once.) For c = 1, we prove that the protocol runs in [Theta](lg lg n) time whp if b [is greater than or equal to] 3. For c = 1 and b = 2, we prove that the protocol runs in [Omega](lg n) time wvhp. For any b [is greater than or equal to] 2 and any constant c [is greater than or equal to] 2, we prove that the protocol runs in [Theta](lg lg n) time whp. (The protocol will run faster for nonconstant c. It would not be difficult to extend our analysis to obtain tight bounds for nonconstant c.) In the case of a c-arbitrary crossbar, the protocol runs in [Theta](lg lg n) time whp for b [is greater than or equal to] 2. In Section 2.4, we show that the above results hold even if the hash functions are only O([log.sup.[Alpha]n)-wise independent, where [Alpha] is a real constant.

In Section 2.5, we observe that any "a out of b" problem with a [is greater than] 1 can be efficiently reduced to a number of "1 out of l" problems, where l = 2 or l = 3. Thus, we are able to easily upper bound the complexity of a (new) protocol for essentially any "a out of b" problem. One might suspect that a reduction of this sort, while making the analysis easier, is only doing so at the expense of a significant constant factor in performance. Interestingly, this is not the case; rather, as discussed in Section 2.5, our reduction yields a faster "a out of b" protocol than is obtained via the natural generalization of Dietzfelbinger and Meyer auf der Heide [1993] for virtually all possible values of a and b.

The main idea underlying the aforementioned results may be explained as follows: While the process of throwing k balls independently and uniformly at random into n bins is well understood (e.g., we can easily compute a sharp bound on the number of bins receiving exactly one ball), we find that the sequence of distributions arising in the analysis of any "a out of b" protocol quickly deviates from such simple behavior. In Dietzfelbinger and Meyer auf der Heide [1993] and Meyer auf der Heide et al. [1995], this problem is attacked by studying certain structures related to the sequence of distributions. We take a different approach to this problem. We provide a more accurate analysis of the "1 out of l" protocol by precisely characterizing the associated sequence of distributions in terms of "truncated k balls in n bins" distributions (e.g., throw k balls into n bins and then remove all balls contained in bins with less than or equal to c balls). Finally, as mentioned above, we derive a protocol for the "a out of b" problem by reducing it to a number of "1 out of l" problems.

1.2. SYMMETRY-BREAKING PROTOCOLS. In this section, we give a brief overview of our results on symmetry-breaking protocols in multiple access channels and for h-relation routing on a 1-collision crossbar.

There has been considerable effort in proving bounds on symmetry-breaking protocols to resolve contention in Ethernet-like multiple access channels.(1) Specifically, it is assumed that some h of n stations wish to transmit to a single shared channel, but a station succeeds in its transmission if and only if it is the only station transmitting at that time. A symmetry-breaking protocol generates a schedule of transmission attempts for each station so that all h stations eventually transmit successfully. Previously studied protocols assume that all stations receive a feedback of 0, 1, or [is greater than or equal to] 2 at each step, depending on how many stations attempt to transmit. We call this the Ethernet model. For the Ethernet model, a lower bound of [Omega]((h/log h)log n) was shown for the time of any deterministic protocol [Greenberg and Winograd 1985], and it was shown that an O(h log n) time (nonadaptive) deterministic protocol exists [Komlos and Greenberg 1985]. We study protocols in which only the transmitting stations receive feedback (1 or [is greater than or equal to] 2) at a given step. We call the general contention resolution problem on this model the Control Tower problem. Protocols to solve the Control Tower problem correspond to non-adaptive protocols for contention resolution on the Ethernet model. Thus, the lower bound of [Omega]((h/log h)log n) above applies to any deterministic solution to the Control Tower problem also. We show a slightly stronger result, that to send even one message (in the Control Tower model, or nonadaptive Ethernet model) requires [Omega]((h/min{log h,log log n}) log n) steps. From a technical standpoint, it is most natural to view the Control Tower problem as a problem on hypergraphs. Our lower bound relies on a combinatorial argument for extracting "thick" hypergraphs and another combinatorial argument showing the existence of contention-generating "near transversals".

Much faster protocols can be obtained for the Control Tower problem using randomization. For instance, the randomized protocol in Gereb-Graus and Tsantilas [1992] solves the Control Tower problem in O(h + log h log n) steps, wvhp. We show a tight lower bound of [Omega](h + log h log n) for randomized protocols for the Control Tower problem that succeed with probability at least 1 - [n.sup.-3/4]. (Naturally, this provides the same lower bound for non-adaptive randomized protocols in the Ethernet model.) Again, we find it technically useful to view the Control Tower problem as a problem on hypergraphs. The randomized lower bound then relies on a combinatorial argument for extracting "thick" hypergraphs (where the "thickness" quality is fundamentally different than that in the deterministic lower bound), and a probabilistic argument showing a nontrivial probability of the existence of contention-generating "near transversals" in random sets of vertices.

We now turn to the problem of direct h-relation routing on a 1-collision crossbar. In a direct algorithm for a given routing problem, the messages to be routed can only be sent directly from the source to the destination without any intermediate hops, and no additional information can be sent between the processors. Direct algorithms have the advantage of simplicity and low overhead. While nondirect algorithms may have better asymptotic behavior, it is likely that this improved asymptotic behavior is only achieved at the expense of large constant factors. The previously mentioned h-relation routing algorithm of Gereb-Graus and Tsantilas [1992] is a direct algorithm, and direct h-relation routing algorithms have also been studied in Goldberg and Jerrum [1992] and Goldberg et al. [1993]. We refer the reader to these previous papers for further details.(2)

There is a close correspondence between results for the Control Tower problem and results for direct h-relation routing on a 1-collision crossbar. In fact, the lower bound for deterministic protocols for the Control Tower problem directly gives the same lower bound for deterministic direct h-relation routing. The correspondence is not exact in terms of deterministic upper bounds, however, as the upper bound of O(h log n) on the Control Tower problem only indicates that there is an O([h.sup.2]log n) deterministic direct h-relation routing algorithm. We show that this bound can be improved to O(h log h log n) by slightly modifying the deterministic Control Tower protocol. Finally, we show that the tight lower bound for randomized protocols for the Control Tower problem can also be used to prove a tight lower bound of [Omega](h + log h log n) for direct randomized h-relation routing on a 1-collision crossbar.

2. Multiple Hash Functions

In this section, we address the a out of b problem discussed in Section 1 on c-arbitrary and c-collision crossbars. In an a out of b problem on an n-processor crossbar, each shared memory cell is uniformly and independently hashed b times into the memory modules of the crossbar, and each processor has to successfully access a out of the b copies of a particular shared memory cell.

Consider the 1 out of l problem where l [is greater than or equal to] 2. Let the l hash functions be labeled hi, 0 [is less than or equal to] i [is less than] l, and the shared memory request of processor j be for cell [x.sub.j]. Processor j needs to successfully access one of the memory locations [h.sub.i]([x.sub.j]), 0 [is less than or equal to] i [is less than] l. To solve this problem, the following simple sequence of l rounds can be repeated until each processor has had one successful access: In the jth round, if processor i has not successfully accessed any copy of [x.sub.i], then processor i accesses [h.sub.j]([x.sub.i]). (This is analogous to Access Schedule 2 of Dietzfelbinger and Meyer auf der Heide [1993], defined for the 2 out of 3 problem.) On a c-collision crossbar, processor j succeeds on its access if and only if there are at most c - 1 other processors accessing the same memory module. Each round is executed in a synchronous fashion. We refer to this protocol as the 1 out of l protocol.

We analyze the above process in an equivalent balls-and-bins setup. Let n balls labeled 0 through n - 1 represent the accesses, and n bins labeled 0 through n - 1 represent the memory modules. Each hash function, a random function from [n] to [n], is equivalent to a random throw of n balls uniformly and independently into n bins. Let [h.sup.A] denote the function h with domain restricted to the set A [subset or equal to] [n]. Let [R.sub.i] denote the set of balls remaining after round i. For convenience, define [R.sub.-1] to be the set of balls left before round 0, that is, [R.sub.-1] = [n]. Note that for i [is greater than or equal to] 0, [R.sub.i] is the subset of [R.sub.i-1] given by the following recurrence:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Recall that a bag (or multiset) is an unordered set in which repetition is allowed. For any set A, we define a bag B to be an A-bag if every element of B is also an element of A.

For nonnegative integers m and n, let [F.sub.m,n] denote the set of functions from [m] to [n]. For each f [element of] [F.sub.m,n], note that the bag {f(j) : j [element of] [m]} is an m-size [n]-bag. For convenience, given any f [element of] [F.sub.m,n] and A [subset or equal to] [m], let the term bag f(A) denote the bag {f(x) : x [element of] A}. Hence, the uniform distribution over [F.sub.m,n] induces a probability distribution, which we denote [D.sub.m,n], over the set of all m-size [n]-bags. For any bag B and A [subset or equal to] [n], let [B.sub.A,B] = {[f.sup.A] : f [element of] [F.sub.n,n] and bag f(A) = B}.

Let [S.sub.i] and [T.sub.i] denote the bags [h.sub.i mod l]([R.sub.i-1]) and [h.sub.i mod l]([R.sub.i]), respectively. Let [t.sub.i] = |[T.sub.i]| = |[R.sub.i]| (thus [t.sub.-1] = n) and [s.sub.i] = |[S.sub.i]|. Note that <[t.sub.i]> is a nonincreasing sequence. The protocol terminates after the first round i for which [t.sub.i] = 0. The protocol fails to terminate if and only if [t.sub.i] = [t.sub.i+ l] [is greater than] 0 for some i [is greater than or equal to] - 1. (In such a case, the protocol enters an infinite loop with [t.sub.j] = [t.sub.i] for all j [is greater than or equal to] i.) The goal of our analysis is twofold: (i) to bound the probability that the protocol fails to terminate, and (ii) to analyze the number of rounds required by the protocol when it does terminate. We begin our analysis by establishing some properties of [D.sub.m,n] and [B.sub.A,B].

Let random variable X be drawn from [D.sub.m,n], B be an arbitrary [n]-bag of size m, and [m.sub.i] be the number of copies of element i in B, 0 [is less than or equal to] i [is less than] n. We have:

(1) Pr[X = B] = m!/[m.sub.0!] ... [m.sub.n-1!] [multiplied by] 1/[n.sup.m.].

LEMMA 2.1. Let m and n be integers such that 0 [is less than or equal to] m [is less than] n and assume that X is a random variable drawn from [D.sub.m+1,n]. Let x be an element of X chosen uniformly at random. If Y is the random variable X\{x}, then the probability distribution of Y is [D.sub.m,n].

PROOF. Let B be any m-size [n]-bag and [B.sub.i] = B [union] {i}, 0 [is less than or equal to] i [is less than] n. Let the number of copies of element i in B be [m.sub.i]. (Hence, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].) Using Eq. (1), we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] []

COROLLARY 2.2. Let a, m, and n be integers such that 0 [is less than or equal to] a [is less than or equal to] m [is less than or equal to] n. Let X be a random variable drawn from [D.sub.m,n]. If Y is a random a-size subbag of X, then the probability distribution of Y is [D.sub.a,n].

LEMMA 2.3. Let R be an arbitrary subset of [n] and B be an arbitrary [n]-bag. Let h be a function drawn uniformly at random from [B.sub.R,B.]. For an arbitrary subset A of R, the bag h(A) is a random |A|-size subbag of B.

PROOF. Consider an arbitrary element x [element of] R. Clearly h(x) is a random element of B. Applying this for each element in A, we obtain that the bag h (A) is a random |A|-size subbag of B. []

For any random variable X and any event E which occurs with nonzero probability, let X | E denote the random variable whose probability distribution is the conditional probability distribution of X given E. Using Corollary 2.2 and Lemma 2.3, we prove the following claims related to the 1 out of l protocol.

LEMMA 2.4. Let R be an arbitrary subset of [n] and T be an arbitrary [n]-bag. For all i [is greater than or equal to] 0, if Pr[{[R.sub.i] = R, [T.sub.i] = T}] is nonzero, then the random variable [h.sub.i mod l] | {[R.sub.i] = R, [T.sub.i] = T} is drawn uniformly at random from [B.sub.R,T].

PROOF. The random variable [h.sub.i mod l] is drawn uniformly at random from [F.sub.n,n]. Therefore, given that [R.sub.i] = R and bag [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is drawn uniformly at random from the set of functions whose domain is R and the range, viewed as a bag, is the [n]-bag T. This set of functions is precisely [B.sub.R,T.] []

LEMMA 2.5. For 0 [is less than or equal to] j [is less than] i, let [R.sub.j], and [T.sub.j] be an arbitrary subset of [n], an arbitrary [n]-bag, and an arbitrary integer, respectively, such that [t.sub.j] = |[R.sub.j| = |[T.sub.j]|. Let [S'.sub.i] denote the random variable [S.sub.i]|{[R.sub.j] = [R.sub.j], [T.sub.j] = [T.sub.j], [t.sub.j] = [t.sub.j] 0 [is less than or equal to] j [is less than] i}. Let i be a nonnegative integer and Pr[{[R.sub.j] = [R.sub.j], [T.sub.j] = [T.sub.j], [t.sub.j] = [t.sub.j] : 0 [is less than or equal to] j [is less than] i}] be nonzero. If 0 [is less than or equal to] i [is less than] l, then [S'.sub.i] is drawn from [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]; otherwise, [S'.sub.i] is a [t.sub.i-1]-size random subbag of [T.sub.i-l].

PROOF. By definition, [S.sub.i] equals the bag [h.sub.i mod l]([R.sub.i-1]). If 0 [is less than or equal to] i [is less than] l, then [S'.sub.i] equals the bag [h.i mod l]([R.sub.i-1]) because [h.sub.i mod l] is independent of all events associated with rounds 0 through i - 1. Let C be an arbitrary n-bag and let h' denote the random variable [h.sub.i mod l]|{[h.sub.i mod l]([n]) = C}. The probability distribution of bag [h.sub.i mod l]([n]) is [D.sub.n,n] and hence h' is drawn uniformly at random from [B.sub.[n], C]. Applying Lemma 2.3 with ([n], C, h', [R.sub.i-1]) for (R, B, h, A), we obtain that bag h' ([R.sub.i-1]), that is, [S'.sub.i] |{[h.sub.i mod l]([n]) = C}, is a random [t.sub.i-1]-size subbag of C. Since the preceding statement holds for all C, we apply Corollary 2.2 with ([t.sub.i-1] n, n, [h.sub.i mod l]([n]), [S'.sub.i) for (a, m, n, X, Y) to obtain that [S'.sub.i] is drawn from [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

We now consider the case i [is greater than or equal to] l. Let h" denote the random variable [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Since h" is independent of all events associated with rounds i - l + 1 through i - 1, [S'.sub.i] equals the bag h"([R.sub.i-1]). Applying Lemma 2.4 with (R.sub.i-l], [T.sub.i-l], [T.sub.i-l]) for (R, T, i), we obtain that h" is drawn uniformly at random from [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Applying Lemma 2.3 with ([R.sub.i-l], [T.sub.i-l], h", [R.sub.i-1]) for (R, B, h, A), we obtain that bag h"([R.sub.i-1]), that is [S'.sub.i], is a random [t.sub.i-1]-size subbag of [T.sub.i-l]. []

We are now ready to describe the protocol in terms of the [S.sub.i]'s and [T.sub.i]'s alone. Let RandomBag (m, n) return a bag drawn from [D.sub.m,n] Let RandomSubbag (B, m) return a new bag that is a random m-size subbag of B. Let PrunedBag (B, c) return a bag that contains exactly those elements of S that have more than c copies. By Lemma 2.5, Alg1(n, l, c) describes the random process occuring in the 1-out-of-l protocol on a c-collision n-processor crossbar.

Alg1(n, l, c) (1.1) i := 0; (1.2) repeat (1.3) if i < l then (1.4) [S.sub.i] := RandomBag(|[T.sub.i-1|, n) (1.5) else (1.6) [S.sub.i] := RandomSubbag([T.sub.i-l], |[T.sub.i-1]|); (1.7) [T.sub.i] := PrunedBag([S.sub.i], c); (1.S) i:= i + 1 (1.9) until |[T.sub.i-1]| = 0

In order to analyze Alg1, we will estimate the size of [T.sub.i] after round i. We propose a modified version of the above algorithm that simplifies the estimation of |[T.sub.i]|. Observe that for 0 [is less than or equal to] i [is less than] l, [S.sub.i] is the bag obtained by throwing |[S.sub.i]| balls at random into n bins, and [T.sub.i] is PrunedBag([S.sub.i], c). Below, we present the modified algorithm Alg2(n, l, c) that approximately maintains this invariant after every round, under a suitable redefinition of [S.sub.i]. The analysis in Section 2.3 will make this precise. Alg2 is the same as Alg1 except that Lines (1.5) and (1.6) are replaced by Lines (2.1) through (2.7), stated below.

(2.1) else { (2.2) [S.sub.i], [T.sub.i] := [S.sub.i-l], [T.sub.i-l]; (2.3) while |[T.sub.i| [is greater than] [T.sub.i-1]| { (2.4) "Select x at random from [S.sub.i]"; (2.5) [S.sub.i], [T.sub.i] := [S.sub.i]\{x}, [T.sub.i]\{x} (2.6) } (2.7) };

Since each element x in line (2.4) is selected at random from [S.sub.i], any element selected from [T.sub.i] is also random in [T.sub.i]. Moreover, exactly |[T.sub.i-1]| of the elements from [T.sub.i-l] are retained after the execution of the while loop.

LEMMA 2.6. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (respectively, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) denote bags [S.sub.i], [T.sub.i] in Alg1 (respectively, Alg2) after round i, i [is greater than or equal to] 0. Then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] have the same probability distribution.

PROOF. We use induction on the number of rounds. For the basis, we observe that [T.sub.0], ..., [T.sub.l-1] in Alg1 and Alg2 are obtained in exactly the same way. (Lines (1.5) and (1.6) of Alg1 and the corresponding lines (2.1) through (2.7) of Alg2 are not executed.)

Consider round i [is greater than or equal to] l. By the induction hypothesis [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] have the same probability distribution, 0 [is less than or equal to] j [is less than] i. In Line (1.6), Alg1 computes [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] by selecting a random subbag of size [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] from the subbag [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. In Lines (2.3) through (2.6), Alg2 computes [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] by removing at random elements from [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] until [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] elements are retained from subbag [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Thus [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]-size subbag chosen randomly from [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. By the induction hypothesis, the probability distribution of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (respectively, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) is the same as that of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (respectively, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]). Therefore, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] after Line (1.6) of Alg1 and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] after Line (2.6) of Alg2 have the same probability distribution. Let S' (respectively, T') denote [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (respectively, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) after Line (2.6) of Alg2. Since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] contains all elements of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] with more than c copies, T' contains all elements of S' with more than c copies.

After Line (1.7), [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is the subbag of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] containing all elements with more than c copies, and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is the subbag of S' containing all elements with more than c copies. Since T' contains all elements of S' with more than c copies, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is the subbag of T' containing all elements with more than c copies. Therefore, the probability distribution of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] after round i is the same as that of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] after round i. []

COROLLARY 2.7. The probability that Alg1(n, l, c) terminates after round i, i [is greater than or equal to], 0 is equal to the probability that Alg2(n, l, c) terminates after round i.

In the remainder of this section, we analyze Alg2 under different assignments to the parameters l and c. In Section 2.1, we present some results on large deviations which we use for our analysis. In Section 2.2, we analyze certain "balls and bins" experiments. Section 2.3 uses these results to analyze Alg2(n, l, 1) and Alg2(n, l, 2). Among other results, we show that Alg2(n, 3, 1) and Alg2(n, 2, 2) each terminate in [Theta](log log n) rounds whp. Our analysis can be easily generalized to show that: (i) Alg2(n, l, 1) terminates in [Theta](log log n) rounds whp for any constant l [is greater than or equal to] 3, and (ii) for any c [is greater than or equal to] 2 and any constant l [is greater than or equal to] 2, Alg2(n, l, c) terminates in [Theta](log log n) rounds whp. Section 2.5 presents simple ideas for extending the above results to general a out of b problems.

2.1. LARGE DEVIATIONS. For our analysis, we make frequent use of bounds on the tails of the binomial and hypergeometric distributions.(3)

THEOREM 2.1.1 [CHERNOFF 1952]. Let X be a random variable drawn from B(n, p), that is, X is the number of successes in n independent Bernoulli trials, where each trial succeeds with probability p. Then,

(2) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

(3) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

(4) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

LEMMA 2.1.2. Let S be a set of s balls, T be a subset of S, t = |T|, and p = t/s. Let s' balls be chosen uniformly at random from S, and t' be the random variable representing the number of balls that are chosen from T. Then, for any real [element of] [is greater than or equal to] 0,

Pr[t' [is greater than or equal to] (p + [Epsilon])s'] [is less than or equal to] exp(-2[[Epsilon].sup.2]s'), and

Pr[t' [is less than or equal to] (p - [Epsilon])s'] [is less than or equal to] exp(-2[[Epsilon].sup.2]s').

PROOF. By Chvatal [1979] and Hoeffding [1963],

Pr[t' [is greater than or equal to] (p - [Epsilon])s'] [is less than or equal to] exp(-2[[Epsilon].sup.2]s').

The lower bound on t' can be proved by using the upper bound on s' - t'. Thus,

Pr[t' [is less than or equal to] (p - [Epsilon])s'] = Pr[s' - t' [is greater than or equal to] (1 - p + [Epsilon])s'] [is less an or equal to exp(-2[[Epsilon].sup.2]s'). []

COROLLARY 2.1.3. Let S be a set of s balls, and T be a subset of S, t = |T|. Let s' balls be chosen uniformly at random from S, and t' be the random variable representing the number of balls that are chosen from T. Then,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

PROOF. Apply Lemma 2.1.2 with [Epsilon] = t/(2s [log.sup.3] n). []

LEMMA 2.1.4. Let S be a set of s balls and T be a subset of S, t = |T|. Let s' balls be chosen at random from S, and let t' be the random variable representing the number of balls that are chosen from T. If s't/s [is greater than or equals to] [log.sup.2] n, then t' [is greater than or equal to] s't/(3s) wvhp.

PROOF. Let p = t/s. Consider the s' balls being chosen in s' rounds (one ball in each round). If the number of balls chosen from bag T in rounds 1, ..., i - 1 is less than ps'/3, the probability that a ball from T is chosen in round i is at least 2p/3. Let X be a random variable drawn from B(s', 2p/3). The probability that t' [is greater than or equal to] ps'/3 is at least the probability that X [is greater than or equal to] ps'/3. By Eq. (2), Pr[X [is greater than or equal to] ps'/3] [is greater than or equal to] 1 - exp(-ps'/12). Since ps' [is greater than or equal to] [log.sup.2] n, the lemma is proven. []

In Alg2(n, l, 1), [T.sub.i] is that subbag of [S.sub.i], each element of which has at least 2 copies. We call such elements (as well as the associated balls) nonsingletons. Similarly, in Alg2(n, l, 2) each element of [T.sub.i] has at least 3 copies. We call such elements (as well as the associated balls) nonpairs. In Section 2.3, we show that the probability distribution of [S.sub.i] is approximately [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Thus, in Alg2(n, l, 1) (respectively, Alg2(n, l, 2)) [t.sub.i] is approximately the number of nonsingletons (respectively, nonpairs) in a random bag drawn from [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. In order to get sharp estimates on the number of nonsingletons and nonpairs in a random bag drawn from [D.sub.m,n], we use a martingale analysis. The following two theorems are used to bound large deviations for martingales [Alon and Spencer 1991].

THEOREM 2.1.5 [ALON AND SPENCER 1991]. Let [Omega] = [A.sup.B] denote the set of functions g: B [right arrow] A. Fix a gradation 0 = [B.sub.0] [subset] [B.sub.1] [subset] ... [subset] [B.sub.m] = B. Let L be a function from [Omega] to R. Define a martingale [X.sub.0], ..., [X.sub.m] by setting

[X.sub.i](h) = E[L(g) | g(b) = h(b) for all b [element of] [B.sub.i]].

Assume that for all i, whenever h and h' differ only on [B.sub.i+1] - [B.sub.i], we have |L(h') - L(h)| [is less than or equal to] 1. Then |[X.sub.i+1](h) - [X.sub.i](h)| [is less than or equal to] 1, for all 0 [is less than or equal to] i [is less than] m, h [element of] [Omega].

THEOREM 2.1.6. AZUMA'S INEQUALITY [ALON AND SPENCER 1991]. Let [X.sub.0], ..., [X.sub.k] be a martingale with |[X.sub.i+1] - [X.sub.i]| [is less than or equal to] 1, for all 0 [is less than or equal to] i [is less than] k. Then for real [Lambda] [is greater than] 0,

2.2. LEMMAS ON BALLS AND BINS. In this section, we estimate the number of nonsingletons and nonpairs in a random bag with distribution [D.sub.m.n] using the large deviation bounds mentioned in Section 2.1. By linearity of expectation, the expected number of nonsingletons (respectively, nonpairs) of a random bag X drawn from [D.sub.m,n] is given by f(m, n) (respectively, g(m, n)), where

f(m,n) = m(1 - [(1 - 1/n).sup.m-1]), and

g(m,n) = m(1 - [(1 - 1/n).sup.m-1] - m-1/n [(1 - 1/n).sup.m-2]).

Throughout this section, n will be fixed, so we use f(m) (respectively, g(m)) to denote f(m, n) (respectively, g(m, n)). Lemmas A.1 and A.2 show that f(m) = [Theta]([m.sup.2]/n), and g(m) = [Theta]([m.sup.3]/[n.sup.2]). Let

[Delta] = 1 - 1/[log.sup.3] n, and

[Delta] = 1 + 1/[log.sup.3] n.

We now bound the probability that the number of nonsingletons in a random bag drawn from [D.sub.m, n] deviates from the mean f(m). Lemma 2.2.1 is used to bound deviations to within a o(1) factor for m suitably large, and Lemma 2.2.3 bounds deviations to within a constant factor for all m.

LEMMA 2.2.1. Let m and n be integers such that 3 [is less than or equal to] m [is less than or equal to] n, h: [m] [right arrow] [n] be a random function drawn from [F.sub.m,n], and t(h) be the number of nonsingletons in bag h([m]). If m [is greater than or equal to] [n.sup.2/3] [log.sup.3] n, then [Delta] f(m) [is less than or equal to] t(h) [is less than or equal to] [Delta]f(m) wvhp.

PROOF. Consider the martingale [X.sub.0], ..., [X.sub.m] defined as:

[X.sub.i](h) = E[t(p) | p and h agree on balls in [i]].

If two functions p and p' differ only on ball i, t(p) and t(p') differ by at most 2. We apply Theorem 2.1.5 by scaling the random variable t by 2 and thus obtain, |[X.sub.i+1] - [X.sub.i]| [is less than or equal to] 2. Similarly, after scaling the [X.sub.i]'s by 2, we apply Theorem 2.1.6 to get

(5) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The expected value [X.sub.0] of t, is f(m). For a function h, t(h) is [X.sub.m](h). By Eq. (5) with [Lambda] = f(m)/(2 [square root of m] [log.sup.3] n), we find that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Since f(m) [is greater than or equal to] [m.sup.2]/3n for all m [is greater than] 2,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

For m [is greater than or equal to] [n.sup.2/3] [log.sup.3] n, [m.sup.3]/([72.sup.2] [log.sup.6] n) [is greater than or equal to] ([log.sup.3] n)/72. Therefore, [Delta]f(m) [is less than or equal to] t(p) [is less than or equal to] [Delta]f(m) wvhp. []

COROLLARY 2.2.2. Let m and n be integers such that 3 [is less than or equal to] m [is less than or equal to] n, S be a random bag drawn from [D.sub.m,n], and t be the number of nonsingletons in S. If m [is greater than or equal to] [n.sup.2/3] [log.sup.3] n, then [Delta]f(m) [is less than or equal to] t [is less than or equal to] [Delta]f(m) wvhp.

LEMMA 2.2.3. Let m and n be integers such that 3 [is less than or equal to] m [is less than or equal to] n and S be a random bag drawn from [D.sub.m,n]. Let t represent the number of nonsingletons in S. Then,

(1) The probability that a particular ball is a nonsingleton is at most m/n.

(2) For [square root of n] [log.sup.5] n [is less than or equal to] m [is less than or equal to] n, we have t [is less than or equal to] 4[m.sup.2]/n wvhp.

(3) For m [is less than or equal to] [square root of n] [log.sup.5] n, we have t [is less than or equal to] 4 [log.sup.10] n wvhp.

PROOF. Let the m balls be thrown one-by-one. Since the balls occupy at most m bins, when a ball i is thrown the probability that i falls into a bin that is nonempty before i is thrown (referred to as a "nonempty bin" henceforth in this proof) is at most m/n. Thus, the probability that a particular ball is a nonsingleton is at most m/n. This establishes Part (1) of the lemma.

Let X be the random variable representing the number of balls that fall into nonempty bins. Thus, the number of nonsingletons is at most 2X. Moreover, X is stochastically dominated by the random variable Y drawn from B(m, m/n). The expected value of Y is [m.sup.2]/n.

For m [is greater than or equal to] [square root of n] [log.sup.5]n, we apply Eq. (3) with [Epsilon] = 1, and obtain Pr[Y [is greater than or equal to] 2[s.sup.2]/n] [is less than or equal to] exp(-[m.sup.2]/3n) [is less than or equal to] exp(-([log.sup.10] n)/3). Therefore, the number of nonsingletons is at most 4[m.sup.2]/n wvhp, proving Part (2) of the lemma.

For m [is less than or equal to] [square root of n] [log.sup.5]n, we upper bound t by the number of nonsingletons in a bag drawn from [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. By Part (2), t [is less than or equal to] 4 [log.sup.10] n wvhp, proving Part (3) of the lemma. []

The following two lemmas establish bounds on the number of nonpairs that are analogous to Lemmas 2.2.1 and 2.2.3.

LEMMA 2.2.4. Let m and n be integers such that 6 [is less than or equal to] m [is less than or equal to] n. Let h: [m] [right arrow] [n] be a random function drawn from [F.sub.m,n], and t(h) be the number of nonpairs in bag h([m]). If m [is greater than or equal to] [n.sup.4/5] [log.sup.3]n, then [Delta]g(m) [is less than or equal to] t(p) [is less than or equal to] [Delta]g(m) wvhp.

PROOF. Consider the martingale [X.sub.0], ..., [X.sub.m] defined as:

[X.sub.i](h) = E[t(p) | p and S agree on balls in [i]].

If two functions p and p' differ only on ball i, t(p) and t(p') differ by at most 3. We apply Theorem 2.1.5 by scaling the random variable t by 3 and thus obtain, |[X.sub.i+1] - [X.sub.i]| [is less than or equal to] 3. Similarly, after scaling the [X.sub.i]'s by 3, we apply Theorem 2.1.6 to get

(6) Pr[|[X.sub.m] - [X.sub.0]| [is greater than] 3[Lambda] [square root of m]] [is less than] 2 exp(- [[Lambda].sup.2]/2).

The expected value [X.sub.0] of t, is g(m). For a function h, t(h) is [X.sub.m](h). By Eq. (6) with [Lambda] = g(m)/(3 [square root of m] [log.sup.3] n), we find that

(7) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Since for 6 [is less than or equal to] m [is less than or equal to] n, g(m) [is greater than or equal to] [m.sup.3]/12[n.sup.2],

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

If m [is greater than or equal to] [n.sup.4/5] [log.sup.3] n, [m.sup.5]/(18 [multiplied by] [12.sup.2][n.sup.4] [log.sup.6] n) [is greater than or equal to] ([log.sup.9] n)/18 [multiplied by] [12.sup.2]. Therefore, for m [is greater than] [n.sup.4/5] [log.sup.3] n, [Delta]g(m) [is less than or equal to] t(p) [is less than or equal to] [Delta]g(m) wvhp. []

COROLLARY 2.2.5. Let m and n be integers such that 6 [is less than or equal to] m [is less than or equal to] n, S be a random bag drawn from [D.sub.m,n], and t be the number of nonpairs in S. If m [is greater than or equal to] [n.sup.4/5] [log.sup.3] n, then [Delta]g(m) [is less than or equal to] t [is less than or equal to] [Delta]g(m) wvhp.

LEMMA 2.2.6. Let m and n be integers such that 6 [is less than or equal to] m [is less than or equal to] n, and S be a random bag drawn from [D.sub.m,n]. Let t be the random variable denoting the number of nonpairs in S. Then,

(1) The probability that a particular ball is a nonpair is at most the maximum of 3[m.sup.2]/[n.sup.2] and 3([log.sup.10] n)/n.

(2) For [n.sup.2/3] [log.sup.3] n [is less than or equal to] m [is less than or equal to] n, t is at most 12[m.sup.3]/[n.sup.2] wvhp.

(3) For m [is less than or equal to] [n.sup.2/3] [log.sup.3] n, t is at most 12 [log.sup.9] n wvhp.

PROOF. Let m [is greater than or equal to] [square root of n] [log.sup.5] n. Consider the experiment of throwing balls one-by-one into n bins until either there are 4[m.sup.2]/n nonsingletons or all the m balls have been thrown. Let t' be the number of nonpairs in this experiment. Since by Part (2) of Lemma 2.2.3, the number of nonsingletons in a random bag from [D.sub.m,n] is at most 4[m.sup.2]/n wvhp, when the experiment terminates all the m balls have been thrown wvhp. Therefore, any upper bound on t' wvhp (respectively, whp) is an upper bound on t wvhp (respectively, whp).

During the above experiment, the nonsingletons occupy at most 2[m.sup.2]/n bins. Therefore, when a ball is thrown, the probability that it falls into a bin with nonsingletons (referred to as "nonsingleton bins") is at most 2[m.sup.2]/[n.sup.2]. Thus, the probability that a particular ball is a nonpair is at most 2[m.sup.2]/[n.sup.2] + 1/[n.sup.c] for any real constant c [is greater than or equal to] 0. Since m [is greater than or equal to] [square root of n] [log.sup.5] n, this probability is at most 3[m.sup.2]/[n.sup.2]. This establishes Part (1) of the lemma. (Note that, for m [is less than or equal to] [square root of n] [log.sup.5]n, we can bound the probability by 3[([square root of n] [log.sup.5] n).sup.2]/[n.sup.2] = 3([log.sup.10] n/n.)

Let X be the random variable representing the number of balls that fall into nonsingleton bins. Hence, the number of nonpairs t' is at most 3X. Moreover, the random variable X is stochastically dominated by the random variable Z drawn from B(m, min{1, 2[m.sup.2]/[n.sup.2]}). The expected value of Z is at most 2[m.sup.3]/[n.sup.2].

For m [is greater than or equal to] [n.sup.2/3] [log.sup.3] n, we apply Eq. (3) with [Epsilon] = 1, and obtain Pr[Z [is greater than or equal to] 4[m.sup.2]/n] [is less than or equal to] exp(-2[m.sup.3]/3[n.sup.2]) [is less than or equal to] exp(-(2 [log.sup.9] n)/3). Therefore, t' (and hence t) is at most 12[m.sup.3]/[n.sup.2] wvhp, establishing Part (2) of the lemma.

For m [is less than or equal to] [n.sup.2/3] [log.sup.3] n, we upper bound t by the number of nonpairs in a bag drawn from [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. By Part (2), t [is less than or equal to] 12 [log.sup.9] n wvhp, establishing Part (3) of the lemma. []

2.3. ANALYSIS OF ALG2. In this section, we analyze the number of rounds Alg2 takes before termination. For 0 [is less than or equal to] i [is less than] l, we have [s.sub.i] = [t.sub.i-1]. Corollaries 2.3.2. and 2.3.3 and Lemma 2.3.4 establish bounds on [s.sub.i] in terms of the [s'.sub.j]'s, 0 [is less than or equal to] j [is less than or equal to] i.

LEMMA 2.3.1. In Alg2(n, l, c), let i [is greater than or equal to] l, [s.sub.+] denote [Delta][s.sub.i-l][t.sub.i-1]/[t.sub.i-l] and [s.sub.-] denote [Delta][s.sub.i-l][t.sub.i-1]/[t.sub.i-l]. Then,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

PROOF. In round i, Alg2 removes elements at random from [S.sub.i-l] until [t.sub.i-1] elements are left from the subbag [T.sub.i-l] of [S.sub.i-l]. Hence, Pr[[s.sub.i] [is greater than or equal to] [s.sub.+]] equals the probability that less than [t.sub.i-1] elements are left from [T.sub.i-l] after [s.sub.i-l] - [s.sub.+] elements are removed. This is equal to the probability that less than [t.sub.i-1] elements are chosen from [T.sub.i-l] in a random selection of [s.sub.+] elements from [S.sub.i-l]. Applying Lemma 2.1.3 with (s, t, s') = ([s.sub.i-l], [t.sub.i-l], [s.sub.+]), the desired probability is at most exp [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (Here we use the inequality (1 - 1/(2 [log.sup.3] n))[Delta] [is greater than] 1 for n sufficiently large.)

Similarly, Pr[[s.sub.i] [is less than or equal to] [s.sub.-]] equals the probability that more than [t.sub.i-1] elements are left from [T.sub.i-l] after [s.sub.i-l] - [s.sub.-] elements are removed from [S.sub.i-l]. This is equal to the probability that more than [t.sub.i-1] elements are chosen from [T.sub.i-l] in a random selection of [s.sub.-] elements from [S.sub.i-l]. Applying Lemma 2.1.3 with (s, t, s') = ([s.sub.i-l, [t.sub.i-l], [s.sub.-]), the desired probability is at most exp [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (Here we use the inequality (1 + 1/(2 [log.sub.3] n))[Delta] [is less than or equal to] 1 for n sufficiently large.)

COROLLARY 2.3.2. In Alg2(n, l, c), if i [is greater than or equal to] l, [s.sub.i-l][t.sub.i-1]/[t.sub.i-l] [is greater than or equal to] 2[n.sup.2/3] [log.sup.3] n and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then wvhp,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

PROOF. Let [s.sub.+], [s.sub.-] be as defined in Lemma 2.3.1. By Lemma 2.3.1, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Since [s.sub.+], [s.sub.i-l] [is greater than or equal to] 2[n.sup.2/3] [log.sup.3] n, and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], the right-hand side of the above inequality is at most exp [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Similarly, we can prove the desired lower bound on [s.sub.i] wvhp using the lower bound in Lemma 2.3.1. (Note that [s.sub.-] [is greater than or equal to] 2[Delta][n.sup.2/3] [log.sup.3] n [is greater than or equal to] [n.sup.2/3] [log.sup.3] n for n sufficiently large.) []

COROLLARY 2.3.3. In Alg2(n, l, c), if [s.sub.i-l][t.sub.i-1]/[t.sub.i-l] [is greater than or equal to] 2[n.sup.4/5] [log.sup.3] n and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then wvhp,

[Delta][s.sub.i-l][t.sub.i-1]/[t.sub.i-l] [is less than or equal to] [s.sub.i] [is less than or equal to] [Delta][s.sub.i-l][t.sub.i-1]/[t.sub.i-l]

PROOF. Let [s.sub.+], [s.sub.-] be as defined in Lemma 2.3.1. By Lemma 2.3.1, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Since [s.sub.+], [s.sub.i-l] [is greater than or equal to] 2[n.sup.4/5] [log.sup.3] n and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], the right-hand side of the above inequality is at most exp [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Similarly, we can prove the desired lower bound on [s.sub.i] wvhp using the lower bound in Lemma 2.3.1. (Note that [s.sub.-] [is greater than or equal to] 2[Delta][n.sup.4/5] [log.sup.3] n [is greater than or equal to] [n.sup.4/5] [log.sup.3] n for n sufficiently large.) []

LEMMA 2.3.4. Let i [is greater than or equal to] l. In Alg2(n, l, c), if [t.sub.i-1] [is greater than or equal to] [log.sup.2] n, then [s.sub.i] [is less than or equal to] 3[s.sub.i-l][t.sub.i-1/[t.sub.i-l] wvhp. If [t.sub.i-1] [is less than or equal to] [log.sup.2] n, then [s.sub.i] [is less than or equal to] 3[s.sub.i-l]([log.sup.2] n)/[t.sub.i-l] wvhp.

PROOF. In Alg2, Pr[[s.sub.i] [is less than or equal to] 3[s.sub.i-l][t.sub.i-1]/[t.sub.i-l]] is equal to the probability that more than [t.sub.i-1] elements are selected from [T.sub.i-l] in a random selection of 3[s.sub.i-l][t.sub.i-1]/[t.sub.i-l] elements from [S.sub.i-l]. If [t.sub.i-1] [is greater than or equal to] [log.sup.2] n, then we apply Lemma 2.1.4 with (s, t, s') = ([s.sub.i-l], [t.sub.i-l], 3[s.sub.i-l][t.sub.i-1]/[t.sub.i-l]) to establish that [s.sub.i] [is less than or equal to] 3[s.sub.i-l][t.sub.i-1]/[t.sub.i-l] wvhp. Similarly, Pr[[s.sub.i] [is less than or equal to] 3[s.sub.i-l]([log.sup.2] n)/[t.sub.i-l]] is equal to the probability that more than [t.sub.i-1] elements are selected from [T.sub.i-l] in a random selection of 3[s.sub.i-l]([log.sup.2] n)/[t.sub.i-l] elements from [s.sub.i-l]. If [t.sub.i-1] [is less than or equal to] [log.sup.2] n, then we apply Lemma 2.1.4 with (s, t, s') = ([s.sub.i-l], [t.sub.i-l], 3[s.sub.i-l]([log.sup.2] n)/[t.sub.i-l]) to establish that [s.sub.i] [is less than or equal to] 3[s.sub.i-l]([log.sup.2] n)/ [t.sub.i-l] wvhp. []

We now relate [t.sub.i] to [s.sub.i] for i [is greater than or equal to] l. First, we prove the following lemma.

LEMMA 2.3.5. Let m balls be thrown independently and uniformly at random into n bins and S be the associated random bag. Let balls be removed at random from S until the remaining bag, denoted by S', satisfies a given condition C. Let X denote the set of balls that are nonsingletons, m' denote |S'|, and t' denote |X|. Let condition C be such that there exist integers d and u satisfying d [is less than or equal to] m' [is less than or equal to] u wvhp.

(1) If d, u [is greater than or equal to] [n.sup.2/3] [log.sup.3] n, then [Delta]f(d) [is less than or equal to] t' [is less than or equal to] [Delta]f(u) wvhp.

(2) If u [is greater than or equal to] [square root of n] [log.sup.5] n, then t' [is less than or equal to] 4[u.sup.2]/n wvhp.

(3) If u [is less than or equal to] [square root of n] [log.sup.5] n, then t' [is less than or equal to] 4 [log.sup.10] n wvhp.

(4) For any ball x, Pr[x [element of] X] [is less than or equal to] [u.sup.2]/(mn) + 1/[n.sup.c] for any real constant c [is greater than or equal to] 0.

PROOF. Consider the experiment of removing balls one-by-one at random from S. Let [S.sub.1] (respectively, [X.sub.1]) be the bag (respectively, set of nonsingleton balls) obtained when m - u balls have been removed and [S.sub.2] be the bag obtained when m - d balls have been removed. Therefore, |[S.sub.1]| = u and |[S.sub.2]| = d. Also, [S.sub.2] is a subbag of [S.sub.1]. Wvhp, the condition C occurs after m - u balls are removed and before m - d balls are removed from S. Thus, wvhp, S' is a subbag of [S.sub.1] and a superbag of [S.sub.2]. Let [t.sub.1] (respectively, [t.sub.2]) denote the number of nonsingletons in [S.sub.1] (respectively, [S.sub.2]). Hence, [t.sub.2] [is less than or equal to] t' [is less than or equal to] [t.sub.1] wvhp. Note that, by Corollary 2.2, [S.sub.1] and [S.sub.2] have probability distributions [D.sub.u,n] and [D.sub.d,n], respectively.

(1) If d, u [is greater than or equal to] [n.sup.2/3] [log.sup.3] n, then by Corollary 2.2.2, [t.sub.2] [is greater than or equal to] [Delta]f(d) and [t.sub.1] [is less than or equal to] [Delta]f(u) wvhp, thus establishing Part (1) of the lemma.

(2) If u [is greater than or equal to] [square root of n] [log.sub.5] n, then by Part (2) of Lemma 2.2.3, [t.sub.i] [is less than or equal to] 4[u.sup.2]/n wvhp, thus establishing Part (2) of the lemma.

(3) If u [is less than or equal to] [square root of n] [log.sup.5] n, then by Part (3) of Lemma 2.2.3, [t.sub.1] [is less than or equal to] 4 [log.sup.10] n wvhp. Hence, t' [is less than or equal to] 4 [log.sup.10] n wvhp, thus establishing Part (3) of the lemma.

(4) For any ball x, Pr[x [element of] X] [is less than or equal to] Pr[x [element of] [X.sub.1]] + 1/[n.sup.c] for any c [is greater than or equal to] 0. By symmetry, the probability that x remains when u balls are left is u/m. Since [S.sub.1] is drawn uniformly at random from [D.sub.u,n], by Part (1) of Lemma 2.2.3, Pr[x [element of] [X.sub.1]] [is less than or equal to] (u/m)(u/n) = [u.sup.2]/(mn), thus establishing Part (4) of the lemma. []

COROLLARY 2.3.6. In Alg2(n, l, 1), let i [is greater than or equal to] l and d, u [is greater than or equal to] 0 be integers such that d [is less than or equal to] [s.sub.i] [is less than or equal to] u wvhp. If t' = [t.sub.i], then Parts (1) through (3) of Lemma 2.3.5 hold. Also, for any ball x [element of] [n], the probability that x remains after round i is at most ([u.sup.2]/[n.sup.2]) + 1/[n.sup.c] for any real constant c [is greater than or equal to] 0.

PROOF. Fix integer i [is greater than or equal to] l. Let k = i mod l. Consider the sequence of bags {[S.sub.j l+k] | j [is greater than or equal to] 0} in Alg2. Bag [S.sub.k], is obtained by throwing [t.sub.k+1] (n if k = 0) balls into n bins. Bag [S.sub.jl+k], j [is greater than] 0, is obtained by removing balls at random from [S.sub.(j-1)l+k] until [t.sub.(j-1)l+k-1] balls are left in a particular subbag [T.sub.(j-1)l+k] of [S.sub.(j-1)l+k].

Bag [S.sub.k] can be obtained equivalently the following way: Remove n - [t.sub.k-1] (0 if k = 0) balls at random from a bag S that is randomly drawn from [D.sub.n,n]. Thus each bag [S.sub.jl+k], j [is greater than] 0 ([S.sub.i], in particular), can be viewed as having been obtained from bag S by removing balls at random until a certain condition (say C) holds. For bag [S.sub.i] thus obtained, it is given that d [is less than or equal to] |[S.sub.i]| [is less than or equal to] u wvhp. We invoke Lemma 2.3.5, substituting (S, [S.sub.i], [s.sub.i], t', n, d, u, C) for (S, S', m', t', m, d, u, C), to establish the desired claims. []

Lemma 2.3.7 is the analogue of Corollary 2.3.6 for Alg2(n, l, 2) and can be proved along the same lines.

LEMMA 2.3.7. In Alg2(n, l, 2), let i [is greater than or equal to] l and d, u [is greater than or equal to] 0 be integers such that d [is less than or equal to] [s.sub.i] [is less than or equal to] u wvhp.

(1) If d, u [is greater than or equal to] [n.sup.4/5] [log.sup.3] n, then [Delta]g(d) [is less than or equal to] [t.sub.i] [is less than or equal to] [Delta]g(u) wvhp.

(2) If u [is greater than or equal to] [n.sup.2/3] [log.sup.3] n, then [t.sub.i] [is less than or equal to] [12u.sup.3]/[n.sup.2] wvhp.

(3) If u [is less than or equal to] [n.sup.2/3] [log.sup.3] n, then [t.sub.i] [is less than or equal to] 12 [log.sup.9] n wvhp.

(4) For any x [element of] [n] the probability that x remains after round i is at most max{3[u.sup.3]/[n.sup.3], (u [log.sup.10] n)/[n.sup.2]} + 1/[n.sup.c] for any real constant c [is greater than or equal to] 0. []

2.3.1. ANALYSIS FOR THE 1-COLLISION CROSSBAR. Using the results of Section 2.2, we show that the probability that Alg2(n, l, 1) deviates significantly from the "expected behavior" is polynomially small. Let [s'.sub.i] be defined as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Let [t'.sub.i] = f([s'.sub.i]) for all i [is greater than or equal to] 0. (Note that for all i [is greater than or equal to] 0, [s'.sb.i] is the expected value of [s.sub.i] given that ([s.sub.j], [t.sub.j]) = ([s'.sub.j], [t'.sub.j]) for 0 [is less than or equal to] j [is less than] i. Similarly, [t'.sub.i] is the expected value of [t.sub.i] given that ([s.sub.j], [t.sub.j]) = ([s'.sub.j], [t.sub.j]) for 0 [is less than or equal to] j [is less than] i and [s.sub.i] = [s'.sub.i].)

LEMMA 2.3.1.1. In Alg2(n, l, 1), for all 0 [is less than or equal to] i [is less than or equal to] 5/2 [log.sub.3] log n, if [s'.sub.i] [is greater than or equal to] [4n.sup.2/3] [log.sup.3] n and n is sufficiently large, then wvhp,

(8) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

(9) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

PROOF. We use induction on i. For the basis, i = 0 and [s.sub.0] = n = [s'.sub.0]. By Lemma 2.2.1, [Delta]f(n) [is less than or equal to] [t.sub.0] [is less than or equal to] [Delta]f(n) wvhp. Since [t'.sub.0] = f(n), the desired claims hold for i = 0.

Assume the claim holds for all j [is less than] i. We first establish Eq. (8) from which we then derive Eq. (9). We consider two cases. If i [is less than] l, then [s.sub.i] = [t.sub.i-1]. Since [s.sub.i-1] [is greater than or equal to] [s'.sub.i] [is greater than or equal to] [4n.sup.2/3] [log.sup.3] n, we obtain from the induction hypothesis that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] wvhp. Since [3.sup.i] [is greater than or equal to] 2 [multiplied by] [3.sub.i-1] + 1 for i [is less than] l, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] wvhp.

If i [is greater than or equal to] l, we use Corollary 2.3.2 to bound [s.sub.i]. By the induction hypothesis and using the inequality min{[s'.sub.i-1], [s'.sub.i-l]} [is greater than or equal to] 4[n.sup.2/3] [log.sup.3] n,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and

Substituting appropriate bounds on [s.sub.i-l], [t.sub.i-l], and [t.sub.i-l], we get the following bounds on s = [s.sub.i-l] [t.sub.i-1]/[t.sub.i-l] wvhp:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Since [Delta] [is less than or equal to] [[Delta].sup.-1] and [[Delta].sup.2] [is greater than or equal to] [[Delta].sup.1] for n sufficiently large, we have

(10) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Since [3.sup.l] [is greater than or equal to] 2 [multiplied by] [3.sup.l-1] + 9 for l [is greater than or equal to] 3, we have [3.sup.i] [is greater than or equal to] 2 [multiplied by] [3.sup.i-1] + 3 [multiplied by] [3.sup.i-l] + 2. Therefore, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] wvhp. Since i [is less than or equal to] 5/2 [log.sub.3] log n, we have [3.sup.i] [is less than or equal to] [log.sup.5/2] n. Hence, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [is greater than or equal to] [Alpha] for any real [Alpha] [is less than] 1 for n sufficiently large. We thus have s [is greater than or equal to] 2[n.sup.2/3] [log.sup.3] n. We next show that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] wvhp. By the induction hypothesis, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] wvhp. Since f([s'.sub.i-l]) [([s'.sub.i-l]).sup.2]/3n and [s.sub.i-l] [is less than or equal to] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] wvhp, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

wvhp. In the last step, we use [Delta] [is less than or equal to] [[Delta].sup.-1]. For any real [Alpha] [is less than] 1, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [is greater than or equal to] a for [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [is greater than or equal to] [Alpha] for n sufficiently large. Therefore, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [is greater than or equal to] 3/4 for n sufficiently large and thus it follows that [t.sub.i-l] [is greater than or equal to] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] wvhp.

We now apply Corollary 2.3.2 to obtain [Delta]s [is less than or equal to] [s.sub.i] [is less than or equal to] [Delta]s wvhp. By Eq. (10), wvhp,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Since for l [is greater than or equal to] 3, [3.sup.l] [is greater than or equal to] 2 [multiplied by] [3.sup.l-1] + 9, we have [3.sub.i-1] - 5 [multiplied by] [3.sup.i-l] + 4 and [3.sup.i] [is greater than or equal to] 2 [multiplied by] [3.sup.i-1] + 3 [multiplied by] [3.sup.i-l] + 3. Since [s'.sub.i] = [s'.sub.i-l] [t'.sub.i-1]/[t'.sub.i-l], Eq. (8) holds wvhp.

We now invoke Part (1) of Corollary 2.3.6 to obtain bounds on [t.sub.i]. Note that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [is greater than or equal to] [n.sup.2/3] [log.sup.3] n for n sufficiently large. Thus, wvhp,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and hence by Corollary A.4,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Since [t'.sub.i] = f([s'.sub.i]), Eq. (9) follows wvhp. []

Lemma 2.3.1.1 implies that we can analyze Alg2(n, l, 1) by studying how [s'.sub.i] decreases as i increases.

LEMMA 2.3.1.2. For all 0 [is less than or equal to] i [is less than] l, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and for i [is greater than or equal to] l, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

PROOF. For 0 [is less than or equal to] i [is less than] l, the desired claim follows directly from the definition of [s'.sub.j], 0 [is less than or equal to] j [is less than] i + 1. Observe that for i = l - 1, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We use this equality as a basis for the case i [is greater than or equal to] l. Assume that for l - 1 [is less than or equal to] k [is less than] i, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Then,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] []

LEMMA 2.3.1.3. For all 1 [is less than or equal to] i [is less than] l, if [s'.sub.i-l] and n are sufficiently large, then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

For i [is greater than or equal to] l, if [s'.sub.i-1] and n are sufficiently large, then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

PROOF. By Lemma 2.3.1.2 and Lemma A.1, if [s'.sub.i-1] and n are sufficiently large, then for all 0 [is less than or equal to] i [is less than] l, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and the claim of the lemma follows after dividing by [s'.sub.0] [[Pi].sub.0 [is less than or equal to] j [is less than] i] [s'.sub.j] By Lemma 2.3.1.2 and Lemma A.1, if [s'.sub.i-1] and n are sufficiently large, then for all i [is greater than or equal to] 0, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and the claim of the lemma follows after dividing by [s'.sub.0] [[Pi].sub.i-l+1 [is less than or equal to] j [is less than] i] [s'.sub.j]. []

Lemma 2.3.1.3 can be used to analyze Alg2(n, l, 1) for any i [is greater than] 2. Let [w.sub.i] = [log.sub.r](n/[s.sub.i]) and [w'.sub.i] = [log.sub.r](n/[s'.sub.i]), where r = n/f(n). (Note that e/(e - 1) [is less than or equal to] r [is less than or equal to] 2 for all n [is greater than or equal to] 2.)

LEMMA 2.3.1.4. In Alg2(n, 3, 1), for all i [is greater than] 0, if [s'.sub.i-l] [is less than or equal to] 3, then [w'.sub.i-2] + [w'.sub.i-1] [is less than or equal to] [w'.sub.i] [is less than or equal to] [w'.sub.i-2] + [w'.sub.i-1] + 2 [log.sub.r] 3.

PROOF. Follows directly from the definition of [w'.sub.i] and Lemma 2.3.1.3. []

We are now ready to place a bound on the number of rounds taken by Alg2(n, l, 1) before termination. We first show that for l [is greater than or equal to] 3, Alg2(n, l, 1) terminates in O(log log n) rounds whp. To prove this upper bound, it is enough to consider the case l = 3. The upper bound for l [is greater than] 3 follows from the bound for l = 3.

LEMMA 2.3.1.5. In Alg2(n, 3, 1), for all i [is greater than] 0, if [s'.sub.i-1] and n are sufficiently large, then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where [p.sub.1] [is greater than] 1 satisfies the following inequality:

(11) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

PROOF. The proof is by induction on i. For the induction basis, i is 1. We have [s'.sub.1] = n/r, hence = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Let the claimed lower bound on [w'.sub.i] hold for all 0 [is less than] j [is less than] i, i [is greater than] 1. By Lemma 2.3.1.4 and the induction hypothesis,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

It thus follows from Eq. (11) that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. []

We now place an upper bound on the number of rounds taken by Alg2(n, 3, 1) before termination.

LEMMA 2.3.1.6. There exists an integer j = O(log log n) such that [s.sub.j] [is less than or equal to] [n.sup.2/5] wvhp in Alg2(n, 3, 1).

PROOF. Let [Phi] = (1 + [square root of 5])/2. Since [[Phi].sup.2] - [Phi] - 1 = 0, Lemma 2.3.1.5 implies that [w'.sub.i] [is greater than or equal to] [[Phi].sup.i-1] for all i [is greater than] 0. Let

k = min { i : [w'.sub.i] [is greater than or equal to] [log.sub.r] ([n.sup.1/3]/4 [log.sup.3] n)}.

For

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Therefore,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Also note that since [w'.sub.2] [is less than or equal to] 1 + 2 [log.sub.r] 3, k [is greater than or equal to] 3 for n sufficiently large.) Since [[Phi].sup.5/2] [is greater than] 3, k [is less than or equal to] 5/2 [log.sub.3] log n for n sufficiently large. Thus, Eqs. (8) and (9) of Lemma 2.3.1.1 hold for all i [is less than] k. (Also note that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [is less than or equal to] 4[n.sup.2/3] [log.sup.3] n.)

By Lemma 2.3.1.1, [t.sub.k-1] [is greater than or equal to] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] wvhp. Since [t'.sub.k-1] = f([s'.sub.k-1]) [is greater than or equal to] [([s'.sub.k-1]).sup.2]/3n, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

wvhp for n sufficiently large. By Lemma 2.3.4, [s.sub.k] [is less than or equal to] 3[s.sub.k-3] [t.sub.k-1]/[t.sub.k-3] wvhp. Substituting appropriate bounds on [s.sub.k-3], [t.sub.k-3], and [t.sub.k-1] from Lemma 2.3.1.1, we have wvhp

(12) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The last step follows from the inequality [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [is less than] [Alpha] for any real [Alpha] [is less than] 1 and for n sufficiently large. We consider two cases depending on the value of [s'.sub.k].

Case 1. [s'.sub.k] [is less than or equal to] [square root of n] [log.sup.5]n. By Eq. (12), [s.sub.k], [is less than or equal to] 4 [square root of n] [log.sup.5] n wvhp. Therefore, by Part (3) of Lemma 2.3.5, [t.sub.k] [is less than or equal to] 64 [log.sup.10] n wvhp. We consider two cases. If [t.sub.k] [is greater than or equal to] [log.sup.2] n, by Lemma 2.3.4, [s.sub.k+1] [is less than or equal to] 3 [s.sub.k-2] [t.sub.k-2] wvhp. If [t.sub.k] [is less than or equal to] [log.sup.2] n, then [s.sub.k+1] [is less than or equal to] 3[s.sub.k-2] [log.sup.2] n/[t.sub.k-2]. In any case, [s.sub.k+1] [is less than or equal to] (192[s.sub.k-2] [log.sup.10] n)/[t.sub.k-2] wvhp. We now substitute appropriate bounds on [s.sub.k-2] and [t.sub.k-2] from Lemma 2.3.1.1 and obtain that wvhp,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for n sufficiently large. (Note: The third step follows from the inequalities [3.sup.k] [is greater than or equal to] 5 [multiplied by] [3.sup.k-2] + 2 and [s'.sub.k-2] [is greater than or equal to] 4[n.sup.2/3] [log.sup.3] n.)

Case 2. [s'.sub.k] [is greater than or equal to] [square root of n] [log.sup.5] n. By Eq. (12), [s.sub.k] [is less than or equal to] 4 [s'.sub.k] wvhp. We again consider two cases, depending on whether [t.sub.k] [is less than or equal to] [log.sup.2] n or [t.sub.k] [is greater than or equal to] [log.sup.2] n.

If [t.sub.k] [is less than or equal to] [log.sup.2] n, then Lemma 2.3.4 implies that [s.sub.k+1] [is less than or equal to] 3 [s.sub.k-2] [log.sup.2] n/[t.sub.k-2] wvhp. Arguing as in Case 2, [s.sub.k+1] is at most [n.sup.2/5] wvhp.

If [t.sub.k] [is less than or equal to] [log.sup.2] n, then Lemma 2.3.4 implies that [s.sub.k+1] [is less than or equal to] 3 [s.sub.k-2] [t.sub.k]/[t.sub.k-2] wvhp. Since [s.sub.k] [is less than or equal to] 4 [s'.sub.k], by Part 2 of Lemma 2.3.5, [t.sub.k] [is less than or equal to] 64[([s'.sub.k]).sup.2]/n [is less than or equal to] 192 [t.sub.k] wvhp. Substituting this upper bound on [t.sub.k] and appropriate bounds on [s.sub.k-2] and [t.sub.k-2] obtained from Lemma 2.3.1.1, we have [s.sub.k+1] [is less than or equal to] 1000 [s'.sub.k+1] wvhp for n sufficiently large. We now derive an upper bound on [s'.sub.k+1].

By Lemma 2.3.1.4,

[w'.sub.k] [is less than or equal to] [w'.sub.k-1] + [w'.sub.k-2] + 2 [log.sub.r] 3.

Since [w'.sub.k-1] [is greater than or equal to] [w'.sub.k-2], we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Thus, by Lemma 2.3.1.4,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for n sufficiently large. We now apply an analysis similar to Case 2 with k replaced by k + 1 to establish that [s.sub.k+2] is at most [n.sup.2/5] wvhp.

Cases 1 and 2 establish that after j = k + 2 = O(log log n) rounds, [s.sub.j] is at most [n.sup.2/5] wvhp. []

LEMMA 2.3.1.7. For any ball x [element of] [n], the probability that x remains after O(log log n) rounds of Alg2(n, 3, 1) is at most 2/[n.sup.6/5] for n sufficiently large.

PROOF. By Lemma 2.3.1.6, after j = O(log log n) rounds, [s.sub.j] [is less than or equal to] [n.sup.2/5] wvhp. By Corollary 2.3.6, the probability that x remains after round j is at most 2[n.sup.4/5]/[n.sup.2] for n sufficiently large. Since 2[n.sup.4/5]/[n.sup.2] = 2/[n.sup.6/5], the desired claim follows. []

The following theorem is an easy consequence of the above lemma.

THEOREM 2.3.1.8. Alg2(n, 3, 1) terminates in O(log log n) rounds whp.

COROLLARY 2.3.1.9. For l [is greater than or equal to] 3, Alg2(n, l, 1) terminates in O(log log n) rounds whp.

We now establish a lower bound on the number of rounds taken by Alg2(n, l, 1) before termination. We first place an upper bound on [w'.sub.i] that complements the lower bound of Lemma 2.3.1.5. (Note that the following lemma applies for all l, while l equals 3 in Lemma 2.3.1.5.)

LEMMA 2.3.1.10. In Alg2(n, l, 1) for all i [is greater than] 0, if [s'.sub.i-1] and n are sufficiently large, then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where [p.sub.2] [is greater than] 1 satisfies the following inequality:

(13) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

PROOF. We first note that [w'.sub.0] = 0. The proof of the lemma is by induction on i. For the induction basis, i = 1. We have [s'.sub.1] = n/r, and hence [w'.sub.1] = 1 = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Let the claimed upper bound on [w'.sub.i] hold for all 0 [is less than] j [is less than] i, i [is greater than] 1. By Lemma 2.3.1.4 and the induction hypothesis, we have:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

By Eq. (13) and the inequality [p.sub.2] [is greater than] 1.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

This completes the proof of the desired claim. []

THEOREM 2.3.1.11. For any l [is greater than or equal to] 3, Alg2(n, l, 1) terminates in [Omega](log log n) rounds wvhp.

PROOF. One solution to Eq. (13) is [p.sub.2] = 2 [log.sub.r]3 + 1 = O(1). Thus, by Lemma 2.3.1.5, [w'.sub.i] [is less than or equal to] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for all i [is greater than] 0. After [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] rounds, [w'.sub.k]] [is less than or equal to] ([log.sub.r n])/4 and [s'.sub.k] [is greater than or equal to] [n.sup.3/4]. For n sufficiently large, [n.sup.3/4] [is greater than or equal to] 4[n.sup.2/3] [log.sup.3] n. Therefore, by Lemma 2.3.1.1, [t.sub.k] [is greater than or equal to] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for n sufficiently large. This shows that Alg2(n, l, 1) executes at least [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (([log.sub.r] n)/4) [is greater than or equal to] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] rounds before termination. []

The recurrence in Lemma 2.3.1.3 for l = 2 yields [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for all i [is greater than or equal to] 0. Thus [w'.sub.i] = O(i). Using an analysis similar to the above theorem we establish an [Omega](log n) lower bound for Alg2(n, 2, 1).

THEOREM 2.3.1.12. Alg2(n, 2, 1) terminates in [Omega](log n) rounds wvhp.

2.3.2. ANALYSIS FOR THE 2-COLLISION CROSSBAR. The analysis of Alg2 with the collision factor set to 2 is similar to the 1-collision case. Analogous to Section 2.3.1 we define [s'.sub.i] as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

For all i [is greater than or equal to] 0, let [t'.sub.i] = g([s'.sub.i]).

LEMMA 2.3.2.1. Let c be the positive root of [c.sup.2] = 4c + 13. In Alg2(n, l, 2),for all 0 [is less than or equal to] i [is less than or equal to] (11/4) [log.sub.c] log n, if [s'.sub.i] [is greater than or equal to] 4[n.sup.4/5] [log.sup.3] n, then wvhp,

(14) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

(15) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

PROOF. We use induction on i. For the basis, i = 0 and [s.sub.0] n [s'.sub.0]. By Corollary 2.2.4, [Delta]g(n) [is less than or equal to] to [is less than or equal to] [Delta]g(n) wvhp and since [t'.sub.0] = g(n), the desired claims hold for i = 0.

Assume the claim holds for all j [is less than] i, i [is greater than or equal to] 1. We first establish Eq. (14), from which we then derive Eq. (15). We consider two cases: i [is less than] l and i [is greater than or equal to] l.

If i [is less than] l, then [s'.sub.i] = [t.sub.i-1] and [s'.sub.i] = [t'.sub.i-1]. Since [S'.sub.i-1] [is greater than or equal to] [s'.sub.i] [is greater than or equal to] 4[n.sup.4/5] [log.sup.3] n, by the induction hypothesis, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] wvhp. Since c [is greater than or equal to] 5, we have [c.sup.i] [is greater than or equal to] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for all i [is greater than or equal to] 1. Hence, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] wvhp. If i [is greater than or equal to] l, we use Corollary 2.3.3 to bound [s.sub.i]. By the induction hypothesis, since [s'.sub.i-1], [s'.sub.i-l] [is greater than or equal to] 4[n.sup.4/5] [log.sup.3] n, we have wvhp,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Substituting appropriate bounds on [s.sub.i-l], [t.sub.i-l], and [t.sub.i-1], we obtain the following bounds on [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] wvhp:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Since [Delta] [is less than or equal to] [[Delta].sup.-1], and [[Delta].sup.2] [is greater than or equal to] [[Delta].sup.-1] we have

(16) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Since l [is greater than or equal to] 2, we have [c.sup.l] [is greater than or equal to] 4[c.sup.l-1] + 13. Hence, [c.sup.i] [is greater than or equal to] 4[c.sup.i-1] + 5[c.sup.i-l] + 2. Therefore, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] wvhp. Since i [is less than or equal to] (11/4)[log.sub.c] log n, we have [c.sup.i] [is less than or equal to] [log.sup.11/4]n and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for any real [Alpha] [is less than] 1 for n sufficiently large. Hence, s [is greater than or equal to] 2[n.sup.4/5] [log.sup.3] n wvhp. We next show that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] wvhp. By the induction hypothesis, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] wvhp. Since g([s'.sub.i-l]) [is greater than or equal to] [([s'.sub.i-l]).sup.3]/12[n.sup.2] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] wvhp, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

wvhp. For any real [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for n sufficiently large. Therefore, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for n sufficiently large and thus [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] wvhp.

We now apply Corollary 2.3.3 to obtain [Delta]s [is less than or equal to] [s.sub.i] [is less than or equal to] [[Delta].sub.s] wvhp. By Eq. (16),

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Since [c.sup.l] [is greater than or equal to] 4[c.sup.l-1] + 13, we have [c.sup.i] [is greater than or equal to] 4[c.sup.i-1] + 5[c.sup.i-l] + 3 and [c.sup.i] [is greater than or equal to] 4[c.sup.i-1] + 9[c.sup.i-l] + 4. Hence, Eq. (8) holds wvhp.

We now invoke Part (1) of Lemma 2.3.7 to obtain bounds on [t.sub.i]. Note that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] n for n sufficiently large. Thus, wvhp,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and hence by Corollary A.6,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Since [t'.sub.i] = g([s'.sub.i]), Eq. (9) follows wvhp. []

Lemmas 2.3.2.2 and 2.3.2.3 determine the rate at which [s'.sub.i] decreases with increasing i. Using Lemma 2.3.2.1, we can then determine the rate of change of [s.sub.i] as i increases.

LEMMA 2.3.2.2. For all 0 [is less than or equal to] i [is less than] l, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and for i [is greater than or equal to] l, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

PROOF. Similar to the proof of Lemma 2.3.1.2. []

LEMMA 2.3.2.3. For all 1 [is less than or equal to] i [is less than] l, if [s'.sub.i-1] and n are sufficiently large, then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

For i [is greater than or equal to] l, if [s'.sub.i-1] and n are sufficiently large, then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

PROOF. By Lemma 2.3.2.2 and Lemma A.2, if [s'.sub.i-1] and n are sufficiently large, then for all 0 [is less than or equal to] i [is less than] l, we have

and the claim of the lemma follows after dividing by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. By Lemma 2.3.1.2 and Lemma A.2, if [s'.sub.i-1] and n are sufficiently large, then for all i [is greater than or equal to] 0, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and the claim of the lemma follows after dividing by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. []

Let [w.sub.i] = [log.sub.r](n/[s.sub.i]) and [w'.sub.i] = [log.sub.r](n/[s'.sub.i]), where r = n/g(n). (Note that e/(e - 2) [is less than or equal to] r [is less than or equal to] 9 for n [is greater than or equal to] 3.)

LEMMA 2.3.2.4. In Alg2(n, 2, 2),for all i [is greater than] O, if [s'.sub.i-1] [is greater than or equal to] 6, then

2[w'.sub.i-1] [is less than or equal to] [w'.sub.i] [is less than] 2[w'.sub.i-l] + [log.sub.r] 12.

PROOF. Follows directly from the definition of [w'.sub.i] and Lemma 2.3.2.3. []

We are now ready to place a tight bound on the number of rounds taken by Alg2(n, l, 2) before termination. We first show that Alg2(n, 2, 2) terminates in O(log log n) rounds whp. The upper bound for l [is greater than] 2 follows from the bound for l = 2.

LEMMA 2.3.2.5. In Alg2(n, 2, 2),for all i [is greater than]l 0, if [s'.sub.i-1] and n are sufficiently large, then [w'.sub.i] [is greater than or equal to] [2.sup.i-1].

PROOF. The proof is by induction on i. For the induction basis, i = 1. We have [s'.sub.1] = n/r; hence, [w'.sub.1] = 1 = [2.sup.0]. Let the claimed lower bound on [w'.sub.i] hold for all 0 [is less than] j [is less than] i, i [is greater than] 1. By Lemma 2.3.1.4 and the induction hypothesis, [w'.sub.i] [is greater than or equal to] 2 [multiplied by] [2.sup.i-2] = [2.sup.i-1]. []

We now place an upper bound on the number of rounds taken by Alg2(n, 2, 2) before termination.

LEMMA 2.3.2.6. There exists an integer j = O(log log n) such that [s.sub.j] [is less than or equal to] [n.sup.5/8] wvhp in Alg2(n, 2, 2).

PROOF. By Lemma 2.3.2.5, [w'.sub.i] [is greater than or equal to] [2.sup.i-1] for all i [is greater than] 0. Let k = min{i: [w'.sub.i] [is greater than or equal to] [log.sub.r] [n.sup.1/3]/(4 [log.sup.3] n)}. Therefore, k [is less than or equal to] ?? log [log.sub.r] [n.sup.1/5]/(4 [log.sup.3] n)?? + 1 [is less than or equal to] log [log.sub.r] [n.sup.1/5]/(4 [log.sup.3] n) + 2. (Also note that since [w'.sub.1] = 1, we have k [is greater than or equal to] 2 for n sufficiently large.) Now we apply Lemma 2.3.2.1 with l = 2. Let [Alpha] be the positive root of the equation [[Alpha].sup.2] = 4[Alpha] + 13. Since [2.sup.11/4] [is greater than] [Alpha], k [is less than or equal to] ,(11/4)[log.sub.[Alpha]], [log.sub.r] n for n sufficiently large. Therefore, by Lemma 2.3.2.1, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] wvhp. Since [t'.sub.k-1] [is greater than or equal to] [(s'.sub.k-1]).sup.3]/(12[n.sup.2]), we have [t.sub.k-1] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] n for n sufficiently large. By Lemma 2.3.4, [s.sub.k] [is less than or equal to] 3[s.sub.k-2] [t.sub.k-1]/[t.sub.k-2] wvhp. Substituting the appropriate bounds on [s.sub.k-2], [t.sub.k-1], and [t.sub.k-2] given by Lemma 2.3.2.1, we have wvhp,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Since [[Alpha].sup.2] = 4[Alpha] + 13, we have [[Alpha].sup.k] [is greater than or equal to] 4[[Alpha].sup.k-1] + 9[[Alpha].sup.k-2] + 3. Therefore,

(17) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

wvhp for n sufficiently large.

We consider two cases, depending on whether [t.sub.k] [is less than or equal to] [log.sup.2] n or [t.sub.k] [is greater than] [log.sup.2] n.

If [t.sub.k] [is less than or equal to] [log.sup.2] n, then by Lemma 2.3.4, [s.sub.k+1] [is less than or equal to] 3[s.sub.k-1] [log.sup.2] n/[t.sub.k-1] wvhp. Substituting appropriate bounds on [s.sub.k-1] and [t.sub.k-1] given by Lemma 2.3.2.1, we have wvhp,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for n sufficiently large. (The second step follows from the lower bound on [t'.sub.k-1] given by Lemma A.2. In the third step, we use [s'.sub.k-1] [is greater than or equal to] [n.sup.4/5] [log.sup.3] n. And in the fourth step, we use [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] 2 for n sufficiently large.)

If [t.sub.k] [is greater than] [log.sup.2] n, then by Lemma 2.3.4, [s.sub.k+1] [is less than or equal to] 3[s.sub.k-1][t.sub.k]/[t.sub.k-1] wvhp. If [s'.sub.k] [is less than or equal to] ([n.sup.2/3] [log.sup.3] n)/4, then since [s.sub.k] [is less than or equal to] 4[s'.sub.k] wvhp, by Part (3) of Lemma 2.3.7, [t.sub.k] [is less than or equal to] 12 [log.sup.9] n wvhp. Hence, as in the case [t.sub.k] [is less than or equal to] [log.sup.2] n above, we can establish that [t.sub.k+1] is zero whp. If [s'.sub.k] [is greater than or equal to] ([n.sup.2/3] [log.sup.3] n)/4, then by Lemma 2.3.7, [t.sub.k] [is less than or equal to] 768[([s'.sub.k-1]).sup.3]/[n.sup.2] wvhp. Therefore, by Lemma A.2, [t.sub.k] [is less than or equal to] 12 [multiplied by] 768[t'.sub.k],. Substituting this bound on [t.sub.k] and appropriate bounds on [s.sub.k-1] and [t.sub.k-1] given by Lemma 2.3.2.1, we have wvhp,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

By Lemma 2.3.2.4 with l = 2, [w'.sub.k+1] [is greater than or equal to] 2[w'.sub.k+1]. Thus

[w'.sub.k+1] [is greater than or equal to] 2 [log.sub.r]([n.sup.1/5]/4 [log.sup.3] n),

and

[s'.sub.k+1] [is less than or equal to] 16[n.sup.3/5] [log.sup.6] n.

Hence, [s.sub.k+1] [is less than or equal to] [n.sup.5/8] for n sufficiently large. []

In Lemma 2.3.2.7 we place a bound on the probability that a particular ball remains after O(log log n) rounds.

LEMMA 2.3.2.7. For any ball x [element of] [n], the probability that x remains after O(log log n) rounds of Alg2(n, 3, 1) is at most 4/[n.sup.9/8] for n sufficiently large.

PROOF. By Lemma 2.3.2.6, after j = O(log log n) rounds, [s.sub.j] [is less than or equal to] [n.sup.5/8] wvhp. By Part 4 of Lemma 2.3.7, the probability that x remains after round j is at most 4[n.sup.15/8]/[n.sup.3] for n sufficiently large. Since 4.[n.sup.15/8]/[n.sup.3] = 4/[n.sup.9/8], the desired claim follows. []

The next theorem follows easily from Lemma 2.3.2.7.

THEOREM 2.3.2.8. Alg2(n, 2, 2) terminates in O(log log n) rounds whp.

We now establish a lower bound on the number of rounds taken by Alg2(n, l, 2) before termination. We first place a upper bound on [w'.sub.i] that complements the lower bound of Lemma 2.3.2.5. The proof of the following lemma is similar to that of Lemma 2.3.1.10 and is omitted.

LEMMA 2.3.2.9. In Alg2(n, l, 2) for all i [is greater than] 0, if [s'.sub.i-1] and n are sufficiently large, then [w'.sub.i] [is less than or equal to] [p.sup.i-1], where p [is greater than] 1 satisfies the following inequality:

(18) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

THEOREM 2.3.2.10. For all l [is greater than or equal to] 1, Alg2(n, l, 2) terminates in [Omega](log log n) rounds wvhp.

PROOF. One solution to Eq. (18) is p = [log.sub.r] 12 = O(1). Therefore, by Lemma 2.3.2.5, [w'.sub.i] [is less than or equal to] [p.sup.i-1] for all i [is greater than] 0. After k = ??[log.sub.p](([log.sub.r] n)/6)??, rounds [w'.sub.k] [is less than or equal to] ([log.sub.r] n)/6, and [s'.sub.k] [is greater than or equal to] [n.sup.5/6]. For n sufficiently large [n.sup.5/6] [is greater than or equal to] 4[n.sup.4/5] [log.sup.3] n. Therefore, by Lemma 2.3.2.1, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] wvhp for n sufficiently large. (Here [Alpha] is the positive root of [[Alpha].sup.2] = 4[Alpha] + 13. Note that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for n sufficiently large.) This shows that Alg2(n, 2, 2) executes at least ??[log.sub.p](([log.sub.r] n)/6)?? [is greater than or equal to] ??[log.sub.p](([log.sub.9] n)/6)?? = [Omega](log log n) rounds wvhp before termination. []

2.4. LIMITED INDEPENDENCE. In this section, we analyze the 1 out of l protocol when the l hash functions are chosen from a k-wise independent family of hash functions. We show that for any c-collision crossbar, the probability that a particular memory request remains after r rounds of the k-wise independent 1 out of l protocol is close to that of the fully independent protocol for r = O(log log n), even when k [much less than] n. Importing the results in Lemmas 2.3.1.7 and 2.3.2.7, we obtain the following main theorems.

THEOREM 2.4.1. For integers l [is greater than or equal to] 3 and c [is greater than or equal to] 1, the 1 out of l problem is solved on a c-collision crossbar in O(log log n) rounds whp, when the l hash functions are chosen independently and uniformly at random from a k-wise independent family of hash functions for any k = [Omega]([log.sup.[Alpha]] n), where [Alpha] is a real constant chosen sufficiently large.

THEOREM 2.4.2. For integers l [is greater than or equal to] 2 and c [is greater than or equal to] 2, the 1 out of l problem is solved on a c-collision crossbar in O(log log n) rounds whp, when the l hash functions are chosen independently and uniformly at random from a k-wise independent family of hash functions for any k = [Omega]([log.sup.[Alpha]] n) where [Alpha] is a real constant chosen sufficiently large.

Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] denote a k-wise independent family of functions from [m] to [n]. That is, for {[x.sub.i]: i [element of] [j]} [subset or equal to] [m], [y.sub.0], ..., [y.sub.l-1] [element of] [[n].sup.j], j [element of] [k + 1], it holds that if h is drawn uniformly at random from k [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then

Pr[h([x.sub.i]) = [y.sub.i] for all i in [j]] = 1/[n.sup.j].

If k [is less than or equal to] [square root of n], [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] can be constructed as in Karp et al. [1992] using the families [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] defined in Carter and Wegman [1979] and Siegel [1989], respectively. (Here d is an appropriate constant.) A hash function h chosen uniformly at random from [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is defined as r ?? s, where r and s are chosen uniformly at random from [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], respectively. Both r and s can be evaluated in constant time [Siegel 1989; Carter and Wegman 1979], and hence the same is true of h.

In order to analyze the 1 out of l protocol, we restrict our attention to the at most n memory requests of the processors. The hash functions with the domain restricted to this set of requests can be viewed as mapping m [is less than or equal to] n memory locations into n memory modules k-wise independently. First, we establish a few simple properties of k-wise independent hash functions.

LEMMA 2.4.3. Let k, m, and n be integers such that 0 [is less than] k [is less than or equal to] m [is less than or equal to] n. Let h be drawn uniformly at random from [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. For any A [subset or equal to] [n], |A| [is less than or equal to] (k - 1)/[e.sup.2], we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

PROOF. If k is even, let k' = k; otherwise, let k' = k - 1. By inclusion-exclusion we have:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

(In the seventh step, we use the inequalities 1 - x [is greater than or equal to] exp(-2x) for 0 [is less than or equal to] x [is less than or equal to] 1/2 and |A| [is less than or equal to] k'/[e.sup.2] [is less than or equal to] n/2. The last step follows since |A| [is less than or equal to] k'/[e.sup.2].) []

LEMMA 2.4.4. Let k, m, and n be integers such that 0 [is less than] k [is less than or equal to] m [is less than or equal to] n. Let h be drawn uniformly at random from [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Let B [subset or equal to] [n] satisfy |B| [is less than or equal to] k/[Beta] for some real [Beta] [is greater than] 0. If S = [h.sup.-1](B), then Pr[|S| [is greater than equal to] [Beta]|B|] [is less than or equal to] [(e/[Beta]).sup.[Beta]|B|].

PROOF. By the definition of S, Pr[|S| [is greater than equal to] [Beta]|B|] is the probability that there exists a set T [subset or equal to] [m], |T| = [Beta]|B|, such that h(T) [subset or equal to] B. Since [Beta]|B| [is less than or equal to] k and h is chosen uniformly from a k-wise independent family of hash functions, the desired probability is at most [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. []

COROLLARY 2.4.5. Let k, m, n, and p be integers such that 0 [is less than or equal to] p [is less than] k [is less than or equal to] m [is less than or equal to] n. Let h be drawn uniformly at random from [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. For i in [p], let X = {[x.sub.i] : i [element of] [p]} [subset or equal to] [m] and y = ([y.sub.0], ..., [y.sub.p-1]) [element of] [[n].sup.p]. Let E be the event that for all i in [p], h([x.sub.i]) = [y.sub.i]. Let A [subset or equal to] [n], |A| [is less than or equal to] min{p, (k - p - 1)/[e.sup.2]}, and E' be the event that for all x [is not an element of] X, h(x) [is not an element of] A. Let B [subset or equal to] [n] satisfy|B| [is less than or equal to] (k - p - 1)/[Beta] for some real [Beta] [is greater than equal to] 0. If S = [h.sup.-1](B), then Pr[|S| [is greater than equal to] [Beta]|B| + p | E [intersection] E'] [is less than or equal to] 2[[e.sup.2]|A|][(e/[Beta]).sup.[Beta]|B|].

PROOF. Let Y denote [m]\X. Thus, g = [h.sub.Y] | E is drawn uniformly from a (k - p)-wise independent family of functions from Y to [n]. The event E' | E is equivalent to the event that [g.sup.-1](A) = 0. If k - p is odd, let k' = k - p; otherwise, let k' = k - p - 1. By inclusion-exclusion, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

(For the second step, we use the inequality (1 - |A|/n) [is greater than equal to] exp(-2|A|/n), since |A| [is less than or equal to] n/2. The third step follows from the inequality k' [is greater than equal to] 2[e.sup.2]|A| [is greater than equal to] 2|A|.)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

(For the last step, we invoke Lemma 2.4.4 substituting (m - p, n, k - p, [Beta], B, S) for (m, n, k, [Alpha], B, S).) []

For the rest of this section, we fix integers l, c [is greater than equal to] 1, and analyze the 1 out of l protocol on the c-collision crossbar. Let h = ([h.sub.0], ..., [h.sub.l-1]) represent a tuple of l hash functions, where [h.sub.i]: [m] [right arrow] [n] for all i in [l]. For x [element of] [m], let [AFFECT.sub.i] (h, x) denote the set of memory requests that could affect the success of request x in round j for all j in [i + 1]. Formally, we define

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] otherwise.

LEMMA 2.4.6. Let k, m, and n be integers such that 0 [is less than or equal to] k [is less than or equal to] m [is less than or equal to] n. Let h = ([h.sub.0], ..., [h.sub.l-1]) denote l hash functions chosen independently and uniformly at random from [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], For any x [element of] [m] and i [is greater than equal to] 0, if k is at least the maximum of 4 [log.sup.2]n and 10|[AFFECT.sub.i-1](h, x)|, then |[AFFECT.sub.i]([h, x)|[is less than or equal to] max{4 [log.sup.2]n, 10/[AFFECT.sub.i-1](h, x)|} wvhp.

PROOF. In the following, we use [A.sub.i] as a shorthand for [AFFECT.sub.i](h, x). Fix i and let j = i mod l. Let [A.sub.i-1] = {[x.sub.0], ..., [x.sub.p-1]}, where p [element of] [m + 1]. If i [is greater than equal to] l - 1, let A = [A.sub.i-1]\[A.sub.i-l]; otherwise, let A = [A.sub.i-1]. Let B = [h.sub.j]([A.sub.i-l]), C = [h.sub.j](A), and S = [A.sub.i]\[A.sub.i-1]. Thus [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Fix y = ([y.sub.0], ..., [y.sub.p-1]) [element of] [[n].sup.p] and let E be the event that ([h.sub.j]([x.sub.0]), ..., [h.sub.j]([x.sub.p-1])) = y. Let E' be the event that for all x [is not an element of] [A.sub.i-1], [h.sub.j](x) [is not an element of] C. Set [Beta] = max{([e.sup.2]p)/|C|, ([log.sup.2] n)/|C|}. We now apply Corollary 2.33.1, substituting (k, m, n, [h.sub.j], p, X, y, B, C, S, E, E', [Beta]) for (k, m, n, h, p, X, y, A, B, S, E, E', [Beta]), to obtain |S| [is less than or equal to] [Beta]|C| + p with probability at least 1 - 2[e.sup.2|B|][(e/[Beta]).sup.[Beta]|C|]. Since [Beta] [is greater than equal to] [e.sup.2]p/|C| [is greater than equal to] [e.sup.2], we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

(For the second step, we use the inequality 2|B| [is less than or equal to] 2p [is less than or equal to] 2[Beta]|C|/[e.sup.2] [is less than or equal to] [Beta]|C|/2. The last step follows from the definition of [Beta].) Thus,

|[A.sub.i]| [is less than or equal to] |[A.sub.i-1]| + |S| [is less than or equal to] max{[e.sup.2]p, 2 [log.sup.2] n} + 2p [is less than or equal to] max{4 [log.sup.2]n, 10|[A.sub.i-1|]} wvhp. []

For r [is greater than equal to] 0, h = ([h.sub.0], ..., [h.sub.l-1]), [h.sub.i]: [m] [right arrow] [n] for all i in [l], and x [element of] [m], define [ASSIGN.sub.r](h, x) as {(x', [h.sub.0](x'), ..., [h.sub.l-1](x')) : x' [element of] [AFFECT.sub.r](h, x)}. We note that [ASSIGN.sub.r](h, x) completely determines whether x succeeds within r rounds under h. Any element in the set [m] x [[n].sup.l] of (l + 1)-dimensional vectors is referred to as an assignment:

In the following, let [Pr.sub.k][EVENT(h)] denote the probability of EVENT(h) when each hash function in h is chosen independently and uniformly from [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

LEMMA 2.4.7. Let k, m, n, and p be integers such that 0 [is less than or equal to] k [is less than or equal to] m [is less than or equal to] n and 0 [is less than or equal to] p [is less than or equal to] (k - 1)/([e.sup.2] + 1). Let [x.sub.i], for all i in [p], be arbitrary distinct integers from [m] and [y.sub.i,j], for all i in [p] and all j in [l], be arbitrary integers from [n]. Let A = {([x.sub.i], [y.sub.i,0], ..., [y.sub.i,l-1]) : i [element of] [p]}. For arbitrary x [element of] [m] and integer r [is greater than equal to] 0, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

PROOF. Let E be the event that [h.sub.j]([x.sub.i]) = [y.sub.i,j] for all i in [p] and all j in [l]. Let X = {[x.sup.i] : i [element of] [p]) and [Y.sub.j] = {[y.sub.i,j] : i [element of] [p]}, j [element of] [l]. (Note that |[Y.sub.j]| [is less than or equal to] p for j in [l].) Let E' be the event that [AFFECT.sub.r](h, x) = X. Thus, [ASSIGN.sub.r](h, x) = A if and only if E and E' occur.

We now consider E' under the assumption that E occurs. Let g denote the vector ([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]). Let [E'.sub.0] be the event that [AFFECT.sub.r](g, x) = X. Let [E'.sub.1] be the event that for j in [l], [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a subset of X, where for all j in [l], [B.sub.j] is determined as follows: If r [is less than] j then [B.sub.j] = 0; otherwise, we consider two cases. If r mod l [is less than or equal to] j, then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]; otherwise, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. We now show that given E, E' is equivalent to [E'.sub.0] [intersection] [E'.sub.1]. First, by the definition of AFFECT, E' implies [E'.sub.0] and E' implies [E'.sub.1]. Second, event [E'.sub.0] implies that [AFFECT.sub.r](h, x) [contains or equal to] X. Since the domain of g is X, by the definitions of [B.sub.j] and AFFECT, if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for all j, then the calculation of [AFFECT.sub.r](h, x) will be identical to that of the calculation of [AFFECT.sub.r](g, x), that is, [AFFECT.sub.r](h, x) = [AFFECT.sub.r](g, x). Therefore, [E'.sub.0] [intersection] [E'.sub.1] implies E'.

Since the occurrence of event E completely determines g, and hence whether [E'.sub.0]) occurs, it follows that [Pr.sub.k][[E'.sub.0] |E] = [Pr.sub.m][[E'.sub.0]|E]. It remains to bound [Pr.sub.k][[E'.sub.1]|E [intersection] [E'.sub.0]], which is the same as [Pr.sub.k][[E'.sub.1]|E].

For any p [is less than or equal to] q [is less than or equal to] m, if [h.sub.j] is drawn from a q-wise independent family of hash functions from [m] to [n], then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is drawn from a (q - p)-wise independent family of hash functions from [m]\X to [n]. We invoke Lemma 2.4.3, substituting (k - p, m - p, n, [f.sub.j], [B.sub.j]) for (k, m, n, h, A), to obtain that for all j in [l]:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Since [Pr.sub.q][E'|E] is at most [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for q in [m + 1], we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. []

LEMMA 2.4.8. Let k, m, and n be integers such that 0 [is less than or equal to] k [is less than] m [is less than or equal to] n. For any real [Gamma] [is greater than or equal to] 0, x [element of] [m], and integer r [is less than or equal to] [Gamma] log log n, if k [is greater than equal to] 8 [log.sup.4[Gamma]+2] n, then the probability [Pr.sub.k] [x remains after r rounds under h] is at most the sum of the probability [Pr.sub.m] [x remains after r rounds under [h.sub.i]] and 1/[n.sup.2], for n sufficiently large.

PROOF. By Lemma 2.4.6 |[ASSIGN.sub.r](h, x)| [is less than or equal to] 4([log.sup.2] n)[10.sup.r]} [is less than or equal to] 4 [log.sup.4[Gamma]+2] n wvhp. By Lemma 2.4.7, for any assignment A such that |A| [is less than or equal to] 4 [log.sup.4[Gamma]+2] n,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

for n sufficiently large. (Here we use the inequality k [is greater than or equal to] 8 [log.sup.4[Gamma]+2] n [is greater than or equal to] 2|A|.)

Let A be the set {[ASSIGN.sub.r](h, x) : h [element of] [F.sub.m,n] and x remains after r rounds under h}. We thus have:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for n sufficiently large. []

By Lemma 2.3.1.7 for any x [element of] [n], [Pr.sub.n][x remains after O(log log n) rounds] is at most 2/[n.sup.6/5] in the 1 out of 3 protocol on the 1-collision crossbar. Similarly, for the 1 out of 2 protocol on the 2-collision crossbar, Lemma 2.3.2.7 implies that [Pr.sub.n][x remains after O(log log n) rounds] is at most 4/[n.sup.9/8] for any x [element of] [n]. We now apply Lemma 2.4.8 to establish Theorems 2.4.1 and 2.4.2.

2.5. GENERALIZATIONS. Alg1 can be generalized to apply to any a out of b problem by changing the RandomSubbag and PrunedBag routines appropriately; after each step, we need to keep track of how many successes each processor has had, and only those processors with fewer than a successes participate. In the following discussion, we refer to this protocol as the generic protocol. For given a and b, the analysis of the generic protocol can be done using the approach of Section 2.3, but involves more complicated calculations and recurrences. A different analysis of this protocol for the 2 out of 3 case is given in Dietzfelbinger and Meyer auf der Heide [1993], where an O(log log n) upper bound is shown when the collision factor is greater than 3. In this section, we present a simple variant of the generic protocol that solves any a out of b problem on a 2-collision crossbar in O(log log n) time whp.

In particular we can solve any a out of a + 1 problem by running Alg1(n, 2, 1) with [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] different hash-function pairs. Since each run fails with a polynomially small probability, and there are only a constant number of runs, the entire algorithm succeeds whp. For instance, in the case of 2 out of 3, we simply perform 3 runs of Alg1. At first glance, it may appear that this revised protocol is only of interest because it is simpler to analyze. Actually, the new protocol is competitive with the generic one for small a and is much faster for large a. Comparing it for the 2 out of 3 problem, we first note that since each of the 3 runs use 2 hash functions only while the generic protocol uses 3, the revised protocol will be at most twice as slow as the generic one. Moreover, the 1 out of 2 problem is clearly a simpler problem than the 2 out of 3 problem. So each run will involve fewer rounds than in the generic algorithm. For large a, this phenomenon is pronounced. For a generic a out of a + 1 protocol to make "progress", a number of processors must have a large number of successes. But at the outset, the fraction of processors that have succeeded on d [is less than or equal to] a hash functions decreases exponentially with d. Therefore, while the revised protocol experiences only a quadratic slowdown in running time, the generic protocol will suffer an exponential increase in running time with increasing a. (We remark here that our notion of the generic protocol does not include the protocol studied in Meyer auf der Heide et al. [1995] that is shown to have a running time that is polynomial in a when a, b, and c are chosen.)

The basic idea outlined above can be used to solve any a out of b problem by choosing any a + 1 hash functions and solving the corresponding a out of a + 1 problem.

THEOREM 2.5.1. For integer constants a and b with 1 [is less than or equal to] a [is less than] b, the corresponding a out of b problem can be solved on a 2-collision crossbar in O(log log n) time whp.

The above generalizations can be made for the 1-collision crossbar as well. Since Alg1 solves the 1 out of 3 problem on a 1-collision crossbar in O(log log n) time whp, any a out of a + 2 problem can be solved in the same asymptotic time bound by running Alg1(n, 3, 1) on [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] different triples of hash functions.

THEOREM 2.5.2. For integer constants a and b with 1 [is less than or equal to] a [is less than] b - 1, the corresponding a out of b problem can be solved on a 1-collision crossbar in O(log log n) time whp.

It is worth noting that by the above result, a 1-collision crossbar can solve the 3 out of 5 problem and hence can simulate an EREW PRAM with n processors in O(log log n) time whp using 5 hash functions. Thus, a 1-collision crossbar is asymptotically as powerful as a 2-collision one.

3. Symmetry Breaking

In this section, we analyze algorithms for the Control Tower problem. In the Control Tower problem, there is one central control tower and n remote stations, h of which contain a message destined for the control tower. Each station can only transmit a message to and receive a message from the control tower, and only in discrete time slots. When two or more stations attempt to transmit a message in the same time slot, all of the transmitted messages are lost. Note that the control tower can transmit a message to only one remote station in one time slot. We will consider each time slot to be a step; the goal is to transmit all h messages to the control tower in as few steps as possible. (Throughout our analysis, we will assume that the remote stations are numbered from 1 to n, and that the control tower sends an acknowledgement upon receipt of a message.)

The Control Tower problem is related to the problem of direct routing of h-relations on a 1-collision crossbar, as discussed in Section 1. Specifically, since each processor is only permitted to transmit a message directly to its destination, we are able to analyze each destination independently. Transmitting a set of at most h messages to a destination is then equivalent to the Control Tower problem. Thus the lower bound we obtain for the Control Tower problem can be used to obtain a lower bound for direct h-relation routing.

To give some intuition into the Control Tower problem, let us first examine the case when h = 2. In this case, the problem is that two stations are trying to transmit messages, but if they transmit at the same time, then both of the transmissions are blocked. Note that some sort of symmetry breaking is required, or the messages may never be successfully transmitted. A simple randomized strategy to break the symmetry would be for each station to flip a coin and transmit if and only if it comes up "heads". Then, the expected number of steps before both messages are successfully transmitted is constant. To achieve success, wvhp requires [Theta](log n) steps, however. Still, this turns out to be the best strategy possible, as shown by Goldberg et al. [1993]. Generalizing to h [is greater than] 2, we can easily verify that if there are k messages left to transmit (k [is less than or equal to] h), then by having each station transmit with probability 1/k, we maximize the probability of obtaining a successful transmission. The difficulty is that the stations are not able to communicate with each other, and consequently they do not know exactly how many messages are left to transmit at any intermediate step of the algorithm. If the number of messages left to transmit were known to all stations at every step, then the Control Tower problem could be solved in [Theta] (h + log n) steps wvhp. If not, Gereb-Graus and Tsantilas [1992] showed that the Control Tower problem could be solved in O(h + log h log n) time wvhp, but it was not known whether the extra log h factor could be eliminated. We show that the extra factor of log h is indeed necessary.

We also examine deterministic solutions for the Control Tower problem and direct h-relation routing. As mentioned in Section 1.2, a deterministic lower bound of [Omega]((h/log h) log n) for the Control Tower problem follows from the same lower bound for routing all h messages in the Ethernet model [Greenberg and Winograd 1985]. We show a lower bound of [Omega]((h/min{log h, log log n })log n) (which improves the previous lower bound for h larger than polylog(n)), and we show this lower bound holds for successfully transmitting any of the h messages in the Control Tower problem. (This result does not hold in the Ethernet model, where it is trivial to successfully transmit one of the messages in [Theta](log n) time.) Finally, we prove the existence of a [Theta](h log h log n) time deterministic algorithm for direct h-relation routing.

Lower bounds for the Control Tower problem can most easily be studied in the context of hypergraphs, so here we review the definition of a hypergraph and related concepts.

Let V be a set of elements, called vertices. Let E be a set of nonempty subsets of V, called edges. Then a hypergraph is given by a pair (V, E). Given a hypergraph H = (V, E), the hypergraph induced by a set of vertices V' [subset of equal to] V is H' = (V', E'), where E' = {e [element of] E : [intersection] V' [is not equal to] 0}. Also, the hypergraph induced by a set of edges E' [subset of equal to] E is H' = (V, E'). A subset of vertices T [subset of equal to] V covers an edge e [element of] E if e [intersection] T [is not equal to] 0. A transversal of H is a set of vertices T [subset of equal to] V that covers every edge in E. For convenience, we define an a-transversal to be a set of vertices T [subset of equal to] V that covers at least a edges of E.

We define a hypergraph H = (V, E) to be a-thick if [min.sub.e [element of] E] |e| [is greater than or equal to] a. Note that if E is empty, then H is a-thick for every a. A hypergraph H = (V, E) is (a, b)-thick if H is a-thick and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where [f.sub.k] denotes the number of edges e [element of] E such that a[2.sup.k] [is less than or equal to] |e| [is less than or equal to] a[2.sup.k+1], k [is greater than or equal to] 0.

We will make use of the inequalities: (i) 1 + x [is less than or equal to] exp(x) for all real x, and (ii) 1 - x [is greater than or equal to] exp(-2x) for 0 [is less than or equal to] x [is less than or equal to] 1/2.

3.1. DETERMINISTIC ALGORITHM FOR DIRECT ROUTING. Here we give an improved upper bound for deterministic direct routing on the 1-collision crossbar. This improved bound is obtained by slightly modifying a technique in Goldberg and Jerrum [1992]. They show that one can solve the Control Tower problem deterministically in [Theta](h log n) steps. (Their proof is much simpler than the proof in Komlos and Greenberg [1985].) This directly implies the existence of a deterministic direct h-relation routing algorithm for the 1-collision crossbar which takes [Theta]([h.sup.2] log n) steps. By modifying their technique, however, we are able to obtain an upper bound of [Phi](h log h log n) on deterministic direct h-relation routing on the 1-collision crossbar. Thus, in combination with the lower bounds shown later, we obtain an exponential decrease in the gap between the upper and lower bounds for this problem.

As in Goldberg and Jerrum [1992], define an (h, k)-relation as a routing problem in which each processor is the source of at most h packets and each memory module is the destination of at most k packets.

LEMMA 3.1.1. There exists a deterministic algorithm that, given an arbitrary (h, k)-relation (k [is less than or equal to] h [is less than or equal to] n), terminates after O(h log n) communication steps such that the remaining communication problem is an (h, ??k/2??)-relation.

PROOF. We employ the probabilistic method to prove this. Assume each processor has h slots numbered 1, ..., h and each slot contains at most one message. Consider the following randomized communication step: Each processor selects one of its slots at random, and if the slot has a message, attempts to transmit it.

At any step, if there are l messages, k/2 [is less than or equal to] l [is less than or equal to] k, yet to be received by a memory module M, the probability of a successful transmission to M is at least:

l 1/h[(1 - 1/h).sup.l-1] [is greater than or equal to] l 1/h[(1 - 1/h).sup.h-1] [is greater than or equal to] k/2eh.

The probability that in ch log n communication steps there exist at least ch log n - ??k/2?? failed transmissions to M is at most

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for n sufficiently large. (The last inequality is obtained by choosing an appropriate c.) Since the number of choices for the sources and the slots of the messages destined to M are at most

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

the expected number of message assignments such that this algorithm fails to send ??k/2?? messages is bounded above by 1/[n.sup.k]. Thus, there exists a deterministic algorithm that transmits at least ??k/2?? messages destined to M. Now we note that any assignment of messages destined to another module P is also a possible assignment for messages to M. Therefore, the same deterministic algorithm that routes at least ??k/2?? messages to M will also route at least ??k/2?? messages to P, for any other P. []

THEOREM 3.1.2. There exists a deterministic algorithm that realizes any h-relation, h [is less than or equal to] n, in O((h log h) log n) steps.

PROOF. There are ??log h?? phases in the algorithm. The ith phase reduces an (h, ??h/[2.sup.i -1]??)-relation problem to an (h, ??h/[2.sup.i]??)-relation using the algorithm in Lemma 3.1. Thus, after ??log h?? phases, the remaining communication problem is an (h, 1)-relation that can be realized in O(h) steps. []

3.2. DETERMINISTIC LOWER BOUND. To obtain a lower bound on the number of steps required for a deterministic solution to the Control Tower problem, we will first find a subset of stations such that a good fraction of those stations transmit at each step, and then show that there are two small disjoint groups of stations which always transmit during exactly the same steps. By placing messages at all stations in both groups, no station in either group would succeed in transmitting its message, due to contention.

Some preliminary results that will aid in our proof are presented here.

Given that the number of edges in a hypergraph is small (compared to the number of vertices), the following lemma shows that we can find a large subset of vertices which all cover exactly the same set of edges. By using this relatively simple lemma, we would be able to prove a logarithmic lower bound on the Control Tower problem. It will be much more difficult, however, to prove a superlogarithmic lower bound.

LEMMA 3.2.1. Any hypergraph H = (V, E) with n vertices and m edges has a subset V' of V with |V'| [is greater than or equal to] n[2.sup.-m] in which every vertex in V' covers exactly the same set of edges.

PROOF. By induction on m. If m = 0, then E = 0, so let V' = V. Then |V'| = n = n[2.sub.0], and every vertex in V' covers no edges. If m [is greater than] 0, choose an edge e [element of] E, and consider the hypergraph [H.sub.0] = (V, E - {e}) induced by E - {e}. By induction we can find a subset V" of V with |V"| [is greater than or equal to] n[2.sup.-(m-1)] in which every vertex in V" covers exactly the same set of edges. Then let V' be the larger of V" [intersection] e and V" - e, one of which is guaranteed to be at least of size |V"|/2 [is greater than or equal to] n[2.sup.-m]. Also, all vertices in V' cover exactly the same set of edges in E - {e}, and either all vertices in V' cover e or all do not cover e. []

The following lemma shows that we can find a subset of vertices such that every edge induced by that subset contains a large fraction of those vertices.

LEMMA 3.2.2. Let x [is greater than] 0. Then any hypergraph H = (V, E) with n vertices and m edges has a subset V' of V with |V'| [is greater than or equal to] n[(1 - 1/x).sup.m] that induces a |V'|/x-thick hypergraph H' = (V', E').

PROOF. Construct V' from V iteratively by removing vertices for m steps. Let [V.sub.i] be the set of vertices remaining after step i, with [V.sub.0] = V, and V' = [V.sub.m]. At step i, if [V.sub.i-1] induces a hypergraph that is |[V.sub.i-1]|/x-thick, let [V.sub.i] = [V.sub.i-1]. Otherwise, let e [element of] E be an edge with |e [intersection] [V.sub.i-1| [is less than] |[V.sub.i-1]|/x, and let [V.sub.i] = [V.sub.i-1] - e. By induction, we have |[V.sub.i]| [is greater than] n[(1 - 1/x).sup.i], and thus |V'| = |[V.sub.m]| [is greater than] n[(1 - 1/x).sup.m]. If at some step i, the hypergraph induced by [V.sub.i] is |[V.sub.i]|/x-thick, then by construction, V' = [V.sub.i], and V' induces a hypergraph which is |V'|/x-thick. Otherwise, the number of edges in the hypergraph induced by [V.sub.i] is at least one less than the number of edges in the hypergraph induced by [V.sub.i-1]. Thus the hypergraph induced by V' = [V.sub.m] contains no edges, and consequently, it is |V'|/x-thick. []

COROLLARY 3.2.3. Let x [is greater than or equal to] 2. Then any hypergraph H = (V, E) with n vertices and m edges has a subset V' of V with |V'| [is greater than or equal to] n exp(-2m/x) that induces a |V'|/x-thick hypergraph H' = (V', E').

Next we formulate some results about transversals and "near-transversals" (small subsets of vertices that cover almost all of the edges).

The following lemma is given by Alon [1990, Proposition 2.1] with [Alpha] set to ln((m/x)/ln k).

LEMMA 3.2.4 [ALON 1990]. Let x [is greater than or equal to] 1. Then any n/x-thick hypergraph H = (V, E) with n vertices and m edges has a transversal of size at most x + x ln(m/x).

We will make use of the following simple corollary.

COROLLARY 3.2.5. Let x [is greater than or equal to] 1. Then any 2n/x-thick hypergraph H = (V, E) with n vertices and m edges where 2n/x [is greater than] 2(x + x ln(m/x)) has two disjoint transversals of size at most x + x ln(m/x).

PROOF. Using the fact that H is n/x thick, we can construct one transversal of size at most x + x ln(m/x) using Lemma 3.2.4. Note that after removing that transversal from the set of vertices, the remaining hypergraph is also n/x thick. Thus, we can construct another (disjoint) transversal of size x + x ln(m/z). []

Using these results, we would only be able to prove the desired lower bound on the Control Tower problem for h = [Omega](log n). In order to prove our bound for small h, we make use of a much lengthier argument involving near-transversals. We first present a lemma similar to Lemma 3.2.4, except that it allows us to trade off the size of a near-transversal with the number of edges covered by the near-transversal.

LEMMA 3.2.6. Let x, z [is greater than or equal to] 1. Then any n/x-thick hypergraph H = (V, E) with n vertices and m edges has an (m - m/z)-transversal of size at most ??x ln z??.

PROOF. Iteratively choose a set of vertices to be in the (m - m/z)-transversal. Let [T.sub.i] be the set of vertices chosen by step i, and let [E.sub.i] be the set of edges that are covered by [T.sub.i]. Then, [T.sub.0] = 0 and [E.sub.0] = 0. We will proceed for at most t = ??x ln z?? steps. At step i, if E = [E.sub.i-1], then let [T.sub.i] = [T.sub.i-1] and [E.sub.i] = [E.sub.i-1]. Otherwise, [T.sub.i-1] does not intersect any edge in E - [E.sub.i-1] and thus each edge in E - [E.sub.i-1] contains at least n/x vertices of V - [T.sub.i-1]. Then, by an averaging argument, some vertex v [element of] V - [T.sub.i-1] is contained in at least |E - [E.sub.i-1]|/x edges. Let [T.sub.i] = [T.sub.i-1] [union] {v}. Then [E.sub.i] = [E.sub.i-1] [union] {e : e [intersection] {v} [is not equal to] 0}. By induction, we have |E - [E.sub.i]| [is less than or equal to] m[(1 - 1/x).sup.i]. Then |E - [E.sub.i]| [is less than or equal to] m exp(-i/x). Thus, |E - [E.sub.t]| [is less than or equal to] m exp(- ln z) = m/z, implying |[E.sub.t]| [is greater than or equal to] m - m/z. Then [T.sub.t] is an (m - m /z)-transversal, and |[T.sub.t]| [is less than or equal to] t = ??x ln z??. []

Let us define an (m - m/z)-transversal obtained by the construction of Lemma 3.2.6 as a near-transversal. To achieve our desired result, we will make use of two disjoint near-transversals. It would be trivial to simply find two of these by applying Lemma 3.2.6 twice, but we require that these two near-transversals have the property that they cover exactly the same edges. (Notice that when using full transversals, this property is trivially satisfied.) Here we show that for certain hypergraphs there exist two small disjoint near-transversals covering almost all of the edges, and furthermore, they cover exactly the same edges.

LEMMA 3.2.7. Let y [is greater than or equal to] 2, k [is greater than or equal to] 1, and t = ??2y ln [y.sup.k]??. Then any n/y-thick hypergraph H = (V, E) with n vertices and m edges, where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

has two disjoint (m - m/[y.sup.k])-transversals each of size at most t which cover exactly the same edges.

PROOF. If m = 0, then the lemma holds trivially, so assume that m [is greater than or equal to] 1. Iteratively construct ??n/(2yt)?? disjoint (m - m/[y.sup.k])-transversals, each having size at most t, using the method of Lemma 3.2.6 with x = 2y and z = [y.sup.k]. After constructing each near-transversal, remove the vertices in that near-transversal from the hypergraph. This ensures that the near-transversals constructed are disjoint. Note that after constructing i near-transversals of size t, we have removed at most it vertices. Therefore, we remove a total of at most ??n/(2yt)??t [is less than or equal to] n/2y vertices, which implies that the remaining hypergraph is n/2y-thick. This guarantees that we can use the value x = 2y in Lemma 3.2.6 at each step.

Now the number of ways to choose at most m/[y.sup.k] edges from m edges is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

By the condition stated in the lemma, this is less than the number of near-transversals we created, and thus two of these near-transversals cover exactly the same edges. []

COROLLARY 3.2.8. Let y [is greater than or equal to] 2. Then any n/y-thick hypergraph H = (V, E) with n vertices and m edges, where y [is greater than or equal to] 4m/ln n and

??n/2y??6y ln y???? [is greater than] [mn.sup.1/4],

has two disjoint (m - m/[y.sup.3])-transversals each of size at most ??6y ln y?? that cover exactly the same edges. []

PROOF. If m = 0, the corollary holds trivially, so assume m [is greater than or equal to] 1. Use Lemma A.7 to show that the conditions of Lemma 3.2.7 apply (with k set to 3), as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Then, Lemma 3.2.7 states that there are two disjoint (m - m/[y.sup.3])-transversals, each of size at most ??6y ln y??, that cover exactly the same edges. []

Now we can place a bound on the number of transmission steps required to solve the Control Tower problem.

THEOREM 3.2.9. A deterministic algorithm for the Control Tower problem with h messages (2 [is less than or equal to] h [is less than or equal to] [n.sup.1/10]) to transmit requires [Omega]((h/min{log h, log log n}) log n) steps to successfully transmit any message.

PROOF. Let V be the set of all n stations, and E be a set of edges, where edge i contains all stations that would attempt to transmit a signal in step i, if they had a message to transmit. Let m = |E|. We will show that if m [is less than] (h/128 min{ln h, ln ln n}) ln n, then we can select a group of h stations such that no station succeeds in transmitting its message. To select a group such that at least two stations do not succeed, we would need to select two disjoint subgroups of stations that try to transmit at exactly the same time steps. In terms of hypergraphs, this is equivalent to selecting two disjoint sets of vertices that cover exactly the same set of edges. (Note that this would be enough to prove a lower bound for the Control Tower problem.) To select a group such that no stations succeed, we need to make sure that in all steps where a station is attempting to transmit, another station is also attempting to transmit. In terms of hypergraphs, this is equivalent to selecting two disjoint sets of vertices that cover exactly the same set of edges, where the size of the union of the two disjoint sets is exactly h.

If h [is less than] 64, then m [is less than or equal to] 1/2 log n. Then, by Lemma 3.2.1, we can find a group of [square root of n] vertices that cover exactly the same set of edges. Then, we simply select h vertices from this group. (This case is also considered by Goldberg et al. [1993].)

If h [is greater than or equal to] 64 and h [is greater than or equal to] In n, then m [is less than] (h/128 ln ln n)ln n, and we choose x such that h = 4x ln ln n. Note that x [is greater than or equal to] h/4ln ln n [is greater than or equal to] 32m/ln n, and x [is greater than or equal to] 2. By Corollary 3.2.3, there is a subset V' of V such that |V'| [is greater than or equal to] n exp(-4m/x) [is greater than or equal to] [n.sup.7/8] and V' induces a 2|V'|/x-thick hypergraph H' = (V', E'). Let m' = |E'|. By Corollary 3.2.5, there are two disjoint transversals of H' whose sizes sum to at most 2(x + x ln ln n) [is less than or equal to] h. Then, we can select the vertices in these two transversals, and select the rest of the h vertices arbitrarily from V'. Then, none of the h stations corresponding to the selected vertices successfully transmits its message.

If 64 [is less than or equal to] h [is less than or equal to] ln n, then choose x such that h = 4 + 12x ln x. Note that x [is greater than or equal to] h/16 ln h [is greater than] 8m/ln n and x [is greater than or equal to] 2. By Corollary 3.2.3 there is a subset V' of V such that |V'| [is greater than or equal to] n exp(-2m/x) [is greater than or equal to] [n.sup.3/4] and V' induces a |V'|/x-thick hypergraph H' = (V', E'). Let m' = |E'|. Then, by Corollary 3.2.8, there are two disjoint (m' - m'/[x.sup.3])-covers [T.sub.1] and [T.sub.2] of H' that cover exactly the same set of edges and whose sizes sum to at most 2(6x ln x + 1) [is less than or equal to] h - 2. Then, to obtain a lower bound for the Control Tower problem, we could select the vertices in [T.sub.1] and [T.sub.2] and select the other h - |[T.sub.1] [union] [T.sub.2] vertices arbitrarily.

To prove the theorem, however, requires that we obtain two disjoint subsets of V that cover the same edges and whose sizes sum to h. We proceed as follows: First we note that we will be selecting the vertices from V', and thus they will not cover any edge in E - E'. We will start with the two disjoint subsets [T.sub.1] and [T.sub.2] found above. Let E" be the set of edges in E' that are not covered by [T.sub.1] or [T.sub.2]. Note that |E"| [is less than or equal to] m'/[x.sup.3] [is less than or equal to] m'/x [is less than or equal to] (ln n)/4. By Lemma 3.2.1, there is a subset V" of V' with |V"| [is greater than or equal to] |V'|[2.sup.-(ln n)/4] [is greater than or equal to] [n.sup.1/2] in which all vertices cover exactly the same set of edges in E". Then, add one vertex from V" to [T.sub.1], and another h - |[T.sub.1] [union] [T.sub.2]| - 1 vertices from V" to [T.sub.2]. []

COROLLARY 3.2.10. Any deterministic algorithm for direct routing of an h-relation (2 [is less than or equal to] h [is less than or equal to] [n.sup.1/10]) on a 1-collision n-crossbar requires [Omega]((h/min{log h, log log n})log n) steps.

PROOF. Consider one memory module to be the control tower, and the other n processors to be the stations. The collision protocol for the 1-collision crossbar is same as in the Control Tower problem. By Theorem 3.2.9, there is a way to place h messages on the n processors such that they are not all successfully transmitted in less than (h/128 min{ln h, ln ln n}) In n steps. []

3.3. RANDOMIZED LOWER BOUND. A randomized algorithm can solve the Control Tower problem in expected O(h) steps. However, for many applications, including the analysis of direct h-relation routing on a c-collision crossbar, it is necessary to determine the number of steps required to achieve a polynomially small probability of failure. That is what we analyze in this section.

Our lower bound will make use of a result of Yao [1983], which states that any lower bound for deterministic algorithms on random inputs implies the same lower bound for randomized algorithms on worst case inputs. In particular, we will proceed by developing a lower bound for deterministic algorithms solving the Control Tower problem, where we assume that the h stations that have messages to transmit are chosen randomly from the n stations.

We begin by converting the problem to the hypergraph domain. Then we show how to reduce the hypergraph corresponding to a given deterministic algorithm to a thick hypergraph, and we show that with a significant probability, the processors corresponding to vertices in this thick hypergraph contain messages that are not successfully transmitted.

The following lemma is a modification of a result of Alon et al. [1991, Lemma 3.1], with a similar proof. For completeness, we present the entire proof.

LEMMA 3.3.1. Given [r.sub.1], [r.sub.2] [is greater than or equal to] 1, where [r.sub.1] [is less than] [r.sub.2], let r = [r.sub.2] - [r.sub.1] and let H = (V, E) be a hypergraph with n vertices and m edges. Then for some k, [r.sub.1] [is less than or equal to] k [is less than] [r.sub.2], there is a subset V' of V with |V'| [is greater than or equal to] n exp(-8m[2.sup.-k]/r) that induces a (|V'|[2.sup.-k], 4m/r)-thick hypergraph H' = (V', E').

PROOF. Define a permutation [e.sub.1], ..., [e.sub.m] of the edges inductively as follows. Let [e.sub.1] be a minimum size edge in E. Then, assuming edges [e.sub.1], ..., [e.sub.i] have already been chosen (1 [is less than or equal to] i [is less than or equal to] m), let [e.sub.i+1] be the edge in E\{[e.sub.1], ..., [e.sub.i]} such that |[e.sub.i+1]\[[union].sub.1 [is less than or equal to] j [is less than or equal to] i] [e.sub.j]| is minimum. For 1 [is less than or equal to] i [is less than or equal to] m, define [p.sub.i] = 0 if |[[union].sub.1 [is less than or equal to] j [is less than or equal to] i] [e.sub.j]| = n, and otherwise define

[p.sub.i] = |[e.sub.i]\[[union].sub.1 [is less than or equal to] j [is less than] i][e.sub.j]|/ n - |[[union].sub.1 [is less than or equal to] j [is less than] i][e.sub.j]|.

For each k [is greater than or equal to] 0, [r.sub.1] [is less than] k [is less than or equal to] [r.sub.2], let j(k) be the smallest i such that [p.sub.i] [is greater than or equal to] [2.sup.-k]. (If there is no such i, let j(k) = m + 1). Notice that by the definition of the permutation [e.sub.1], ..., [e.sub.m], for every k [is greater than or equal to] 0 and every j' [is greater than or equal to] j(k),

|[e.sub.j']\[[union].sub.1 [is less than or equal to] j [is less than] j(k)][e.sub.i]|/ n - |[[union].sub.1 [is less than or equal to] i [is less than] j(k)][e.sub.j]| [is greater than or equal to] [2.sup.-k].

Now for each k [is greater than or equal to] 0, let

[d.sub.k] = |{i : 1 [is less than or equal to] i [is less than or equal to] m and [2.sup.-k] [is less than or equal to] [p.sub.i] [is less than] [2.sup.-k+1]}|, and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Call an index k good if [r.sub.1] [is less than] k [is less than] [r.sub.2] and [d'.sub.k] [is less than or equal to] 2m/r. The average value of [d'.sub.k] over [r.sub.1] [is less than or equal to] k [is less than] [r.sub.2] is at most m/r, and thus at least half of the indices k, [r.sub.1] [is less than] k [is less than or equal to] [r.sub.2], are good. Note that if k is good, then we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Thus, for any good k there exists some subset V' of the required size that induces a |V'][2.sup.-k]-thick hypergraph.

Next we show that for some good k, there exists a subset V' that induces a (|V'|[2.sup.-k], 4m/r)-thick hypergraph. For each good k and each edge [e.sub.j], with j(k) [is less than or equal to] j' [is less than or equal to] m, define s(k, j') to be the unique integer l such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Note that if k', k are both good and k' [is less than] k, then j(k') [is greater than or equal to] j(k). Thus, if j' [is greater than or equal to] j(k') then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Consequently, s(k', j') [is less than or equal to] s(k, j') - 1. Therefore, for every fixed j' [is less than or equal to] m,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

For each good k, define [y.sub.k] = [[Sigma].sub.j' [is greater than or equal to] j(k)[2.sup.-s(k,j')]. Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Since at least r/2 indices are good, there is some index k with [y.sub.k] [is less than or equal to] 4m/r. Hence V' = V\[[union].sub.1 [is less than or equal to] i [is less than] j(k)][e.sub.j] satisfies the conditions of the lemma. []

Next we show that large random sets of vertices in a thick hypergraph cover many edges with nontrivial probability.

LEMMA 3.3.2. Let x [is greater than or equal to] 1 and t = ??13x??. Given an (n/x, y)-thick hypergraph H = (V, E) with n vertices and m edges, and a randomly chosen subset T of V with |T| = t, then with probability at least [(2x).sup.-t], for every j [is greater than or equal to] 0, T covers all but y[2.sup.-(j+1) of the edges with thickness in the range [n[2.sup.j]/x, n[2.sup.j+1]/x).

PROOF. Note that ??13x?? [is greater than or equal to] ??1 + ??log x?? + 4x [[Sigma].sub.i [is greater than or equal to] 0[(3/2).sup.-i??. For each j, 0 [is less than or equal to] j [is less than or equal to] log x, let

[E.sub.j] = {e [element of] E : n[2.sup.j]/x [is less than or equal to] |e| [is less than] n[2.sup.j+1]/x}.

Then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. By the fact that H is (n/x, y)-thick, |[E.sub.j]| [is less than or equal to] y[2.sup.j]. View T as a collection of disjoint randomly chosen subsets [T.sub.0], ..., [T.sub.??log x??], T', where [t.sub.j] = |[T.sub.j]| = ??4x[(1.5).sup.-j]??, and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Note that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. We will show that the vertices from the set [T.sub.0] cover all but y[2.sup.-1] edges in [E.sub.0] with probability at least [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], the vertices from the set [T.sub.1] cover all but y[2.sup.-2] edges in [E.sub.1] that were not covered by [T.sub.1] with probability at least [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and in general the vertices from the set [T.sub.j] cover all but y[2.sup.-(j+1)] of the edges in [E.sub.j] that were not covered by [[union].sub.0 [is less than or equal to] i [is less than] j] [T.sub.i] with probability at least [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. The claim of the lemma then follows easily.

Assume we have chosen the vertices in sets [T.sub.0], ..., [T.sub.j-1], J [is greater than or equal to] 0. Let

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Consider choosing the vertices in [T.sub.j] one at a time. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be the set containing the first i vertices chosen. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be the set of edges in [E'.sub.j] not covered by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN AS with [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Let

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The hypergraph [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]-thick, so the average number of edges covered by a vertex in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is at least [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and the maximum number of edges covered by a vertex in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Hence, with probability at least [2.sup.j]/(2x) [is greater than] [(2x).sup.-1] , the number of edges of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] covered by the next vertex added is at least [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Therefore, with probability at least [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Thus, with probability at least [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (Here we use the fact that for all integers j [is greater than or equal to] 0, [2.sup.j]exp(-2[(4/3).sup.j]) [is less than or equal to] [2.sup.-(j+1)].) []

COROLLARY 3.3.3. Let x [is greater than or equal to] 1 and t = ??13x??. Given an (n/x, y)-thick hypergraph H = (V, E) with n vertices and m edges, there are at least [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] subsets of vertices of size t that cover, for every j [is greater than or equal to] 0, all but y[2.sup.-(j+1)] of the edges with thickness in the range [n[2.sup.j]/x, n[2.sup.j+1]/x).

Using Corollary 3.3.3, we establish a lower bound on the probability that a random set of vertices contains two near-transversals covering exactly the same set of edges.

LEMMA 3.3.4. Let x [is greater than or equal to] 1 and t = ??13x??. Given an (n/x, y)-thick hypergraph H = (V, E) with n vertices and m edges, where n [is greater than or equal to] 4t, the probability that two randomly chosen disjoint t-size subsets of V cover exactly the same set of edges is at least

1/2[(2x).sup.t](1/2[y.sup.log y][(2x).sup.t] exp(18y) - 4[t.sup.2]/n).

PROOF. If m = 0, then the lemma holds trivially, so assume m [is greater than or equal to] 1. Call a t-size subset of V an attempt, and an attempt that satisfies the condition of Corollary 3.3.3 a good attempt. From Lemma A.9, the number of different subsets of edges that could possibly fail to be covered by a good attempt is at most [y.sup.log y] exp(18y). Let A be the set containing exactly these subsets. For a given attempt, define the uncovered set to be the subset of edges not covered by that attempt. Using Corollary 3.3.3, we find that on average each subset in A is the uncovered set for at least

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

good attempts. Let B [subset of equal to] A be the set containing those subsets of edges, each of which is the uncovered set for at most [Alpha]/2 good attempts. Then, at most

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

good attempts correspond to uncovered sets in B. Hence, the probability that a single random attempt [T.sub.1] is one of the good attempts with associated uncovered set in A\B is at least 1/2[(2x).sup.-t]. If this is so, then the number of attempts that are disjoint from [T.sub.1] and that cover the same edges as [T.sub.1] is at least

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Note that we are subtracting the total number of subsets of size t that intersect [T.sub.1]. Hence, the probability that a random attempt [T.sub.2] covers the same edges as [T.sub.1] without intersecting [T.sub.1] is at least

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

By Lemma A.8, the probability that two randomly chosen t-size disjoint subsets of V cover exactly the same set of vertices is at least

1/2[(2x).sup.t](1/2[y.sup.log y][(2x).sup.t] exp(18y) - 4[t.sup.2]/n). []

Now we can place a bound on the number of transmission steps required to solve the Control Tower problem with probability of failure polynomially small in n.

THEOREM 3.3.5. Let A be a deterministic algorithm for the Control Tower problem where h [is greater than or equal to] 2 messages are placed randomly at h of the n stations. If A succeeds in T(n, h) steps with probability at least 1 - [n.sup.-3/4], then for some constant [Epsilon] [is greater than] 0, T(n,h) [is greater than or equal to] [Epsilon] log h log n.

PROOF. Let [Epsilon] = [10.sup.-5]. For h [is greater than or equal to] log n log log n, the result is trivial, since T(n, h) [is greater than or equal to] h [is greater than or equal to] [10.sup.-5] log h log n. So assume 2 [is less than or equal to] h [is less than or equal to] log n log log n. Let V be the set of n stations, and E be a set of edges, where edge i contains each station that would attempt to transmit a message in step i if it had a message to transmit. Let m = |E|, and assume that m [is less than] [10.sup.-5] log h log n [is less than] [10.sup.-4] log h ln n. In what follows, we show that, with probability at least [n.sup.-3/4], there are two disjoint sets of stations that attempt to transmit at exactly the same time steps. In terms of hypergraphs, this is equivalent to showing that with probability at least [n.sup.-3/4], a random set of h vertices contains two disjoint sets of vertices that cover exactly the same set of edges.

If h [is less than] [2.sup.1000], then m [is less than or equal to] (1/10) log n. If n [is less than] [2.sup.10], then m = 0, and the theorem holds trivially. Otherwise, by Lemma 3.2.1, we can find a group of [n.sup.9/10] vertices that cover exactly the same set of edges. The probability that two of the h randomly placed messages lie in this group is at least

[n.sup.-1/10]([n.sup.9/10] - 1/n - 1) [is greater than or equal to] [n.sup.-3/4].

(Goldberg et al. [1993] prove a similar result.)

If [2.sup.1000] [is less than or equal to] h [is less than or equal to] log n log log n [is less than or equal to] [log.sup.2] n, then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and h [is less than or equal to] [n.sup.1/10]. If m [is less than or equal to] log h then m [is less than or equal to] (log n)/10, and the argument in the previous paragraph holds; otherwise, from Lemma 3.3.1 with [r.sub.1] = (log h)/10 and [r.sub.2] = (3 log h)/10, there is a subset V' of V with

|V'| [is greater than or equal to] n exp(-40m/x log h)

that induces a (|V'|/x, 20m/log h)-thick hypergraph, for some x, [h.sup.1/10] [is less than or equal to] x [is less than or equal to] [h.sup.3/10]. By our assumption that m [is less than or equal to] [10.sup.-4] log h ln n, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

and the induced hypergraph is (|V'|/x, (ln n/500)-thick. Note that for h [is greater than or equal to] [2.sup.1000], we have |V'| [is greater than or equal to] 52x + 4 and [h.sup.1/2]/5 [is greater than or equal to] 2 ??13x??. Furthermore, with y set to (ln n)/500 and t set to ??13x??, we have

1/2[(2x).sup.t](1/2[y.sup.log y][(2x).sup.t] exp(18y) - 4[t.sup.2]/n) [is greater than or equal to] [n.sup.-1/5].

Hence, the probability that at least 2??13x?? of the stations with messages belong to V' is at least

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

By Lemma 3.3.4, the probability that two disjoint ??13x??-size random subsets of these vertices each cover exactly the same set of edges is at least [n.sup.-1/5]. Hence, the probability that two disjoint subsets of the randomly chosen set of h vertices cover exactly the same set of edges is at least [n.sup.-2/5][n.sup.-1/5] [is greater than or equal to] [n.sup.-3/4]. []

COROLLARY 3.3.6. Let A be a randomized algorithm for the Control Tower problem with h [is less than or equal to] 2 messages and n processors. If A succeeds in T(n, h) steps with probability at least 1 - [n.sup.-3/4], then for some constant [Epsilon] [is greater than] 0, T(n, h) [is greater than or equal to] [Epsilon] log h log n.

PROOF. With [Epsilon] = [10.sup.-5], this corollary follows from Theorem 3.3.5 and Yao [1983, Theorem 1]. []

COROLLARY 3.3.7. Let h [is greater than or equal to] 2, and let A be a randomized algorithm for direct routing of an h-relation on a 1-collision crossbar with n processors. If the expected time of A is T(n, h) then for some constant [Epsilon] [is greater than] 0, T(n, h) [is greater than or equal to] max{h, [Epsilon] log h log n}.

PROOF. Let [Epsilon] = [10.sup.-6]. The claim that T(n, h) [is greater than or equal to] h is trivial. Also, for all h [is greater than or equal to] 2, if n [is less than] [2.sup.100] or h [is greater than or equal to] [n.sup.1/3], then h [is greater than or equal to] [10.sup.-6] log h log n, and so the claimed bound on T(n, h) is trivial.

In the case of n [is greater than or equal to] [2.sup.100] and h [is less than] [n.sup.1/3], by Yao [1983, Theorem 1], we only need to show that the lower bound holds for the expected time of any deterministic algorithm over some input distribution. We choose an input distribution as follows. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be a set of ??n.sup.1/3?? disjoint groups of ??[n.sup.1/3]?? [is greater than or equal to] [n.sup.1/5] processors, and let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be a set of processors that is disjoint from each [S.sub.i], 1 [is less than or equal to] i [is less than or equal to] ??[n.sup.1/3]??. For all i, 1 [is less than or equal to] i [is less than or equal to] ??[n.sup.1/3]??, let h messages, each with destination [p.sub.i], be placed randomly at h processors in [S.sub.i]. By Theorem 3.3.5, for any deterministic algorithm using at most ([10.sup.-5]/5)10g h log n steps, the probability of a group [S.sub.i] successfully transmitting all h messages to [p.sub.i] is at most 1 - [n.sup.-1/4]. Hence the probability of success in all groups is at most [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (Notice that the analysis for each group is independent, since we are dealing with direct algorithms.) Therefore, the expected number of steps required is at least [10.sup.-6]log h log n. []

4. Concluding Remarks

For appropriate choices of a and b, the a out of b protocol can be used to emulate a single step of an n-processor EREW PRAM on an n-processor crossbar. As shown in Section 2, the delay associated with this simulation is O(log log n) whp. One way to optimize delay is to introduce parallel slackness. By simulating an m-processor PRAM on an n-processor crossbar (m [is greater than] n) with delay O(m/n), work-optimal simulations can be obtained [Karp et al. 1992]. It would be interesting to see if the techniques of Section 2 used to analyze the a out of b protocol can be applied to obtain tight analyses of work-optimal simulations.

The randomized lower bound for the Control Tower and the h-relation routing problems in Section 3 matches the upper bound of Gereb-Graus and Tsantilas [1992] up to a constant factor. In the deterministic case, however, there is factor of min{log h, log log n} (respectively, min(log h, log log n) log h) separating the best known upper and lower bounds for the Control Tower problem (respectively, h-relation routing problem). Closing this gap is an important open problem.

Appendix A. Technical Lemmas

LEMMA A. 1. For all integers m and n such that 3 [is less than or equal to] m [is less than or equal to] n, we have [m.sup.2]/3n [is less than or equal to] f(m) [is less than or equal to][m.sup.2]/n.

PROOF. By definition,

f(m) = m (1 - [(1 - 1/n).sup.m-1]).

Since [(1 - 1/n).sup.m-1] [is greater than or equal to] 1 - (m - 1)/n,

f(m) [is less than or equal to] m (1 - 1 + m - 1/n) [is less than or equal to] [m.sup.2]/n.

For the lower bound, since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

In the third step, we use (m - 2)/2n [is less than or equal to] 1/2, and in the last step, we use (m - 1)/2 [is greater than or equal to] m/3 for m [is greater than or equal to] 3. []

LEMMA A.2. For all integers m and n such that 6 [is less than or equal to] m [is less than or equal to] n, we have

[m.sup.3]/12[n.sup.2] [is less than or equal to] g(m) [is less than or equal to] [m.sup.3]/[n.sup.2].

PROOF. By definition,

g(m) = m (1 - [(1 - 1/n).sup.m-1] - m - 1/n [(1 - 1/n).sub.m-2]).

Since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

For the lower bound,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

In the last step, we use (m - 1)(m - 2) [is greater than or equal to] [m.sup.2]/2 for m [is greater than or equal to] 6. []

LEMMA A.3. If n and m are integers such that 2 [square of n] [is less than or equal to] m [is less than or equal to] n, then for all real x [is greater than or equal to] 0,

f(m(1 + x)) [is less than or equal to] [(1 + x).sup.2]f(m).

PROOF. By the definition of f,

f(m(1 + x)) = m(1 + x)(1 - [(1 - 1/n).sup.m(1+x)-1]).

We establish the desired inequality by proving that

(1 - [(1 - 1/n).sup.m-1+mx]) [is less than or equal to] (1 + x)(1 - [(1 - 1/n).sup.m-1]),

which is equivalent to showing that

[(1 - 1/n).sup.m-1+mx] [is greater than or equal to] [(1 - 1/n).sup.m-1] (1 + x) - x.

Since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The last step follows from the fact that for m [is greater than or equal to] 2 [square root of n], (1 + m/n) [is less than or equal to] [(1 - 1/n).sup.1-m]. []

COROLLARY A.4. If n and m are integers and x is real such that 0 [is less than or equal to] x [is less than] 1 and 2 [square root of n] [is less than or equal to] m(1 - x) [is less than or equal to] m [is less than or equal to] n, then:

f(m(1 + x)) [is less than or equal to] [(1 + x).sup.2]f(m), and

f(m(1 - x)) [is greater than or equal to] [(1 - x).sup.2]f(m).

PROOF. The first inequality follows directly from Lemma A.3. The second inequality is proved by applying Lemma A.3 substituting (m(1 - x), 1/(1 - x) - 1) for(m, x). []

LEMMA A.5. If n and m are integers such that n [is greater than or equal to] 9 and 10 [square root of n] [is less than or equal to] m [is less than or equal to] n, then for real x [is greater than or equal to] 0,

g(m(1 + x)) [is less than or equal to] [(1 + x).sup.4]g(m).

PROOF. By the definition of g,

g(m(1 + x)) = m(1 + x) (1 - [(1 - 1/n).sup.m(1+x)-1] - m(1 + x) - 1/n [(1 - 1/n).sup.m(1+x)-2]).

We establish the desired inequality by showing that

(1 - [(1 - 1/n).sup.m(1+x)-1] - m(1 + x) - 1/n [(1 - 1/n).sup.m(1+x)-2]) [is less than or equal to] [(1 + x).sup.3] (1 - [(1 - 1/n).sup.m-1] - m - 1/n [(1 - 1/n).sup.m-2]).

This is equivalent to showing that

[(1 - 1/n).sup.m-1+mx] + m(1 + x) - 1/n [(1 - 1/n).sup.m-2+mx] [is greater than or equal to] [(1 + x).sup.3] [(1 - 1/n).sup.m-1] + [(1 + x).sup.3] m - 1/n [(1 - 1/n).sup.m-2] -[x.sup.3] - [3x.sup.2] - 3x.

We have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The last step follows from the fact that (1 + (m - 1)/n + [m.sup.2]/3[n.sup.2]) [is less than or equal to] [(1 - 1/n).sup.-(m-2)] for n [is greater than or equal to] 9 and 10 [square root of n] [is less than or equal to] m [is less than or equal to] n. []

COROLLARY A.6. If n and m are integers and x is real such that 0 [is less than or equal to] x [is less than] 1, n [is greater than orequal to] 9, and 10 [square root of n] [is less than or equal to] m(1 - x) [is less than or equal to] m [is less than or equal to] n, then:

g(m(1 + x)) [is less than or equal to] [(1 + x).sup.4]g(m), and g(m(1 - x)) [is greater than or equal to] [(1 - x).sup.4]g(m).

PROOF. The first inequality follows directly from Lemma A.5. The second inequality is proved by applying Lemma A.5 substituting (m(1 - x), 1/(1 - x) - 1) for (m, x). []

LEMMA A.7. Let m [is greater than or equal to] 1 be an integer, and let y [is greater than or equal to] 2 be a real. The number of ways to choose at most m/[y.sup.3] items from a set of m items is at most m exp(m/y).

PROOF. If [m/y.sup.3] [is less than] 1, then we are considering the number of ways to choose 0 items, which is 1 [is less than or equal to ] m exp(m/y). If [m/y.sup.3] [is greater than or equal to] 1, then the number of ways to choose at most m/[y.sup.3] items can be bounded as follows: Note that we use the fact that for y [is greater than or equal to] 2, 1 + ln 2 + 3 ln y [is less than or equal to] [y.sup.2].

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

LEMMA A.8. Let y [is greater than or equal to] 1 be a real number, and j [is greater than or equal to] 0 be an integer. The number of ways to choose at most y[2.sup.-(j+1)] items from a set of at most y[2.sup.j] items is at most y exp(6y[(3/2).sup.-j]).

PROOF. If y[2.sup.-(j+1)] [is less than] 1 then we are considering the number of ways to choose 0 items, which is 1 [is less than or equal to] y exp(6y[(3/2).sup.-j]). Otherwise, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where the last inequality holds since (1 + (2j + 2)ln 2)[2.sup.-(j+1)] [is less than or equal to] 6[(3/2).sup.-j] for all integers j [is greater than or equal to] 0. []

LEMMA A.9. Let y [is greater than or equal to] 1 be a real number. Let <[S.sup.j]> be a sequence of disjoint sets with |[S.sub.j]| [is less than or equal to] y[2.sup.j] for all j [is greater than or equal to] 0. The number of ways to choose a sequence of sets <[T.sup.j]> with [T.sub.j] [subset or equal to] [S.sub.j] and |[T.sub.j| [is less than or equal to] y[2.sup.-(j+1)] for all j [is greater than or equal to] 0, is at most [y.sup.log y]exp(18 y).

PROOF. We will consider the product over all j [is greater than or equal to] 0, of the number of ways to choose [T.sub.j] from [S.sub.j]. Note that we only need to be concerned with j [is less than or equal to] log y, because for j [is greater than] log y, y[2.sup.-(j+1)] [is less than] 1, so we would be choosing 0 items. By Lemma A.8, we can bound the desired product by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

LEMMA A. 10. For all positive integers n and t such that n [is greater than or equal to] 4t, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

PROOF:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

ACKNOWLEDGMENTS. The authors would like to thank Noga Alon, Leslie Goldberg, Yossi Matias, Friedhelm Meyer auf der Heide, Aravind Srinivasan, Torsten Suel, and David Zuckerman for many helpful discussions.

(1) See, for example, Greenberg et al. [1987], Greenberg and Winograd [1985], Komlos and Greenberg [1985], and Martel and Vadya [1988].

(2) For previous work on nondirect h-relation routing on the OCPC, see Anderson and Miller [1988], Goldberg and Jerrum [1992], Goldberg et al. [1993], and Valiant [1990]; for recent work that also incorporates redundancy-based techniques, see Goldberg et al. [1994].

(3) See, for example, Alon and Spencer [1991], Chernoff [1952], Chvatal [1979], and Hoeffding [1963].

REFERENCES

ABRAMSON, N. 1973. The ALOHA system. In Computer-Communication Networks. N. Abramson and F. Kuo, eds. Prentice-Hall, Englewood Cliffs, N.J.

ALON, N. 1990. Transversal numbers of uniform hypergraphs. Graphs Combin. 6, 1-4.

ALON, N., BAR-NOY, A., LINIAL, N., AND PELEG, D. 1991. A lower bound for radio broadcast. J. Comput. Syst. Sci. 43, 290-298.

ALON, N., AND SPENCER, J.H. 1991. The Probabilistic Method. Wiley, New York.

ANDERSON, R. J., AND MILLER, G.L. 1988. Optical communication for pointer based algorithms. Tech. Rep. CRI-88-14, Computer Science Dept., Univ. Southern California.

CARTER, J. L., AND WEGMAN, M.N. 1979. Universal classes of hash functions. J. Comput. Syst. Sci. 18, 143-154.

CHERNOFF, H. 1952. A measure of the asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Stat. 23, 493-509.

CHVATAL, V. 1979. The tail of the hypergeometric distribution. Disc. Math. 25, 285-287.

DIETZFELBINGER, M., AND MEYER AUF DER HEIDE, F. 1993. Simple, efficient shared memory simulations. In Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures (Velen, Germany, June 30-July 2). ACM, New York, pp. 110-119.

GEREB-GRAUS, M., AND TSANTTLAS, T. 1992. Efficient optical communication in parallel computers. In Proceedings of the 4th Annual ACM Symposium on Parallel Algorithms and Architectures (San Diego, Calif., June 29-July 1). ACM, New York, pp. 41-48.

GOLDBERG, L. A., AND JERRUM, M. 1992. A sub-logarithmic communication algorithm for the completely connected optical communication parallel computer. Tech. Rep. ECS-LFCS-92-234 (September), Laboratory for Foundations of Computer Science, Department of Computer Science, University of Edinburgh, Edinburgh, Scotland.

GOLDBERG, L. A., JERRUM, M., LEIGHTON, T., AND RAO, S. 1993. A doubly logarithmic communication algorithm for the completely connected optical communication parallel computer. In Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures (Velen, Germany, June 30-July 2). ACM, New York, pp. 300-309.

GOLDBERG, L. A., MATIAS, Y., AND RAO, S.B. 1994. An optical simulation of shared memory. In Proceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures (Cape May, N.J., June 27-29). ACM, New York, pp. 257-267.

GREENBERG, A. G., FLAJOLET, P., AND LADNER, R. E. 1987. Estimating the multiplicities of conflicts to speed their resolution in multiple access channels. J. ACM 34, 289-325.

GREENBERG, A. G., AND WINOGRAD, S. 1985. A lower bound on the time needed in the worst case to resolve conflicts deterministically in multiple access channels. J. ACM 32, 589-596.

GREENBERG, R. I., AND LEISERSON, C.E. 1985. Randomized routing on fat-trees. In Proceedings of the 26th Annual IEEE Symposium on Foundations of Computer Science (Oct.), IEEE, New York, pp. 241-249.

HOEFFDING, W. 1963. Probability inequalities for sums of bounded random variables. JASA 58, 13-30.

KARP, R., LUBY, M., AND MEYER AUF DER HEIDE, F. 1992. Efficient PRAM simulation on a distributed memory machine. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing (Victoria, B.C., Canada, May 4-6). ACM, New York, pp. 318-326.

KOMLOS, J., AND GREENBERG, A.G. 1985. An asymptotically optimal nonadaptive algorithm for conflict resolution in multiple-access channels. IEEE Trans. Inf. Theory IT-31,302-306.

MARTEL, C. U., AND VADYA, T.P. 1988. The complexity of selection resolution, conflict resolution, and maximum finding on multiple access channels. In Proceedings of the 3rd International Workshop on Parallel Computation and VLSI Theory (1988), pp. 401-410.

METCALFE, R., AND BOGGS, D. 1976. Ethernet: Distributed packet switching for local computer networks. Commun. ACM 19, 7 (July), 395-404.

MEYER AUF DER HEIDE, F., SCHEIDELER, C., AND STEMANN, V. 1995. Exploiting storage redundancy to speed up randomized shared memory simulations. In Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, vol. 900 (March), Springer-Verlag, New York, pp. 267-278.

SIEGEL, A. 1989. On universal classes of fast high performance hash functions, their time-space tradeoff, and their applications. In Proceedings of the 30th IEEE Symposium on Foundations of Computer Science (Nov.). IEEE, New York, pp. 20-25. (Revised version).

UPFAL, E., AND WIGDERSON, A. 1987. How to share memory in a distributed system. J. ACM 34, 116-127.

VALIANT, L.G. 1990. General purpose parallel architectures. In Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity, J. van Leeuwen, ed., Elsevier/MIT Press, Cambridge, Mass., pp. 943-971.

YAO, A. C. 1983. Lower bounds by probabilistic arguments. In Proceedings of the 24th Annual IEEE Symposium on Foundations of Computer Science (Oct.). IEEE, New York, pp. 420-428.

RECEIVED JUNE 1994, REVISED JUNE 1997, ACCEPTED JUNE 1997

A preliminary version of this paper appeared in Proceedings of the 26th Annual ACM Symposium on Theory of Computing (Montreal, Que., Canada, May 23-25). ACM, New York, 1994, pp. 153-162.

While this research was conducted, P. D. MacKenzie and R. Rajaraman were at the Department of Computer Science at the University of Texas at Austin.

This research was supported by the National Science Foundation (NSF) CCR 91-11591 and the Texas Advanced Research Program under Grant nos. 91-003658-480 and 93-003658-461.

Authors' addresses: P. D. MacKenzie, Department of Mathematics and Computer Science, Boise State University, Boise, ID 83725; C. G. Plaxton, Department of Computer Science, Taylor Hall 2.124, University of Texas at Austin, Austin, TX 78712; R. Rajaraman, DIMACS Center, Rutgers University, P. O. Box 1179, Piscataway, NJ 08855.

Permission to make digital/hard copy of part or all of this work for personal or classroom use is granted without fee provided that the copies are not made or distributed for profit or commercial advantage, the copyright notice, the title of the publication, and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery (ACM), Inc. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee.

[C] 1998 ACM 0004-5411/98/0300-0324 $05.00

Printer friendly Cite/link Email Feedback | |

Author: | MACKENZIE, P. D.; PLAXTON, C. G.; RAJARAMAN, R. |
---|---|

Publication: | Journal of the Association for Computing Machinery |

Geographic Code: | 1USA |

Date: | Mar 1, 1998 |

Words: | 32245 |

Previous Article: | Randomized Binary Search Trees. |

Next Article: | Time to Publication: A Progress Report. |

Topics: |