Gaussian Limits for a Fork-Join Network with Nonexchangeable Synchronization in Heavy Traffic

• 成果类型: Article
• 署名作者: Lu, Hongyuan; Pang, Guodong
• 署名单位: Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2015.0740
• 发表日期: 2016
• 页码: 560-595
• 关键词: infinite-server queues; STOCHASTIC-PROCESSES; service; MODEL; times; approximation; CONVERGENCE; mapreduce; max

摘要

We study a fork-join network of stations with multiple servers and nonexchangeable synchronization in heavy traffic under the first-come-first-served (FCFS) discipline. Tasks are only synchronized if all the tasks associated with the same job are completed. Service times of parallel tasks of each job can be correlated. We jointly consider the number of tasks in each waiting buffer for synchronization with the number of tasks in each parallel service station and the number of synchronized jobs. We develop a new approach to show a functional central limit theorem for these processes in the quality-driven regime, under general assumptions on arrival and service processes. Specifically, we represent these processes as functionals of a sequential empirical process driven by the sequence of service vectors for each job's parallel tasks. All of the limiting processes are functionals of two independent processes, i.e., the limiting arrival process and a generalized Kiefer process driven by the service vector of each job. We characterize the transient and stationary distributions of the limiting processes.