2016/12/16 by Wasiur R. KhudaBukhsh, Amr Rizk, KhudaBukhsh, Wasiur R. +5
Business, Management and Accounting · Computer Science · #60K25 #90B22 #Advanced Queuing Theory Analysis #Cloud Computing and Resource Management #D.2.8 #D.4.8 #Distributed systems and fault tolerance #FOS: Computer and information sciences #G.3 #Performance (cs.PF)
paper · pdf · doi:10.48550/arxiv.1612.05486
openalex publication_date 2016/12/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Fork-Join (FJ) queueing models capture the dynamics of system parallelization\nunder synchronization constraints, for example, for applications such as\nMapReduce, multipath transmission and RAID systems. Arriving jobs are first\nsplit into tasks and mapped to servers for execution, such that a job can only\nleave the system when all of its tasks are executed.\n In this paper, we provide computable stochastic bounds for the waiting and\nresponse time distributions for heterogeneous FJ systems under general\nparallelization benefit. Our main contribution is a generalized mathematical\nframework for probabilistic server scheduling strategies that are essentially\ncharacterized by a probability distribution over the number of utilized\nservers, and the optimization thereof. We highlight the trade-off between the\nscaling benefit due to parallelization and the FJ inherent synchronization\npenalty. Further, we provide optimal scheduling strategies for arbitrary\nscaling regimes that map to different levels of parallelization benefit. One\nnotable insight obtained from our results is that different applications with\nvarying parallelization benefits result in different optimal strategies.\nFinally, we complement our analytical results by applying them to various\napplications showing the optimality of the proposed scheduling strategies.\n