We consider N processors communicating unidirectionally over a closed transmission channel, or ring. Each message is assembled into a fixed-length packet. Packets to be sent are generated at random times by the processors, and the transit times spent by packets on the ring are also random. Packets being forwarded, i.e., packets already on the ring, have priority over waiting packets. The objective of this paper is to analyze packet waiting times under a greedy policy within a discrete Markov model that retains the overall structure of a practical system but is simple enough so that explicit results can be proved. Independent, identical Bernoulli processes model message generation at the processors, and independently and identically distributed (i.i.d.) geometric random variables model the transit times. Our emphasis is on asymptotic behavior for large ring sizes, N, when the respective rate parameters have the scaling $\lambda /N$ and $\mu /N$. Our main result shows that, if the traffic intensity is fixed at $\rho = \lambda / \mu < 1$, then as $N \to \infty$ the expected time a message waits to be put on the ring is bounded by a constant. This result verifies that the expected waiting time under the greedy policy is within a constant factor of that under an optimal policy.

We consider schemes for reuse-efficient packet access in wireless data networks. We show that computing the maximum ergodic packet arrival rate is NP-hard. We give an upper bound on the maximum ergodic throughput in terms of the eigenvalues of matrices related to the path-gain matrix. We present simple, practical heuristic algorithms which exhibit good throughput and packet delay and report on results of preliminary simulations. More sophisticated algorithms that yield optimal throughput are also presented. A recent result of McKeown, Anantharam and Walrand (1996) on scheduling of input-queued switches is obtained as a by-product.

Let G3n,p,3 be a random 3-colorable graph on a set of 3n vertices generated as follows. First, split the vertices arbitrarily into three equal color classes, and then choose every pair of vertices of distinct color classes, randomly and independently, to be edges with probability p. We describe a polynomial-time algorithm that finds a proper 3-coloring of G3n,p,3 with high probability, whenever p $\geq$ c/n, where c is a sufficiently large absolute constant. This settles a problem of Blum and Spencer, who asked if an algorithm can be designed that works almost surely for p $\geq$ polylog(n)/n [J. Algorithms, 19 (1995), pp. 204--234]. The algorithm can be extended to produce optimal k-colorings of random k-colorable graphs in a similar model as well as in various related models. Implementation results show that the algorithm performs very well in practice even for moderate values of c.

An upper bound is given on the minimum distance between i subsets of same size of a regular graph in terms of the ith largest eigenvalue in absolute value. This yields a bound on the diameter in terms of the ith largest eigenvalue for any integer i. Our bounds are shown to be asymptotically tight for explicit families of graphs having an asymptotically optimal ith largest eigenvalue. A result by Quenell [Adv. Math., 106 (1994), pp. 122--148] relating the diameter, the second eigenvalue, and the girth of a regular graph is obtained as a by-product.

Consider a set of n processors that can communicate with each other. Assume that each processor can be either "good" or "faulty". Also assume that the processors can test each other. We consider how to use parallel testing rounds to identify the faulty processors, given an upper bound t on their number. We prove that 4 rounds are necessary and sufficient when 2/spl radic/(2n)/spl les/0.03n (for n sufficiently large). Furthermore, at least 5 rounds are necessary when t/spl ges/0.49n (for n sufficiently large), and 10 rounds are sufficient when t<0.5n (for all n). (It is well known that no general solution is possible when t/spl ges/0.5n).

We establish a lower bound of (1:12 \\Gamma o(1)) n log n on the size of any n-input sorting network; this is the first lower bound that improves upon the trivial information-theoretic bound by more than a lower order term. We then extend the lower bound to comparator networks that approximately sort a certain fraction of all input permutations. We also prove a lower bound of (c \\Gamma o(1)) log n, where c ß 3:27, on the depth of any sorting network; the best previous result of approximately (2:41 \\Gamma o(1)) log n was established by Yao in 1980. Our result for size is based on a new technique that lower bounds the number of "0--1 collisions " in the network; we provide strong evidence that the technique will lead to even better lower bounds. 1 Part of this work was done while the author was at DIMACS. 2 XEROX Palo Alto Research Center, 3333 Coyote Hill Road, Palo Alto, CA 94304. Partially supported by the NSF under grant CCR-9404113. Email: [email protected]. 3 Department o...

The spectral method is the best currently known technique to prove lower bounds on expansion. Ramanujan graphs, which have asymptotically optimal second eigenvalue, are the best-known explicit expanders. The spectral method yielded a lower bound of k /4 on the expansion of linear-sized subsets of k -regular Ramanujan graphs. We improve the lower bound on the expansion of Ramanujan graphs to approximately k /2. Moreover, we construct a family of k -regular graphs with asymptotically optimal second eigenvalue and linear expansion equal to k /2. This shows that k /2 is the best bound one can obtain using the second eigenvalue method. We also show an upper bound of roughly 1 + √k - 1 on the average degree of linear-sized induced subgraphs of Ramanujan graphs. This compares positively with the classical bound 2√k - 1. As a byproduct, we obtain improved results on random walks on expanders and construct selection networks (respectively, extrovert graphs) of smaller size (respectively, degree) than was previously known.

Let G(3n, p, 3) be a random 3-colorable graph on a set of 3n vertices generated as follows.First, split the vertices arbitrarily into three equal color classes and then choose every pair of vertices of distinct color classes, randomly and independently, to be an edge with probability p.We describe a polynomial time algorithm that finds a proper 3coloring of G(3n, p, 3) with high probability, whenever p ~c/n, where c is a sufficiently large absolute constant.This settles a problem of Blum and Spencer, who asked if one can design an algorithm that works almost surely for p ~polylog(n)/n.The algorithm can be extended to produce optimal kcolorings of random k-colorable graphs in a similar model, as well as in various related models.

The authors investigate the relation between the second eigen-value and the linear expansion of regular graphs. The spectral method is the best currently known technique to prove lower bounds on the expansion. He improves this technique by showing that the expansion coefficient of linear-sized subsets of a k-regular graph G is at least k/2(1- square root max(0,1-/sub lambda 1(G)2//sup 4k-4/))/sup -/ , where lambda /sub 1/(G) is the second largest eigenvalue of the graph. In particular, the linear expansion of Ramanujan graphs, which have the property that the second largest eigenvalue is at most 2 square root k-1, is at least (k/2)/sup -/. This improves upon the best previously known lower bound of 3(k-2)/8. For any integer k such that k-1 is prime, he explicitly constructs an infinite family of k-regular graphs G/sub n/ on n vertices whose linear expansion is k/2 and such that lambda /sub 1/(G/sub n/)>

The expansion properties of regular graphs are investigated. The best previously known expansion of subsets of linear size of explicit k-regular graphs is k/4. This bound is achieved by nonbipartite Ramanujan graphs of degree k=p+1, which have the property that all but the largest eigenvalue have absolute value at most 2 square root p. The expansion coefficient for linear subsets for nonbipartite Ramanujan graphs is improved to 3(k-2)/8. Other results are established, including improved results about random walks on expanders.>