Search

For X1 , X2 , ..., Xn a sequence of non-negative independent random variables with common distribution function F(t), X(n) denotes the maximum and Sn denotes the sum. The ratio variate Rn = X(n) / Sn is a quantity arising in the analysis of process speedup and the performance of scheduling. O’Brien (J. Appl. Prob. 17:539–545, 1980) showed that as n → ∞, Rn →0 almost surely iff \({\sf E} X_1\) is finite. Here we show that, provided either (1) \({\sf E} X_1^2 \) is finite, or (2) 1 − F (t) is a regularly varying function with index ρ < − 1, then \({\sf E} R_n \sim { {\sf E} X_{(n)} }/{{\sf E} S_n } ,( n \rightarrow \infty )\). An integral representation for the expected ratio is derived, and lower and upper asymptotic bounds are developed to obtain the result. Since \({\sf E} X_{(n)}\) is often known or estimated asymptotically, this result quantifies the rate of convergence of the ratio’s expected value. The result is applied to the performance of multiprocessor scheduling.

Let ${\cal G}_d (n)$ be the set of d-regular simple graphs with n vertices, and for $G = (V,E)$ in ${\cal G}_d (n)$ let $f: V \to \{1,2, \ldots, n \}$ be a bijective coloring of the vertices of G. Also let $\alpha$ denote an interference parameter in $\{0,1, \ldots, n-1 \}$, and define the interference number of f with respect to G and $\alpha$ as the number of edges $\{u,v\}$ in $E$ for which $\min \{ | f(u) - f(v) |$, $n- | f(u) - f(v) | \} \le \alpha$. We consider two interference number problems for feasible $(n, \alpha, d)$. The first is to specify a $G \in {\cal G}_d (n)$ and an f for which the interference number is as small as possible. The second is to determine a $G \in {\cal G}_d (n)$ whose minimum interference number over all f is as large as possible. A previous paper completely solves both problems for d = 2. The present paper solves the first problem for all $d \ge 3$ and obtains partial results for the second problem for $d \ge 3$ that focus on interference-minimizing f's when G consists of disjoint copies of $K_{d+1}$.

Communications problems that involve frequency interference, such as the channel assignment problem in the design of cellular telephone networks, can be cast as graph coloring problems in which the frequencies (colors) assigned to an edge's vertices interfere if they are too similar. The paper considers situations modeled by vertex-coloring d-regular graphs with n vertices using a color set 1, 2,..., n, where colors i and j are said to interfere if their circular distance $\min \{ | i-j | , n- | i-j | \}$ does not exceed a given threshold value $\alpha$. Given a d-regular graph G and threshold $\alpha$, an interference-minimizing coloring is a coloring of vertices that minimizes the number of edges that interfere. Let $I_\alpha (G)$ denote the minimum number of interfering edges in such a coloring of $G$. For most triples $(n, \alpha ,d),$ we determine the minimum value of $I_\alpha (G)$ over all d-regular graphs and find graphs that attain it. In determining when this minimum value is 0, we prove that for $r \geq 3$ there exists a d-regular graph G on n vertices that is r-colorable whenever $d \leq (1- \frac{1}{r}) n-1$ and nd is even. We also study the maximum value of $I_\alpha (G)$ over all d-regular graphs and find graphs that attain this maximum in many cases.

The Nelder--Mead simplex algorithm, first published in 1965, is an enormously popular direct search method for multidimensional unconstrained minimization. Despite its widespread use, essentially no theoretical results have been proved explicitly for the Nelder--Mead algorithm. This paper presents convergence properties of the Nelder--Mead algorithm applied to strictly convex functions in dimensions 1 and 2. We prove convergence to a minimizer for dimension 1, and various limited convergence results for dimension 2. A counterexample of McKinnon gives a family of strictly convex functions in two dimensions and a set of initial conditions for which the Nelder--Mead algorithm converges to a nonminimizer. It is not yet known whether the Nelder--Mead method can be proved to converge to a minimizer for a more specialized class of convex functions in two dimensions.

A double-loop network with hop constants h1, h2, DL(n, h1, h2) may be represented as a directed graph with n nodes 0, 1, …, n − 1 and 2n links of the form i → i + h1mod n and i → i + h2mod n (referred to as h1-links and h2-links). They have been proposed as architectures for local area networks and for data alignment in SIMD processors, among other applications. Three reliability models of double-loop networks have been studied in the literature. In the link model, nodes always work and each link fails independently with probability p. Hwang and Li showed that for p small DL(n, 1, 1 + n/2) is most reliable for n even, and DL(n, 1, 2) is most reliable for n odd. In the node model, links always work and each node fails independently with probability p. Hu et al. showed that for p small DL(n, 1, 1 + ⌈n/2⌉) is the most reliable. However, no nonenumerative algorithms were given to compute the reliabilities of these most reliable networks except DL(n, 1, 1 + n/2) for even n under the node model. Recently, Hwang and Wright proposed a novel approach to compute the reliabilities of double-loop networks under the uniform model that each node fails with probability p, each h1-link with probability p1, and each h2-link with probability p2, and the failures are independent. In particular, they obtained the reliabilities for DL(n, 1, 2). In this paper, we applied their approach to compute the reliabilities of DL(n, 1, 1 + ⌈n/2⌉) under the uniform model, except that for n odd we need the assumption that h1-links always work. Note that even under this additional assumption our reliability model is more general than is the node model, the original model under which DL(n, 1, 1 + ⌈n/2⌉) is found to be most reliable for n odd. We also used this approach to obtain the reliabilities of DL(n, 1, n − 2), known as the daisy chain in the literature. © 1997 John Wiley & Sons, Inc. Networks 30: 81–90, 1997

In the combinatorial version of the generalized birthday problem, w1's and n−w 0's are randomly arranged in either a line or a cycle; km is defined to be the largest number of 1's appearing within any m consecutive positions. In the binomial version, each point is independently 1 with probability p and 0 with probability 1−p. Current algorithms for computing Pr(km The generalized birthday problem corresponds to a test for non-random clustering and has applications in statistical trials. Applications to reliability theory are also discussed.

Fast, efficient parallel algorithms are presented for discrete event simulations of dynamic channel assignment schemes for wireless cellular communication networks. The driving events are called arrivals and departures, in continuous time, to cells geographically distributed across the service area. A dynamic channel assignment scheme decides which call arrivals to accept, and which channels to allocate to the accepted calls, attempting to minimize call blocking while ensuring co-channel interference is tolerably low. Specifically, the scheme ensures that the same channel is used concurrently at different cells only if the pairwise distances between those cells are sufficiently large. Much of the complexity of the system comes from ensuring this separation. The network is modeled as a system of interacting continuous time automata, each corresponding to a cell. To simulate the model, we use conservative methods; i.e., methods in which no errors occur in the course of the simulation and so no rollback or relaxation is needed. Implemented on a 16K processor MasPar MP-1, an elegant and simple technique provides speedups of about 15x over an optimized serial simulation running on a high speed workstation. A drawback of this technique, typical of conservative methods, is that processor utilization is rather low. To overcome this, we developed new methods that exploit slackness in event dependencies over short intervals of time, thereby raising the utilization to above 50% and the speedup over the optimized serial code to about 120x with respect to the workstation simulation.

Consider a closed, N -node, cyclic network, where each node has an independent, exponential single server. Using lattice-Bessel functions, we can explicitly solve for the transition probabilities of events that occur prior to one of the nodes becoming empty. This calculation entails associating with this absorbing process a symmetry group that is the semidirect product of simpler groups. As a byproduct, we are able to compute explicitly the entire spectrum for the finite-dimensional matrix generator of this process. When the number of nodes exceeds 1, such a spectrum is no longer purely real. Moreover, we are also able to obtain the quasistationary distribution or the limiting behavior of the network conditioned on no node ever being idle.

This paper provides an examination of an abstract moving-server system that models several computer applications, including software debugging and accessing compressed data. In this model, the server moves on the unit interval $[0,1]$, serving requests where they are encountered. The locations of successive requests are not known in advance, but they are known to be independent samples from a given distribution F on $[0,1]$. Before serving a request, the server must be moved to a reset point to the left of the request. There is a choice of two reset points, one fixed at 0 and one, called the checkpoint, that can be moved in the course of serving requests. The cost of serving a request is proportional to the distance moved to the request from the chosen reset point. This paper formulates a stochastic optimization problem whose solution, for a wide class of distributions F, yields a policy for deciding the successive locations of the checkpoint so as to minimize the expected total cost of serving a sequence...

We consider the double queue arising from a system consisting of two processors serving three job streams generated by independent Poisson sources. The central job stream of rate v consists of jobs which place resource demands on both processors, which are handled separately by each processor once the request is made. In addition, the first processor receives background work at a rate of λwhile the second receives similar tasks at a rate η. Each processor has exponentially distributed service times with rates α and β respectively. A functional equation is found for P(z, w), the generating function of the joint queue-length distribution, which leads to a relation between P(z, 0) and P(0, w) in the region |z|, |w| < 1 of a complex algebraic curve associated with the problem. The curve is parametrized by elliptic functions z(ξ) and w(ξ) and the relation between Ρ (z(ξ), 0) and P(0, w(ξ)) persists on their analytic continuation as elliptic functions in the ξ-plane. This leads to their eventual determination by an appeal to the theory of elliptic functions. From this determination we obtain asymptotic limit laws for the expectations of the mean number of jobs in each queue conditioned on the other, as the number of jobs in both processors tends to∞. Transitions are observed in the asymptotic behavior of these quantities as one crosses various boundaries in the parameter space. An interpretation of these results via the theory of large deviations is presented.

Customers, in a Poisson stream at rate $\lambda $, enter an infinite-server queue. Customer service times are independent and uniformly distributed on $[ 0,s ],\, s > 0$. Gated service is performed in stages as follows. A stage begins with all customers transferred from the queue to the servers. The servers then begin serving these customers, all simultaneously. The stage ends when the service of all customers is complete. At this point, the next stage begins if the queue is nonempty. If the queue is empty, the servers just remain idle, awaiting the next arrival, at which time the next stage begins.This paper develops asymptotics for the equilibrium distribution of the number served in a stage in the light and heavy traffic regimes $\lambda \to 0$ and $\lambda \to \infty $, respectively. The results are obtained by the analysis of a Fredholm integral equation of the second kind. For computational purposes, the integral equation is transformed into an infinite system of linear algebraic equations. The effe...

We analyze gated, exhaustive service of an infinite-server system with vacations. Customers enter a queue in a Poisson stream. The servers, working in parallel, serve customers in stages. A stage begins with all customers transferred from the queue to the servers (the gate opens). The servers then begin serving these customers, all simultaneously. The stage ends when their services are completed. Service is exhaustive because the servers must again examine the queue to see if any new customers arrived during the last stage. If there are any, a new stage begins. If there are none, the servers move on to other work. The time spent away from the queue is called vacation time. The queue may represent a node or station in a data transmission network and the servers may be communication channels.We analyze the equilibrium behavior of the number of requests served during a stage for general service and vacation time distributions. This analysis leads to the solution of a Fredholm integral equation of the second kind. We find conditions under which the system is stable and compute bounds on performance metrics of interest. Approximate techniques are introduced and tested. Finally, an extension to polling systems is studied.

We analyze the concurrent-read exclusive-write protocol for access to a shared resource, such as occurs in database and distributed operating systems. Readers arrive according to a Poisson process and acquire shareable i.e., non-exclusive, locks which, once granted, are released after a generally distributed random period. Writers arrive according to an arbitrary renewal process and acquire exclusive locks which, once granted, are held for a random time which is also generally distributed. Locks are granted in the order in which requests are received.We derive necessary and sufficient conditions under which the queue is stable i.e., the Iatencies for reader/writer lock acquisition have a limiting distribution. In the unstable case, the delays of successive readers/writers become unbounded. The stability condition is sensitive to the interarrival-time distribution of the writers and the lock holding-time distribution of the readers but depends only on the mean lock holding-time of the writers.Distributional and moment bounds are given for the latencies of read/write requests.

In this note, we prove a generalization of a theorem of Morrison (Notices Amer. Math. Soc. 1962, 119) which states that the only real finite symmetric convolution integral operator K in L2[−1, 1] with kernel ϱ analytic about the origin, which admits a second order, singular symmetric differential operator in its commutator is (aside from a trivial scaling) given by Kφ(x) = ∝−1+1 ϱ(x − y) φ(y) dy, φ ϵ L2[−1, 1], with ϱ(x) = Ω 2 sinh Ω 1 x Ω 1 sinh Ω 2 x , −2 ⩽ x ⩽ 2 , where Ω 1 and Ω 2 are either real or pure imaginary. If either Ω 1 , or Ω 2 = 0 , one takes the appropriate limit. The associated commuting differential operator is L = d dx a(x) d dx + b(x) , with a(x) = 1 − sinh 2 Ω 2 x sinh 2 Ω 2 and b(x) = (Ω 1 2 − Ω 2 2 ) a(x) + Ω 3 . Here Ω 3 is an arbitrary real constant. Our result states that this remains true, under the relaxed assumptions that ϱ is C2, with 0 as a non-degenerate critical point, and a(x) and b(x) are C1 and C0, respectively. Thus under a mild smoothness and non-degeneracy hypothesis, the only examples are those in which K is a time-and-band limiting operator and L is the operator originally found by Landau, Pollak, and Slepian.

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.

We analyze the concurrent-read exclusive-write protocol for access to a shared resource, such as occurs in database and distributed operating systems. Readers arrive according to a Poisson process and acquire shareable i.e., non-exclusive, locks which, once granted, are released after a generally distributed random period. Writers arrive according to an arbitrary renewal process and acquire exclusive locks which, once granted, are held for a random time which is also generally distributed. Locks are granted in the order in which requests are received.We derive necessary and sufficient conditions under which the queue is stable i.e., the Iatencies for reader/writer lock acquisition have a limiting distribution. In the unstable case, the delays of successive readers/writers become unbounded. The stability condition is sensitive to the interarrival-time distribution of the writers and the lock holding-time distribution of the readers but depends only on the mean lock holding-time of the writers.Distributional and moment bounds are given for the latencies of read/write requests.

How many sublattices of index N are there in the planar hexagonal lattice? Which of them are the best from the point of view of packing density, signal-to-noise ratio, or energy? We answer the first question completely and give partial answers to the other questions.

This paper studies a dual of classical stochastic scheduling of parallel processor systems. The given data are n jobs with running times T 1 ,…, T n and waiting-time constraints W 1 ,…, W n ; these sequences are independent and each consists of i.i.d. random variables. Although the T i and W i are not known in advance, they are known to be samples from exponential distributions with given parameters. Scheduling policies are nonpreemptive and have the option, for each i , of making the i th job wait during [0, W i ). However, by the random deadline W i , the i th job must be assigned to a processor, if it is still waiting. In this paper, we find a policy that minimizes the expected number of processors used, among all policies of the above type. We also estimate the expected number of processors used under this policy. There appears to be no simple, exact formula for this quantity, so we turn to an asymptotic analysis based on a continuous approximation.