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.

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*).

- SODA 2014 proceedings version:
**PDF**.

@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