Distributed Load Balancing in the Face of Reappearance Dependencies
Kunal Agrawal, William Kuszmaul, Zhe Wang, Jinhao Zhao · 2024
We consider the problem of load-balancing on distributed databases. We assume that data is divided into chunks and each chunk can be replicated on a constant number d of servers. When a request arrives, it is routed to one of the servers that contains the relevant chunk. Each server may store outstanding requests in a bounded queue and requests may be rejected if the queue is full. The goal is to design strategies for data distribution and request routing that minimize both the rejection rate and the average request latency.