A shared ledger is a record of transactions that can be updated by any member of a group of users. The notion of independent and consistent record-keeping in a shared ledger is important for blockchain and more generally for distributed ledger technologies. In this paper we analyze a stochastic model for the shared ledger known as the tangle, which was devised as the basis for the IOTA cryptocurrency. The model is a random directed acyclic graph, and its growth is described by a non-Markovian stochastic process. We first prove ergodicity of the stochastic process, and then derive a delay differential equation for the fluid model which describes the tangle at high arrival rate. We prove convergence in probability of the tangle process to the fluid model, and also prove global stability of the fluid model. The convergence proof relies on martingale techniques.

A parallel server system with n identical servers is considered. The service time distribution has a finite mean 1 / μ, but otherwise is arbitrary. Arriving customers are routed to one of the servers immediately upon arrival. The join-idle-queue routeing algorithm is studied, under which an arriving customer is sent to an idle server, if such is available, and to a randomly uniformly chosen server, otherwise. We consider the asymptotic regime where n → ∞ and the customer input flow rate is λn. Under the condition λ / μ < ½, we prove that, as n → ∞, the sequence of (appropriately scaled) stationary distributions concentrates at the natural equilibrium point, with the fraction of occupied servers being constant at λ / μ. In particular, this implies that the steady-state probability of an arriving customer waiting for service vanishes.

A service system with multiple types of customers, arriving according to Poisson processes, is considered. The system is heterogeneous in that the servers can also be of multiple types. Each customer has an independent, exponentially distributed service time, with the mean determined by its type. Multiple customers (possibly of different types) can be placed for service into one server, subject to `packing' constraints, which depend on the server type. Service times of different customers are independent, even if served simultaneously by the same server. The large-scale asymptotic regime is considered such that the customer arrival rates grow to ∞. We consider two variants of the model. For the infinite-server model, we prove asymptotic optimality of the greedy random (GRAND) algorithm in the sense of minimizing the weighted (by type) number of occupied servers in steady state. (This version of GRAND generalizes that introduced by Stolyar and Zhong (2015) for homogeneous systems, with all servers of the same type.) We then introduce a natural extension of the GRAND algorithm for finite-server systems with blocking. Assuming subcritical system load, we prove existence, uniqueness, and local stability of the large-scale system equilibrium point such that no blocking occurs. This result strongly suggests a conjecture that the steady-state blocking probability under the algorithm vanishes in the large-scale limit.

We develop diffusion approximations for parallel-queueing systems with the randomized longest-queue-first scheduling (LQF) algorithm by establishing new mean-field limit theorems as the number of buffers n → ∞. We achieve this by allowing the number of sampled buffers d = d(n) to depend on the number of buffers n, which yields an asymptotic 'decoupling' of the queue length processes. We show through simulation experiments that the resulting approximation is accurate even for moderate values of n and d(n). To the best of the authors' knowledge, this is the first derivation of diffusion approximations for a queueing system in the large-buffer mean-field regime. Another noteworthy feature of our scaling idea is that the randomized LQF algorithm emulates the LQF algorithm, yet is computationally more attractive. The analysis of the system performance as a function of d(n) is facilitated by the multi-scale nature in our limit theorems: the various processes we study have different space scalings. This allows us to show the trade-off between performance and complexity of the randomized LQF scheduling algorithm.

A large-scale service system with multiple customer classes and multiple server pools is considered, with the mean service time depending both on the customer class and server pool. The allowed activities (routeing choices) form a tree (in the graph with vertices being both customer classes and server pools). We study the behavior of the system under a leaf activity priority (LAP) policy, introduced by Stolyar and Yudovina (2012). An asymptotic regime is considered, where the arrival rate of customers and number of servers in each pool tend to ∞ in proportion to a scaling parameter r, while the overall system load remains strictly subcritical. We prove tightness of diffusion-scaled (centered at the equilibrium point and scaled down by r−1/2) invariant distributions. As a consequence, we obtain a limit interchange result: the limit of diffusion-scaled invariant distributions is equal to the invariant distribution of the limiting diffusion process.

We study the conditions for positive recurrence and transience of multi-dimensional birth-and-death processes describing the evolution of a large class of stochastic systems, a typical example being the randomly varying number of flow-level transfers in a telecommunication wire-line or wireless network. First, using an associated deterministic dynamical system, we provide a generic method to construct a Lyapunov function when the drift is a smooth function on ℝN. This approach gives an elementary and direct proof of ergodicity. We also provide instability conditions. Our main contribution consists of showing how discontinuous drifts change the nature of the stability conditions and of providing generic sufficient stability conditions having a simple geometric interpretation. These conditions turn out to be necessary (outside a negligible set of the parameter space) for piecewise constant drifts in dimension two.

We study a multiclass Markovian queueing network with switchover across a set of many-server stations. New arrivals to each station follow a nonstationary Poisson process. Each job waiting in queue may, after some exponentially distributed patience time, switch over to another station or leave the network following a probabilistic and state-dependent mechanism. We analyze the performance of such networks under the many-server heavy-traffic limiting regimes, including the critically loaded quality-and-efficiency-driven (QED) regime, and the overloaded efficiency-driven (ED) regime. We also study the limits corresponding to mixing the underloaded quality-driven (QD) regime with the QED and ED regimes. We establish fluid and diffusion limits of the queue-length processes in all regimes. The fluid limits are characterized by ordinary differential equations. The diffusion limits are characterized by stochastic differential equations, with a piecewise-linear drift term and a constant (QED) or time-varying (ED) covariance matrix. We investigate the load balancing effect of switchover in the mixed regimes, demonstrating the migration of workload from overloaded stations to underloaded stations and quantifying the load balancing impact of switchover probabilities.

We construct an efficient numerical scheme for the quantum Fokker-Planck- Landau (FPL) equation that works uniformly from kinetic to fluid regimes. Such a scheme inevitably needs an implicit discretization of the nonlinear collision operator, which is difficult to invert. Inspired by work [9] we seek a linear operator to penalize the quantum FPL collision term QqFPL in order to remove the stiffness induced by the small Knudsen number. However, there is no suitable simple quantum operator serving the purpose and for this kind of operators one has to solve the complicated quantum Maxwellians (Bose-Einstein or Fermi-Dirac distribution). In this paper, we propose to penalize QqFPL by the "classical" linear Fokker-Planck operator. It is based on the observation that the classical Maxwellian, with the temperature replaced by the internal energy, has the same first five moments as the quantum Maxwellian. Numerical results for Bose and Fermi gases are presented to illustrate the efficiency of the scheme in both fluid and kinetic regimes.

In this paper we establish limit theorems for a class of stochastic hybrid systems (continuous deterministic dynamics coupled with jump Markov processes) in the fluid limit (small jumps at high frequency), thus extending known results for jump Markov processes. We prove a functional law of large numbers with exponential convergence speed, derive a diffusion approximation, and establish a functional central limit theorem. We apply these results to neuron models with stochastic ion channels, as the number of channels goes to infinity, estimating the convergence to the deterministic model. In terms of neural coding, we apply our central limit theorems to numerically estimate the impact of channel noise both on frequency and spike timing coding.

We introduce a formal limit, which we refer to as a fluid limit, of scaled stochastic models for a cache managed with the least-recently-used algorithm when requests are issued according to general stochastic point processes. We define our fluid limit as a superposition of dependent replications of the original system with smaller item sizes when the number of replications approaches ∞. We derive the average probability that a requested item is not in a cache (average miss probability) in the fluid limit. We show that, when requests follow inhomogeneous Poisson processes, the average miss probability in the fluid limit closely approximates that in the original system. Also, we compare the asymptotic characteristics, as the cache size approaches ∞, of the average miss probability in the fluid limit to those in the original system.

In a general model (AIMD) of transmission control protocol (TCP)used in internet traffic congestion management, the time dependentdata flow vector x(t) > 0 undergoes a biased random walk ontwo distinct scales. The amount of data of each component x i (t)goes up to x i (t)+a with probability 1-ζ i (x) ona unit scale or down to γ x i (t), 0 < γ < 1 withprobability ζ i (x) on a logarithmic scale, where ζ i depends on the joint state of the system x. Weinvestigate the long time behavior, mean field limit, and the oneparticle case. According to c = lim inf|x|→∞ |x|ζ i (x), the process drifts to ∞ in thesubcritical c < c + (n, γ) case and has an invariantprobability measure in the supercritical case c > c + (n, γ).Additionally, a scaling limit is proved when ζ i (x)and a are of order N –1 and t → N t, in the form of acontinuum model with jump rate α(x).

The classical models in risk theory consider a single type of claim. In the insurance business, however, several business lines with separate claim arrival processes appear naturally, and the individual claim processes may not be independent. We introduce a new class of models for such situations, where the underlying counting process is a multivariate continuous-time Markov chain of pure-birth type and the dependency of the components arises from the fact that the birth rate for a specific claim type may depend on the number of claims in the other component processes. Under certain conditions, we obtain a fluid limit, i.e. a functional law of large numbers for these processes. We also investigate the consequences of such results for questions of interest in insurance applications. Several specific subclasses of the general model are discussed in detail and the Cramér asymptotics of the ruin probabilities are derived in particular cases.

We consider the stability of the longest-queue-first scheduling policy (LQF), a natural and low-complexity scheduling policy, for a generalized switch model. Unlike that of common scheduling policies, the stability of LQF depends on the variance of the arrival processes in addition to their average intensities. We identify new sufficient conditions for LQF to be throughput optimal for independent, identically distributed arrival processes. Deterministic fluid analogs, proved to be powerful in the analysis of stability in queueing networks, do not adequately characterize the stability of LQF. We combine properties of diffusion-scaled sample path functionals and local fluid limits into a sharper characterization of stability.

We use a sample-path technique to derive asymptotics of generalized Jackson queueing networks in the fluid scale; that is, when space and time are scaled by the same factor n. The analysis only presupposes the existence of long-run averages and is based on some monotonicity and concavity arguments for the fluid processes. The results provide a functional strong law of large numbers for stochastic Jackson queueing networks, since they apply to their sample paths with probability 1. The fluid processes are shown to be piecewise linear and an explicit formulation of the different drifts is computed. A few applications of this fluid limit are given. In particular, a new computation of the constant that appears in the stability condition for such networks is given. In a certain context of a rare event, the fluid limit of the network is also derived explicitly.

We give the exact asymptotics of the tail of the stationary maximal dater in generalized Jackson networks with subexponential service times. This maximal dater, which is an analogue of the workload in an isolated queue, gives the time taken to clear all customers present at some time t when stopping all arrivals that take place later than t. We use the property that a large deviation of the maximal dater is caused by a single large service time at a single station at some time in the distant past of t, in conjunction with fluid limits of generalized Jackson networks, to derive the relevant asymptotics in closed form.