Single-class closed queueing networks, consisting of infinite-server and single-server queues with exponential service times and probabilistic routing, admit product-from solutions. Such solutions, ...although seemingly tractable, are difficult to characterize explicitly for practically relevant problems due to the exponential combinatorial complexity of its normalization constant (partition function). In “A Probabilistic Approach to Growth Networks,” Jelenković, Kondev, Mohapatra, and Momčilović develop a novel methodology, based on a probabilistic representation of product-form solutions and large-deviations concentration inequalities, which identifies distinct operating regimes and yields explicit expressions for the marginal distributions of queue lengths. From a methodological perspective, a fundamental feature of the proposed approach is that it provides exact results for order-one probabilities, even though the analysis involves large-deviations rate functions, which characterize only vanishing probabilities on a logarithmic scale.
Widely used closed product-form networks have emerged recently as a primary model of stochastic growth of subcellular structures, for example, cellular filaments. The baseline bio-molecular model is equivalent to a single-class closed queueing network, consisting of single-server and infinite-server queues. Although this model admits a seemingly tractable product-form solution, explicit analytical characterization of its partition function is difficult due to the large-scale nature of bio-molecular networks. To this end, we develop a novel methodology, based on a probabilistic representation of product-form solutions and large-deviations concentration inequalities, which identifies distinct operating regimes and yields explicit expressions for the marginal distributions of queue lengths. The parameters of the derived distributions can be computed from equations involving large-deviations rate functions, often admitting closed-form algebraic expressions. From a methodological perspective, a fundamental feature of our approach is that it provides exact results for order-one probabilities, even though our analysis involves large-deviations rate functions, which characterize only vanishing probabilities on a logarithmic scale.
Supplemental Material:
The e-companion is available at
https://doi.org/10.1287.opre.2021.2195
.
How the size of micrometer-scale cellular structures such as the mitotic spindle, cytoskeletal filaments, the nucleus, the nucleolus, and other non-membrane bound organelles is controlled despite a ...constant turnover of their constituent parts is a central problem in biology. Experiments have implicated the limiting-pool mechanism: structures grow by stochastic addition of molecular subunits from a finite pool until the rates of subunit addition and removal are balanced, producing a structure of well-defined size. Here, we consider these dynamics when multiple filamentous structures are assembled stochastically from a shared pool of subunits. Using analytical calculations and computer simulations, we show that robust size control can be achieved only when a single filament is assembled. When multiple filaments compete for monomers, filament lengths exhibit large fluctuations. These results extend to three-dimensional structures and reveal the physical limitations of the limiting-pool mechanism of size control when multiple organelles are assembled from a shared pool of subunits.
Display omitted
•The limiting-pool mechanism of size control successfully assembles one structure of a well defined size•Multiple structures assembled from a common limiting pool exhibit large size fluctuations•Assembly of multiple structures exhibits three characteristic timescales
While the limiting-pool mechanism can control the size of an individual sub-cellular structure, it fails to control the sizes of multiple structures that are all competing for the same pool of subunits.
Consider a generic data unit of random size L that needs to be transmitted over a channel of unit capacity. The channel availability dynamic is modeled as an independent and identically distributed ...sequence {A, A
i
}
i≥1 that is independent of L. During each period of time that the channel becomes available, say A
i
, we attempt to transmit the data unit. If L <A
i
, the transmission is considered successful; otherwise, we wait for the next available period A
i+1 and attempt to retransmit the data from the beginning. We investigate the asymptotic properties of the number of retransmissions N and the total transmission time T until the data is successfully transmitted. In the context of studying the completion times in systems with failures where jobs restart from the beginning, it was first recognized by Fiorini, Sheahan and Lipsky (2005) and Sheahan, Lipsky, Fiorini and Asmussen (2006) that this model results in power-law and, in general, heavy-tailed delays. The main objective of this paper is to uncover the detailed structure of this class of heavy-tailed distributions induced by retransmissions. More precisely, we study how the functional relationship ℙL>x-1 ≈ Φ (ℙA>x-1) impacts the distributions of N and T; the approximation ‘≈’ will be appropriately defined in the paper based on the context. Depending on the growth rate of Φ(·), we discover several criticality points that separate classes of different functional behaviors of the distribution of N. For example, we show that if log(Φ(n)) is slowly varying then log(1/ℙN>n) is essentially slowly varying as well. Interestingly, if log(Φ(n)) grows slower than e√(logn) then we have the asymptotic equivalence log(ℙN>n) ≈ - log(Φ(n)). However, if log(Φ(n)) grows faster than e√(logn), this asymptotic equivalence does not hold and admits a different functional form. Similarly, different types of distributional behavior are shown for moderately heavy tails (Weibull distributions) where log(ℙN>n) ≈ -(log Φ(n))1/(β+1), assuming that log Φ(n) ≈ nβ, as well as the nearly exponential ones of the form log(ℙN>n) ≈ -n/(log n)1/γ, γ>0, when Φ(·) grows faster than two exponential scales log log (Φ(n)) ≈ n
γ.
Retransmission-based failure recovery represents a primary approach in existing communication networks that guarantees data delivery in the presence of channel failures. Recent work has shown that, ...when data sizes have infinite support, retransmissions can cause long (-tailed) delays even if all traffic and network characteristics are light-tailed. In this paper we investigate the practically important case of bounded data units 0 ≤ L
b
≤ b under the condition that the hazard functions of the distributions of data sizes and channel statistics are proportional. To this end, we provide an explicit and uniform characterization of the entire body of the retransmission distribution ℙN
b
> n in both n and b. Our main discovery is that this distribution can be represented as the product of a power law and gamma distribution. This rigorous approximation clearly demonstrates the coupling of a power law distribution, dominating the main body, and the gamma distribution, determining the exponential tail. Our results are validated via simulation experiments and can be useful for designing retransmission-based systems with the required performance characteristics. From a broader perspective, this study applies to any other system, e.g. computing, where restart mechanisms are employed after a job processing failure.
We extend Goldie's (1991) implicit renewal theorem to enable the analysis of recursions on weighted branching trees. We illustrate the developed method by deriving the power-tail asymptotics of the ...distributions of the solutions R to and similar recursions, where (Q, N, C
1, C
2,…) is a nonnegative random vector with N ∈ {0, 1, 2, 3,…} ∪ {∞}, and are independent and identically distributed copies of R, independent of (Q, N, C
1, C
2,…); here ‘∨’ denotes the maximum operator.
We consider possibly nonlinear distributional fixed-point equations on weighted branching trees, which include the well-known linear branching recursion. In Jelenković and Olvera-Cravioto (2012), an ...implicit renewal theorem was developed that enables the characterization of the power-tail asymptotics of the solutions to many equations that fall into this category. In this paper we complement the analysis in our 2012 paper to provide the corresponding rate of convergence.
Retransmissions represent a primary failure recovery mechanism on all layers of communication network architecture. Similarly, fair sharing, for example, processor sharing (PS), is a widely accepted ...approach to resource allocation among multiple users. Recent work has shown that retransmissions in failure-prone, for example, wireless ad hoc, networks can cause heavy tails and long delays. In this paper, we discover a new phenomenon showing that PS-based scheduling induces complete instability with zero throughput in the presence of retransmissions, regardless of how low the traffic load may be. This phenomenon occurs even when the job sizes are bounded/fragmented, for example, deterministic. Our analytical results are further validated via simulation experiments. Moreover, our work demonstrates that scheduling one job at a time, such as first-come-first-serve, achieves a larger stability region and should be preferred in these systems.
The persistent-access-caching algorithm Jelenkovic, Predrag R; Radovanovic, Ana
Random structures & algorithms,
September 2008, Volume:
33, Issue:
2
Journal Article
Power law distributions have been repeatedly observed in a wide variety of socioeconomic, biological, and technological areas. In many of the observations, e.g., city populations and sizes of living ...organisms, the objects of interest evolve because of the replication of their many independent components, e.g., births and deaths of individuals and replications of cells. Furthermore, the rates of replications are often controlled by exogenous parameters causing periods of expansion and contraction, e.g., baby booms and busts, economic booms and recessions, etc. In addition, the sizes of these objects often have reflective lower boundaries, e.g., cities do not fall below a certain size, low-income individuals are subsidized by the government, companies are protected by bankruptcy laws, etc.
Hence, it is natural to propose reflected modulated branching processes as generic models for many of the preceding observations. Indeed, our main results show that the proposed mathematical models result in power law distributions under quite general polynomial Gärtner-Ellis conditions, the generality of which could explain the ubiquitous nature of power law distributions. In addition, on a logarithmic scale, we establish an asymptotic equivalence between the reflected branching processes and the corresponding multiplicative ones. The latter, as recognized by Goldie Goldie, C. M. 1991. Implicit renewal theory and tails of solutions of random equations.
Ann. Appl. Probab.
1
(1) 126-166, is known to be dual to queueing/additive processes. We emphasize this duality further in the generality of stationary and ergodic processes.
PDF
