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 + k2log3k) 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.)