Approximate solutions for M/G/1 fork/join synchronization

Approximation techniques are developed to evaluate the performance of symmetric fork-join synchronization delays for K M/G/1 queues. For a server utilization ρ, the mean response time for fork-join requests is expressed as the sum of the mean response time at one of the queues and the mean synchronization delay as follows: R_K^F1/(ρ)=R₁(ρ)+F_Kα_K(ρ)σ₁(ρ), where F_K is obtained from the previous equation at ρ=0, R₁(ρ) and σ₁(ρ) are the mean and the standard deviation of response time at any one of the queues, respectively, and α_K(ρ) is a low-degree service-time distribution dependent polynomial in ρ, whose coefficients are determined from simulation results. We also use simulation results to show that when fork-join requests share the servers with local requests, a good approximation (and an upper bound) to the fork-join response time is obtained by treating the components of fork-join response time as independent, i.e., the mean fork-join response time can be approximated by the expected value of the maximum of the response times at the K queues.