Dynamic Task Allocation in Asynchronous Shared Memory
Authors: Dan Alistarh (MIT), James Aspnes (Yale University), Michael A. Bender (Stony Brook University), Rati Gelashvili (MIT), and Seth Gilbert (NUS)
Task allocation is a classic distributed problem in which a set of p potentially faulty processes must perform a set of m tasks. The problem is all the more challenging when there is heterogeneity, either on the workers' side, since individual agents may have varying speed and robustness, or because of uneven workloads. In large-scale systems, heterogeneity is the norm. Our work considers the dynamic version of task allocation, in which tasks are injected adversarially during an asynchronous execution. Intuitively, a major challenge in this setting is the fact that, at the same time, the adversary controls scheduling, process crashes, and the input.
We give a new shared-memory algorithm for dynamic task allocation which is within logarithmic factors of optimal. The main algorithmic idea is a randomized data structure called a dynamic to-do tree, which allows processes to pick new tasks to perform uniformly at random from the set of available tasks, and to insert tasks at uniform random locations in the data structure. We show that these properties avoid duplicating work unnecessarily in well-behaved executions, and that work duplication is inherent under certain input-schedule combinations. This is the first algorithm to allow efficient work sharing in this challenging setting, and the result has applications to other problems, such as producer-consumer buffers, and distributed renaming.