#
Asynchronous adaptive task allocation

##
Sotirios Kentros

We present a randomized algorithm for asynchronous task allocation, also
known as the write-all or do-all problem. Our algorithm has work
complexity
of *O*(*n* + *k*^{2}log^{3}*k*)
with high probability, where *n* is the number of tasks
and *k* is the number of processes that participate in the
computation. This is the first adaptive solution for the write-all
problem that has work *n* plus some additive term which depends
only on the number of participating processes *k* and not the
size of the problem *n*.

(Joint work with Chadi Kari, Aggelos Kiayias, and Alexander Russell.)