# A Study Comparing Waiting Times in Global and Local Queuing Systems with Heterogeneous Workers
## 2 Related Work
### Local Queues with Homogenous (LH) and Heterogeneous (LHT) Workers  
Parallel queue systems were developed for separated servers where a centralized management system could not handle all tasks locally. A centrally located dispatcher assigns tasks to several queues using different routing policies. The JSQ is an optimal routing policy that routes tasks to the server with the shortest queue. JSQ minimizes the average delay of jobs and the number of customers in the system consisting of identical servers [15] using Markov Decision Processes (MDP), assuming Poisson arrivals and exponential service times. This optimality result was extended to general stochastic arrival processes [16; 17]. [PERSON] et al. [18] provided a formal model and analysis of JSQ when used in the routing policy for server farms with the same processing rate and general task-size distributions. [PERSON] et al. [19] found that JSQ achieves a better response time than the method that considers a worker's average queue length (AQL) with homogenous and heterogeneous workers (LH, LHT).  
JSQ is good for identical servers with independent service times but not for heterogeneous systems with different processing rates. The SED routing policy is used in the latter case, which routes customers to the server with the shortest expected response time. However, SED requires knowledge of the entire job size distribution to estimate the remaining service time. It is difficult to analyze exact systems when service rates are not equal, and finding optimal delay schemes for heterogeneous systems remains an open problem due to infinite state spaces [20]. In this work, we simulate WJSQL, which learns the processing rates online and assigns them to the fastest worker with the shortest expected delay. [PERSON] & [PERSON] [21] introduced SA-JSQ (speed-aware JSQ), which is a variant of the JSQ scheme with a large number of processing rate categories. In SA-JSQ, each incoming task is assigned to a server with the highest speed among those with the minimum queue length. Ties among servers are broken randomly and uniformly. They proved that SA-JSQ is optimal in fluid limits when the system size is infinite. However, numerical simulations showed that assigning tasks based on SED performed better than SA-JSQ for small system sizes. [PERSON] et al. [22] investigate dynamic routing policies in a local queue system (LHT) with two servers, focusing on scenarios where only a subset of jobs was observable and controllable while others were assigned randomly, showing that heuristic routing strategies can significantly reduce the average response time, closely approaching the performance of the optimal fully observable system under heavy loads, as represented by the SED policy. Their problem is relevant because it shows the strength of a good routine policy.  
Our study assumes a centralized dispatcher that assigns incoming tasks. As cloud infrastructure grows and server heterogeneity increases, traditional single-dispatcher load-balancing policies like JSQ become less feasible. There are low-communication policies with few dispatchers, such as JSQ(d), where each dispatcher picks d queues randomly and allocates the task to the queue with the shortest queue, and the Join-Idle-Queue (JIQ). Both architectures are unstable or perform poorly when the number is very large, and their speed is heterogeneous. [PERSON] et al. [23] introduced the Local Shortest Queue (LSQ) family of load-balancing algorithms with multiple dispatchers. Each dispatcher maintains its local view of the server queue lengths and uses JSQ on its local view, which is updated infrequently and possibly outdated. They showed how their LSQ policies often outperformed even JSQ due to the low communication and how the slow server problem was solved using advanced pull-based communication. [PERSON] et al. [24] formulated \"power-of-d\" versions of JIQ and JSQ policies, improving the mean response time and queue length distribution analyses and outperforming other heterogeneity-aware policies, such as SED.