TITLE: Large-Scale Fork-Join Networks with Non-Exchangeable Synchronization

SPEAKER: Dr. Guodong (Gordon) Pang

ABSTRACT:

Fork-join networks consist of a set of service stations that serve job requests simultaneously and sequentially according to pre-designated deterministic precedence constraints. We consider non-exchangeable synchronization (NES), that is, each job can be synchronized only after all of its tasks are completed. Such networks have many applications in manufacturing, telecommunications, patient flow analysis in healthcare and parallel computing. When each station has multiple servers and operates under the FCFS service discipline, the main mathematical challenge to study fork-join networks with NES is the resequencing of tasks’ arrival orders after service completion. We develop a new framework to solve the resequencing problem in the many-server heavy-traffic regimes where the arrival rates and the numbers of servers in each station get large appropriately.

In this talk, we focus on a fundamental fork-join network model with a single class of jobs and NES. Service times of the parallel tasks of each job can be correlated. Upon service completion, each parallel task will join a buffer associated with its service station and wait for synchronization. The goal is to understand the waiting buffer dynamics for synchronization as well as the service dynamics. We show functional central limit theorems for the number of tasks in each waiting buffer for synchronization jointly with the number of tasks in each parallel service station and the number of synchronized jobs, in the many-server asymptotic regimes. All the limiting processes are functionals of two independent processes: the arrival limit process and the generalized multiparameter Kiefer process driven by the service vectors for the parallel tasks of each job. We characterize the transient and stationary distributions of these limiting processes. We also discuss generalizations of the framework to study more complex fork-join networks with NES constraints.