Diffusion approximations for load balancing mechanisms in cloud storage systems

DOI10.1017/APR.2019.3zbMATH Open1427.60187arXiv1706.09914OpenAlexW2963022723MaRDI QIDQ5203891FDOQ5203891

Authors: Eric M. Friedlander, Amarjit Budhiraja 

Publication date: 9 December 2019

Published in: Advances in Applied Probability (Search for Journal in Brave)

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 $n$ 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 $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. $noinfty$). For the central limit theorem, the limit process take values in $mathbf{ell}_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$ routing scheme, also known as the supermarket model, is a special case of the model considered here.

Full work available at URL: https://arxiv.org/abs/1706.09914

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

zbMATH Keywords

diffusion approximationpropagation of chaosmean-field approximationcylindrical Brownian motionsupermarket modelstochastic networkpower-of-\(d\)cloud storage systemMDS coding

Mathematics Subject Classification ID

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Queueing system with selection of the shortest of two queues: An asymptotic approach
• Stochastic networks with multiple stable points
• Stochastic-Process Limits
• Title not available (Why is that?)
• Title not available (Why is that?)
• SPDE limits of many-server queues
• Title not available (Why is that?)
• Title not available (Why is that?)
• Stochastic Equations in Infinite Dimensions
• Limit theorems for sequences of jump Markov processes approximating ordinary differential processes
• Semimartingales: A course on stochastic processes
• Error control coding. Fundamentals and applications
• Chaoticity on path space for a queueing network with selection of the shortest queue among several
• Asymptotic independence of queues under randomized load balancing
• Title not available (Why is that?)
• Stochastic analysis of biochemical systems
• Weak convergence of sequences of semimartingales with applications to multitype branching processes
• Diffusion approximation of nuclear space-valued stochastic differential equations driven by Poisson random measures
• Representations of Markov processes as multiparameter time changes
• 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
• Title not available (Why is that?)
• Asymptotic optimality of maximum pressure policies in stochastic processing networks
• A functional central limit theorem for the \(M/GI/\infty \) queue
• Controlled stochastic networks in heavy traffic: convergence of value functions
• Central limit theorems and diffusion approximations for multiscale Markov chain models
• Distribution-valued heavy-traffic limits for the \(\mathrm{G}/\mathrm{GI}/\infty\) queue
• Diffusion approximations for controlled weakly interacting large finite state systems with simultaneous jumps
• Join the shortest queue with many servers. The heavy-traffic asymptotics
• Pull-based load distribution in large-scale heterogeneous service systems
• Universality of load balancing schemes on the diffusion scale
• Ergodicity of an SPDE associated with a many-server queue
• An asymptotic optimality result for the multiclass queue with finite buffers in heavy traffic

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)