Diffusion approximations for load balancing mechanisms in cloud storage systems
From MaRDI portal
Publication:5203891
diffusion approximationpropagation of chaosmean-field approximationcylindrical Brownian motionsupermarket modelstochastic networkpower-of-\(d\)cloud storage systemMDS coding
Applications of continuous-time Markov processes on discrete state spaces (60J28) Applications of Brownian motions and diffusion theory (population genetics, absorption problems, etc.) (60J70) Central limit and other weak theorems (60F05) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Queues and service in operations research (90B22) Queueing theory (aspects of probability theory) (60K25) Applications of stochastic analysis (to PDEs, etc.) (60H30) Limit theorems for vector-valued random variables (infinite-dimensional case) (60B12)
Abstract: 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 routing scheme for a network of servers storing a set of files using the Maximum Distance Separable (MDS) code (cf. Li, Ramamoorthy, and Srikant (2016)). Specifically, each file is stored in equally sized pieces across servers such that any pieces can reconstruct the original file. When a request for a file is received, the dispatcher routes the job into the -shortest queues among the 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. ). For the central limit theorem, the limit process take values in , the space of square summable sequences. Due to the large size of such systems, a direct analysis of the -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- routing scheme, also known as the supermarket model, is a special case of the model considered here.
Recommendations
- A \(q\)-analogue of a result of Carlitz, Scoville and Vaughan via the homology of posets
- Systems with large flexible server pools: instability of ``natural load balancing
- Universality of load balancing schemes on the diffusion scale
- Asymptotic optimality of power-of-\(d\) load balancing in large-scale systems
- The hydrodynamic limit of a randomized load balancing network
Cites work
- scientific article; zbMATH DE number 1631027 (Why is no real title available?)
- scientific article; zbMATH DE number 4211245 (Why is no real title available?)
- scientific article; zbMATH DE number 3951715 (Why is no real title available?)
- scientific article; zbMATH DE number 4034749 (Why is no real title available?)
- scientific article; zbMATH DE number 4076265 (Why is no real title available?)
- scientific article; zbMATH DE number 3719745 (Why is no real title available?)
- scientific article; zbMATH DE number 3729228 (Why is no real title available?)
- scientific article; zbMATH DE number 43057 (Why is no real title available?)
- A functional central limit theorem for the \(M/GI/\infty \) queue
- An asymptotic optimality result for the multiclass queue with finite buffers in heavy traffic
- Asymptotic independence of queues under randomized load balancing
- Asymptotic optimality of maximum pressure policies in stochastic processing networks
- Central limit theorems and diffusion approximations for multiscale Markov chain models
- Chaoticity on path space for a queueing network with selection of the shortest queue among several
- Controlled stochastic networks in heavy traffic: convergence of value functions
- Diffusion approximation of nuclear space-valued stochastic differential equations driven by Poisson random measures
- Diffusion approximations for controlled weakly interacting large finite state systems with simultaneous jumps
- Distribution-valued heavy-traffic limits for the \(\mathrm{G}/\mathrm{GI}/\infty\) queue
- Dynamic scheduling of a system with two parallel servers in heavy traffic with resource pooling: Asymptotic optimality of a threshold policy
- Ergodic rate control problem for single class queueing networks
- Ergodicity of an SPDE associated with a many-server queue
- Error control coding. Fundamentals and applications
- Join the shortest queue with many servers. The heavy-traffic asymptotics
- Limit theorems for sequences of jump Markov processes approximating ordinary differential processes
- Pull-based load distribution in large-scale heterogeneous service systems
- Queueing system with selection of the shortest of two queues: An asymptotic approach
- Representations of Markov processes as multiparameter time changes
- SPDE limits of many-server queues
- Semimartingales: A course on stochastic processes
- Stochastic Equations in Infinite Dimensions
- Stochastic analysis of biochemical systems
- Stochastic networks with multiple stable points
- Stochastic-Process Limits
- Universality of load balancing schemes on the diffusion scale
- Weak convergence of sequences of semimartingales with applications to multitype branching processes
Cited in
(6)- Cloud data storage: a queueing model with thresholds
- Scalable Load Balancing in Networked Systems: A Survey of Recent Advances
- A functional central limit theorem for the Becker-Döring model
- Many-server asymptotics for join-the-shortest-queue: large deviations and rare events
- Beyond the MDS Bound in Distributed Cloud Storage
- Near equilibrium fluctuations for supermarket models with growing choices
This page was built for publication: Diffusion approximations for load balancing mechanisms in cloud storage systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5203891)
