In large storage systems, files are often coded across several servers to improve reliability and retrieval speed. We study load balancing under the batch sampling routeing scheme for a network of n servers storing a set of files using the maximum distance separable (MDS) code (cf. Li (2016)). Specifically, each file is stored in equally sized pieces across L servers such that any k pieces can reconstruct the original file. When a request for a file is received, the dispatcher routes the job into the k-shortest queues among the L for which the corresponding server contains a piece of the file being requested. We establish a law of large numbers and a central limit theorem as the system becomes large (i.e. n → ∞), for the setting where all interarrival and service times are exponentially distributed. For the central limit theorem, the limit process take values in ℓ2, the space of square summable sequences. Due to the large size of such systems, a direct analysis of the n-server system is frequently intractable. The law of large numbers and diffusion approximations established in this work provide practical tools with which to perform such analysis. The power-of-d routeing scheme, also known as the supermarket model, is a special case of the model considered here.

In this work, we study a new model for continuum line-of-sight percolation in a random environment driven by the Poisson–Voronoi tessellation in the d-dimensional Euclidean space. The edges (one-dimensional facets, or simply 1-facets) of this tessellation are the support of a Cox point process, while the vertices (zero-dimensional facets or simply 0-facets) are the support of a Bernoulli point process. Taking the superposition Z of these two processes, two points of Z are linked by an edge if and only if they are sufficiently close and located on the same edge (1-facet) of the supporting tessellation. We study the percolation of the random graph arising from this construction and prove that a 0–1 law, a subcritical phase, and a supercritical phase exist under general assumptions. Our proofs are based on a coarse-graining argument with some notion of stabilization and asymptotic essential connectedness to investigate continuum percolation for Cox point processes. We also give numerical estimates of the critical parameters of the model in the planar case, where our model is intended to represent telecommunications networks in a random environment with obstructive conditions for signal propagation.

Consider a saturated porous m edium in which water is flowing slowly with a steady velocity. Suppose at some space-time scale the concentration C(x, r) of a non-reactive dilute solute is governed by the following Fokker-Planck differential equation:

A two-dimensional linear birth and death process is a continuous-time Markov chain Y(·) with state space (Z+)2 which can jump from the point (n, m) to one of its four neighbors, with rates that are linear functions of n and m. Criteria are extended for determining whether such a process has a positive probability or zero probability of escaping to infinity. In the transient case considered, the projections of the imbedded Markov chain {Xn} of the successive states visited by Y(·) on a suitable pair of orthonormal vectors v and w are shown to be regularly varying sequences with index 1. Specifically, (Xn, v)∽δn and (Xn, w)∽ kn/log n for positive constants δ and k.

In this paper, we obtain Markovian bounds on a function of a homogeneous discrete time Markov chain. For deriving such bounds, we use well-known results on stochastic majorization of Markov chains and the Rogers–Pitman lumpability criterion. The proposed method of comparison between functions of Markov chains is not equivalent to generalized coupling method of Markov chains, although we obtain same kind of majorization. We derive necessary and sufficient conditions for existence of our Markovian bounds. We also discuss the choice of the geometric invariant related to the lumpability condition that we use.

We study the present value Z∞ = ∫0∞ e-Xt-dYt where (X,Y) is an integrable Lévy process. This random variable appears in various applications, and several examples are known where the distribution of Z∞ is calculated explicitly. Here sufficient conditions for Z∞ to exist are given, and the possibility of finding the distribution of Z∞ by Markov chain Monte Carlo simulation is investigated in detail. Then the same ideas are applied to the present value Z-∞ = ∫0∞ exp{-∫0tRsds}dYt where Y is an integrable Lévy process and R is an ergodic strong Markov process. Numerical examples are given in both cases to show the efficiency of the Monte Carlo methods.

This paper considers a queueing system with two classes of customers and a single server, where the service policy is of threshold type. As soon as the amount of work required by the class 1 customers is greater than a fixed threshold, the class 1 customers get the server's attention; otherwise the class 2 customers have the priority. Service interruptions can occur for both classes of customers on the basis of the above description of the service mechanism, and in this case the service interruption discipline is preemptive resume priority (PRP). This model, which turns out to be a generalization of the PRP queueing system, has potential applications in computer systems and in communication networks. For Poisson inputs, exponential (arbitrary) servicetime distribution for class 1 (class 2) customers, we derive the Laplace–Stieltjes transform of the stationary joint distribution of the workload of the server, by reducing the analysis to the resolution of a boundary value problem. Explicit formulas are obtained.

We consider a branching Brownian motion on starting with n particles of mass 1/n, with interactive branching dynamics. The parameters are unsealed, but depend on the present state of the measure-valued process. For this mean-field model, which is a generalization of Chauvin and Rouault (1990) and Nappo and Orlandi (1988), we prove a propagation of chaos and a fluctuation theorem in ([0, T]; W–5).

We consider the M/M/∞ queue with m primary servers and infinitely many secondary servers. All the servers are numbered and ordered. An arriving customer takes the lowest available server. We define the wasted spaces as the difference between the highest numbered occupied server and the total number of occupied servers. Letting ρ = λ0/μ be the ratio of arrival to service rates, we study the probability distribution of the wasted spaces asymptotically for ρ → ∞. We also give some numerical results and the tail behavior for ρ = O(1).

Many authors have discussed the equivalence of partial balance and insensitivity in in stochastic processes. When speeds are introduced into a stochastic process there arises a difficulty in proving the necessity of partial balance for insensitivity. Previous authors have overcome this difficulty by assuming that a process has the property of instantaneous attention. This property enforces the requirement that no lifetime can be created in a state in which that lifetime has zero speed.

In this paper it is shown that for processes with a finite state space it is unnecessary to make this assumption provided the notion of partial balance is slightly changed. Thus we give a criterion, analogous to partial balance, which is necessary and sufficient for insensitivity even in processes which do not possess the property of instantaneous attention. When a process does have instantaneous attention this criterion is equivalent to partial balance.

A random binary search tree grown from the uniformly random permutation of [n] is studied. We analyze the exact and asymptotic counts of vertices by rank, the distance from the set of leaves. The asymptotic fraction ck of vertices of a fixed rank k ≥ 0 is shown to decay exponentially with k. We prove that the ranks of the uniformly random, fixed size sample of vertices are asymptotically independent, each having the distribution {ck}. Notoriously hard to compute, the exact fractions ck have been determined for k ≤ 3 only. We present a shortcut enabling us to compute c4 and c5 as well; both are ratios of enormous integers, the denominator of c5 being 274 digits long. Prompted by the data, we prove that, in sharp contrast, the largest prime divisor of the denominator of ck is at most 2k+1 + 1. We conjecture that, in fact, the prime divisors of every denominator for k > 1 form a single interval, from 2 to the largest prime not exceeding 2k+1 + 1.

Continuous-space-time branching processes (CSBP) are investigated in order to model random energy cascades. CSBPs are based on spectrally positive Lévy processes and, as such, are characterized by their corresponding Laplace exponents. Special emphasis is put on the CSBPs of Feller, Lamperti and Neveu and on their Poisson point process representations. The Neveu model (either supercritical or subcritical) is of particular interest in physics for its connection with the random energy model of Derrida, as revisited by Ruelle. Exploiting some connections between the partition functions of energy and the Poisson-Dirichlet distributions of Pitman and Yor, some information on the zero-temperature limit is extracted. Finally, for the subcritical versions of the three models, we compute the distribution of some of their interesting features: extinction time and probability, area under the profile (total energy) and width (maximal energy).

Let F(x) denote a distribution function in Rd and let F*n(x) denote the nth convolution power of F(x). In this paper we discuss the asymptotic behaviour of 1 - F*n(x) as x tends to ∞ in a certain prescribed way. It turns out that in many cases 1 - F*n(x) ∼ n(1 - F(x)). To obtain results of this type, we introduce and use a form of subexponential behaviour, thereby extending the notion of multivariate regular variation. We also discuss subordination, in which situation the index n is replaced by a random index N.

We consider the flow of service starting times in the M/G/1/∞ queue and study some of its equilibrium properties.

Consider two independent Goldstein-Kac telegraph processes X1(t) and X2(t) on the real line ℝ. The processes Xk(t), k = 1, 2, describe stochastic motions at finite constant velocities c1 > 0 and c2 > 0 that start at the initial time instant t = 0 from the origin of ℝ and are controlled by two independent homogeneous Poisson processes of rates λ1 > 0 and λ2 > 0, respectively. We obtain a closed-form expression for the probability distribution function of the Euclidean distance ρ(t) = |X1(t) - X2(t)|, t > 0, between these processes at an arbitrary time instant t > 0. Some numerical results are also presented.

In order to estimate the specific intrinsic volumes of a planar Boolean model from a binary image, we consider local digital algorithms based on weighted sums of 2×2 configuration counts. For Boolean models with balls as grains, explicit formulas for the bias of such algorithms are derived, resulting in a set of linear equations that the weights must satisfy in order to minimize the bias in high resolution. These results generalize to larger classes of random sets, as well as to the design-based situation, where a fixed set is observed on a stationary isotropic lattice. Finally, the formulas for the bias obtained for Boolean models are applied to existing algorithms in order to compare their accuracy.

For a family of linear preferential attachment graphs, we provide rates of convergence for the total variation distance between the degree of a randomly chosen vertex and an appropriate power law distribution as the number of vertices tends to ∞. Our proof uses a new formulation of Stein's method for the negative binomial distribution, which stems from a distributional transformation that has the negative binomial distributions as the only fixed points.

A bootstrap percolation process on a graph with n vertices is an ‘infection’ process evolving in rounds. Let $r \ge 2$ be fixed. Initially, there is a subset of infected vertices. In each subsequent round, every uninfected vertex that has at least r infected neighbors becomes infected as well and remains so forever.

We consider this process in the case where the underlying graph is an inhomogeneous random graph whose kernel is of rank one. Assuming that initially every vertex is infected independently with probability $p \in (0,1]$, we provide a law of large numbers for the size of the set of vertices that are infected by the end of the process. Moreover, we investigate the case $p = p(n) = o(1)$, and we focus on the important case of inhomogeneous random graphs exhibiting a power-law degree distribution with exponent $\beta \in (2,3)$. The first two authors have shown in this setting the existence of a critical $p_c =o(1)$ such that, with high probability, if $p =o(p_c)$, then the process does not evolve at all, whereas if $p = \omega(p_c)$, then the final set of infected vertices has size $\Omega(n)$. In this work we determine the asymptotic fraction of vertices that will eventually be infected and show that it also satisfies a law of large numbers.

Random intersection graphs model networks with communities, assuming an underlying bipartite structure of communities and individuals, where these communities may overlap. We generalize the model, allowing for arbitrary community structures within the communities. In our new model, communities may overlap, and they have their own internal structure described by arbitrary finite community graphs. Our model turns out to be tractable. We analyze the overlapping structure of the communities, show local weak convergence (including convergence of subgraph counts), and derive the asymptotic degree distribution and the local clustering coefficient.