Stationary Waiting Time in Parallel Queues with Synchronization

• 成果类型: Article
• 署名作者: Olvera-Cravioto, Mariana; Ruiz-Lacedelli, Octavio
• 署名单位: University of North Carolina; University of North Carolina Chapel Hill; University of North Carolina School of Medicine; Columbia University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2019.1045
• 发表日期: 2021
• 页码: 1-27
• 关键词: probabilistic models; queuing system; fixed-points; service; STABILITY; equation

摘要

Motivated by database locking problems in today's massive computing systems, we analyze a queueing network with many servers in parallel (files) to which jobs (writing access requests) arrive according to a Poisson process. Each job requests simultaneous access to a random number of files in the database and will lock them for a random period of time. Alternatively, one can think of a queueing system where jobs are split into several fragments that are then randomly routed to specific servers in the network to be served in a synchronized fashion. We assume that the system operates on a first-come, first-served basis. The synchronization and service discipline create blocking and idleness among the servers, which leads to a strict stability condition compared with other distributed queueing models. We analyze the stationary waiting time distribution of jobs under a many-server limit and provide exact tail asymptotics. These asymptotics generalize the celebrated Cramer-Lundberg approximation for the single-server queue.