Dynamic task allocation in asynchronous shared memory

Dan Alistarh, James Aspnes, Michael Bender, Rati Gelashvili, and Seth Gilbert. Dynamic task allocation in asynchronous shared memory. 2014 ACM-SIAM Symposium on Discrete Algorithms, January 2014, pp. 416–435.

Abstract

Task allocation is a classic distributed problem in which a set of p potentially faulty processes must cooperate to perform a set of m tasks. This paper considers a new dynamic version of the problem, in which tasks are injected adversarially during an asynchronous execution. A major challenge in this setting is the fact that, at the same time, the adaptive adversary controls the scheduling and process crashes, as well as choosing the input. We give the first asynchronous shared-memory algorithm for dynamic task allocation, and we prove that our solution is optimal within logarithmic factors. The main algorithmic idea is a randomized data structure called a dynamic to-do tree, which allows processes to pick new tasks to perform at random from the set of available tasks, and to insert tasks at random available locations in the data structure. Our analysis shows that that these properties avoid duplicating work unnecessarily. On the other hand, since the adversary controls the input as well the scheduling, it can induce executions where lots of processes contend for a few available tasks, which is inefficient. However, we prove that every algorithm has the same problem: given an arbitrary input, if OPT is the worst-case complexity of the optimal algorithm on that input, then the expected complexity of our algorithm on the same input is O(OPT log³m).

BibTeX

Download
@inproceedings{AlistarhABGG2014,
author = {Dan Alistarh and James Aspnes and Michael Bender and Rati Gelashvili and Seth Gilbert},
title = {Dynamic task allocation in asynchronous shared memory},
month=jan,
year = 2014,
booktitle={2014 ACM-SIAM Symposium on Discrete Algorithms},
pages={416--435}
}

Consolidated BibTeX file
Return to James Aspnes's publications
Return to James Aspnes's home page