Large-Scale Fork-Join Networks with Synchronization Constraints

Project: Research project

Project Details


Fork-join networks with synchronization constraints can be widely used to model patient flows in hospitals (e.g., emergency department treatment and patient discharge process) and data centers (e.g., parallelized Web search), among many other applications. In such networks, jobs are forked into parallel tasks to be served at service stations with parallel servers, and tasks are then joined for job completion or further processing provided that certain synchronization constraints are satisfied, for example, only completed tasks from the same job can be joined (non-exchangeable). However, very little is known about the performance, reliability and control of these networks, and existing methods in stochastic networks cannot be applied to study them. This award supports development of new methodology to better understand important performance measures (e.g., congestions and response times) of fork-join networks with non-exchangeable synchronization constraints, to design reliable fork-join networks with synchronization constraints operating in dynamic random environments, and to manage them in a cost-effective way. The research findings will have a broad impact on the society by improving the efficiency and quality of services in healthcare and data centers. The research will result in young STEM-trained graduates and underrepresented groups with new mathematical tools that help understand and improve the delivered services.

The main mathematical challenge to study fork-join networks of multi-server service stations with non-exchangeable synchronization lies in the resequencing of arrival orders after service completion at each station due to randomness of service times. Unlike classical queueing networks, delay for synchronization is a key performance measure affecting system congestion, while resequencing is its determining factor. No analytical methods and results are known for such networks. This research will develop a new framework to solve the resequencing problem in fork-join networks, and thus, result in effective approximations for the synchronization dynamics as well as the service dynamics. The approach will use multi-parameter stochastic processes to study the service, queueing and synchronization dynamics, including sequential empirical processes driven by random vectors and their limits, and two-parameter processes tracking elapsed and residual service and wait times. Coordination and information sharing among parallel tasks of each job during their services will be exploited to develop optimal control policies for fork-join networks with synchronization constraints in order to minimize delay for synchronization as well as delay for service. Preventive strategies will be provided on the design and management of reliable fork-join networks with synchronization constraints operating in dynamic random environments.

Effective start/end date8/1/157/31/18


  • National Science Foundation: $250,000.00


Explore the research topics touched on by this project. These labels are generated based on the underlying awards/grants. Together they form a unique fingerprint.