Distributed Load Balancing in the Face of Reappearance Dependencies

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. What makes this problem technically difficult is reappearance dependencies: if a chunk x is accessed at multiple different time steps, then the set of d servers that it can be routed to is the same each time it is accessed. This is a substantial departure from classical balls-and-bins settings where each ball arrival introduces fresh randomness into the system. We show that, with new algorithmic and analytical approaches, it is possible to overcome reappearance dependencies and construct algorithms with optimal rejection rate, latency, and queue size.