Scheduling strategies and long-range dependence

Consider a single server queue with unit service rate fed by an arrival process of the following form: sessions arrive at the times of a Poisson process of rate λ, with each session lasting for an independent integer time τ ⩾ 1, where P(τ = k) = p _k with p _k ~ αk ^−(1+α) L(k), where 1 < α < 2 and L(·) is a slowly varying function. Each session brings in work at unit rate while it is active. Thus the work brought in by each arrival is regularly varying, and, because 1 < α < 2, the arrival process of work is long-range dependent. Assume that the stability condition λE[τ] < 1 holds. By simple arguments we show that for any stationary nonpreemptive service policy at the queue, the stationary sojourn time of a typical session must stochastically dominate a regularly varying random variable having infinite mean; this is true even if the duration of a session is known at the time it arrives. On the other hand, we show that there exist causal stationary preemptive policies, which do not need knowledge of the session durations at the time of arrival, for which the stationary sojourn time of a typical session is stochastically dominated by a regularly varying random variable having finite mean. These results indicate that scheduling policies can have a significant influence on the extent to which long-range dependence in the arrivals influences the performance of communication networks. This revised version was published online in June 2006 with corrections to the Cover Date.     

Performance of a Leaky Bucket System with Long-Range Dependent Input Traffic

The leaky bucket is a flow control mechanism that is designed to reduce the effect of the inevitable variability in the input stream into a node of a communication network. In this paper we study what happens when an input stream with heavy tailed work sessions arrives to a server protected by such a leaky bucket. Heavy tailed sessions produce long-range dependence in the input stream. Previous studies of the systems suggested that such long-range dependence can have dramatic effect on the system performance. By concentrating on the time until overflow of large finite buffers, we characterize the distribution of the time until buffer overflow, and we show that the leaky bucket flow control does make the system overflow less often, but long-range dependence still makes its presence felt.     

Infinite frequency solutions to discontinuous control systems with variable delay

In this article, we study the frequency of zeros in the solution tou′(t)=f(t, u(t−τ(t))), whereτ is a delay that depends on time, andf is a discontinuous function. First we show examples of solutions that have infinite frequency for autonomous systems with variable delay, and for non-autonomous systems with constant delay. Then we prove that infinite frequency solutions cannot come from finite frequency data. Also we prove that under certain conditions on the delay, the zero solution is the only solution that has infinitely many zeros in each interval of a fixed length.     

Subsequences of normal sequences

In this paper, we characterize a set of indices τ={τ(0)<τ(1)<…} such that forany normal sequence (α(0), α(1),…) of a certain type, the subsequence (α(τ(0)), α(τ(1)),…) is a normal sequence of the same type. Assume that_n→∞. Then, we prove that τ has this property if and only if the 0–1 sequence (θ _τ (0), whereθ _τ (i)=1 or 0 according asi∈{τ(j);j=0, 1,…} or not, iscompletely deterministic in the sense of B. Weiss.     

Noise sensitivity of Boolean functions and applications to percolation

It is shown that a large class of events in a product probability space are highly sensitive to noise, in the sense that with high probability, the configuration with an arbitrary small percent of random errors gives almost no prediction whether the event occurs. On the other hand, weighted majority functions are shown to be noise-stable. Several necessary and sufficient conditions for noise sensitivity and stability are given. Consider, for example, bond percolation on ann+1 byn grid. A configuration is a function that assigns to every edge the value 0 or 1. Let ω be a random configuration, selected according to the uniform measure. A crossing is a path that joins the left and right sides of the rectangle, and consists entirely of edges ℓ with ω(ℓ)=1. By duality, the probability for having a crossing is 1/2. Fix an ɛ ∈ (0, 1). For each edge ℓ, let ω′(ℓ)=ω(ℓ) with probability 1 − ɛ, and ω′(ℓ)=1 − ω(ℓ) with probability ɛ, independently of the other edges. Letp(τ) be the probability for having a crossing in ω, conditioned on ω′ = τ. Then for alln sufficiently large,P{τ : |p(τ) − 1/2| > ɛ}<ɛ.     

Some limit theorems for regenerative queues

We consider a single server queue with the interarrival times and the service times forming a regenerative sequence. This traffic class includes the standard models: iid, periodic, Markov modulated (e.g., BMAP model of Lucantoni [18]) and their superpositions. This class also includes the recently proposed traffic models in high speed networks, exhibiting long range dependence. Under minimal conditions we obtain the rates of convergence to stationary distributions, finiteness of stationary moments, various functional limit theorems and the continuity of stationary distributions and moments. We use the continuity results to obtain approximations for stationary distributions and moments of an MMPP/GI/1 queue where the modulating chain has a countable state space. We extend all our results to feed-forward networks where the external arrivals to each queue can be regenerative. In the end we show that the output process of a leaky bucket is regenerative if the input process is and hence our results extend to a queue with arrivals controlled by a leaky bucket. This revised version was published online in June 2006 with corrections to the Cover Date.     

Derivations on the Algebra of τ-Compact Operators Affiliated with a Type I von Neumann Algebra

Let M be a type I von Neumann algebra with the center Z, and a faithful normal semi-finite trace τ. Consider the algebra L(M, τ) of all τ-measurable operators with respect to M and let S ₀(M, τ) be the subalgebra of τ-compact operators in L(M, τ). We prove that any Z-linear derivation of S ₀(M, τ) is spatial and generated by an element from L(M, τ).      

A quantum spin system with random interactions I

We study a quantum spin glass as a quantum spin system with random interactions and establish the existence of a family of evolution groups {τ_t(ω)}_ω∈/Ω of the spin system. The notion of ergodicity of a measure preserving group of automorphisms of the probability space Ω, is used to prove the almost sure independence of the Arveson spectrum Sp(τ(ω)) of τ_t(ε). As a consequence, for any family of (τ(ω),β) — KMS states {ρ(ω)}, the spectrum of the generator of the group of unitaries which implement τ(ω) in the GNS representation is also almost surely independent of ω.     

Hyperidentities and solid varieties

Let V be a variety of type τ. A type τ hyperidentity of V is an identity of V which also holds in an additional stronger sense: for every substitution of terms of the variety (of appropriate arity) for the operation symbols in the identity, the resulting equation holds as an identity of the variety. Such identities were first introduced by Walter Taylor in [27] in 1981. A variety is called solid if all its identities also hold as hyperidentities. For example, the semigroup variety of rectangular bands is a solid variety. For any fixed type τ, the collection of all solid varieties of type τ forms a complete lattice which is a sublattice of the lattice L(τ) of all varieties of type τ. In this paper we give an overview of the study of hyperidentities and solid varieties, particularly for varieties of semigroups, culminating in the construction of an infinite collection of solid varieties of arbitrary type. This paper is dedicated to Walter Taylor. Received July 16, 2005; accepted in final form January 3, 2006. This paper is an expanded version of a talk presented at the Conference on Algebras, Lattices and Varieties in Honour of Walter Taylor, in Boulder Colorado, August 2004. The author’s research is supported by NSERC of Canada.     

Hypergraph families with bounded edge cover or transversal number

The transversal number, packing number, covering number and strong stability number of hypergraphs are denoted by τ, ν, ϱ and α, respectively. A hypergraph family t is called τ-bound (ϱ-bound) if there exists a “binding function”f(x) such that τ(H)≦f(v(H)) (ϱ(H)≦f(α(H))) for allH ∈ t. Methods are presented to show that various hypergraph families are τ-bound and/or ϱ-bound. The results can be applied to families of geometrical nature like subforests of trees, boxes, boxes of polyominoes or to families defined by hypergraph theoretic terms like the family where every subhypergraph has the Helly-property.     

An additive divisor problem with a growing number of factors

Let τk(n) be the number of representations ofn as the product ofk positive factors, τ(n)=τ(n). The asymptotics of Σ _n≤x τ _k (n)τ(n+1) for 80k ¹⁰ (lnlnx)³≤lnx is shown to be uniform with respect tok. Translated fromMatematicheskie Zametki, Vol. 61, No. 3, pp. 391–406, March, 1997. Translated by N. K. Kulman     

On Two Theorems of Finite Solvable Groups

For a finite group G, let T（G） denote a set of primes such that a prime p belongs to T（G） if and only if p is a divisor of the index of some maximal subgroup of G. It is proved that if G satisfies any one of the following conditions： （1） G has a p-complement for each p∈T（G）; （2）│T（G）│= 2： （3） the normalizer of a Sylow p-subgroup of G has prime power index for each odd prime p∈T（G）; then G either is solvable or G/Sol（G）≌PSL（2, 7） where Sol（G） is the largest solvable normal subgroup of G.     

Pointwise estimates of polynomials orthogonal on a circle with respect to a weight not belonging to the spaces Lr (r > 1)

Two-sided pointwise estimates are established for polynomials that are orthogonal on the circle |z| = 1 with respect to the weight ϕ(τ): = h(τ)|sin(τ/2)|⁻¹ g(|sin(τ/2)|) (τ ∈ ℝ), where g(t) is a concave modulus of continuity slowly changing at zero such that t ⁻¹ g(t) ∈ L ¹[0, 1] and h(τ) is a positive function from the class C _2π with a modulus of continuity satisfying the integral Dini condition. The obtained estimates are applied to find the order of the distance from the point t = 1 to the greatest zero of a polynomial orthogonal on the segment [−1, 1].     

Operator-semistable, operator semi-selfdecomposable probability measures and related nested classes on p-adic vector spaces

Let V be a finite dimensional p-adic vector space and let τ be an operator in GL(V). A probability measure μ on V is called τ-decomposable or m ? [(L)\tilde]₀(t)\mu\in {\tilde L}_0(\tau) if μ = τ(μ)* ρ for some probability measure ρ on V. Moreover, when τ is contracting, if ρ is infinitely divisible, so is μ, and if ρ is embeddable, so is μ. These two subclasses of [(L)\tilde]₀(t){\tilde L}_0(\tau) are denoted by L ₀(τ) and L ₀ ^#(τ) respectively. When μ is infinitely divisible τ-decomposable for a contracting τ and has no idempotent factors, then it is τ-semi-selfdecomposable or operator semi-selfdecomposable. In this paper, sequences of decreasing subclasses of the above mentioned three classes, [(L)\tilde]_m(t) é L_m(t) é L^#_m(t), 1 ￡ m ￡ ￥{\tilde L}_m(\tau)\supset L_m(\tau) \supset L^\#_m(\tau), 1\le m\le \infty , are introduced and several properties and characterizations are studied. The results obtained here are p-adic vector space versions of those given for probability measures on Euclidean spaces.     

Worst Case Traffic from Regulated Sources

We address the problem of finding the worst possible traffic a user of a telecommunications network can send. We take worst to mean having the highest effective bandwidth, a concept that arises in the Large Deviation theory of queueing networks. The traffic is assumed to be stationary and to satisfy leaky bucket constraints, which represent the a priori knowledge the network operator has concerning the traffic. Firstly, we show that this optimization problem may be reduced to an optimization over periodic traffic sources. Then, using convexity methods, we show that the realizations of a worst case source must have the following properties: at each instant the transmission rate must be either zero, the peak rate, or the leaky bucket rate; it may only be the latter when the leaky bucket is empty or full; each burst of activity must either start with the leaky bucket empty or end with it full.     

On sojourn times in <Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">GI</Emphasis> systems under state-dependent processor sharing

We consider a system with Poisson arrivals and i.i.d. service times. The requests are served according to the state-dependent processor-sharing discipline, where each request receives a service capacity which depends on the actual number of requests in the system. The linear systems of PDEs describing the residual and attained sojourn times coincide for this system, which provides time reversibility including sojourn times for this system, and their minimal non-negative solution gives the LST of the sojourn time V(τ) of a request with required service time τ. For the case that the service time distribution is exponential in a neighborhood of zero, we derive a linear system of ODEs, whose minimal non-negative solution gives the LST of V(τ), and which yields linear systems of ODEs for the moments of V(τ) in the considered neighborhood of zero. Numerical results are presented for the variance of V(τ). In the case of an M/GI/2-PS system, the LST of V(τ) is given in terms of the solution of a convolution equation in the considered neighborhood of zero. For service times bounded from below, surprisingly simple expressions for the LST and variance of V(τ) in this neighborhood of zero are derived, which yield in particular the LST and variance of V(τ) in M/D/2-PS.     

Dominated convergence in measure on semifinite von Neumann algebras and arithmetic averages of measurable operators

Consider a von Neumann algebra M with a faithful normal semifinite trace τ. We prove that each order bounded sequence of τ-compact operators includes a subsequence whose arithmetic averages converge in τ. We also prove a noncommutative analog of Pratt’s lemma for L ₁(M, τ). The results are new even for the algebra M = B(H) of bounded linear operators with the canonical trace τ = tr on a Hilbert space H. We apply the main result to L _p (M, τ) with 0 < p ≤ 1 and present some examples that show the necessity of passing to the arithmetic averages as well as the necessity of τ-compactness of the dominant.     

On the values of the divisor function

For a positive integer n we let τ(n) denote the number of its positive divisors. In this paper, we obtain lower and upper bounds for the average value of the ratio τ(n + 1)/τ(n) as n ranges through positive integers in the interval [1,x]. We also study the cardinality of the sets {τ(p − 1) : p ≤ x prime} and {τ(2ⁿ − 1) : n ≤ x}. Authors’ addresses: Florian Luca, Instituto de Matemáticas, Universidad Nacional Autónoma'de'México, C.P. 58089, Morelia, Michoacán, México; Igor E. Shparlinski, Department of Computing, Macquarie University, Sydney, NSW 2109, Australia     

Random ergodic theorems and real cocycles

We study mean convergence of ergodic averages associated to a measure-preserving transformation or flow τ along the random sequence of times κ _n (ω) given by the Birkhoff sums of a measurable functionF for an ergodic measure-preserving transformationT. We prove that the sequence (k _n(ω)) is almost surely universally good for the mean ergodic theorem, i.e., that, for almost every, ω, the averages (*) converge for every choice of τ, if and only if the “cocycle”F satisfies a cohomological condition, equivalent to saying that the eigenvalue group of the “associated flow” ofF is countable. We show that this condition holds in many natural situations. When no assumption is made onF, the random sequence (k _n(ω)) is almost surely universally good for the mean ergodic theorem on the class of mildly mixing transformations τ. However, for any aperiodic transformationT, we are able to construct an integrable functionF for which the sequence (k _n(ω)) is not almost surely universally good for the class of weakly mixing transformations.