We present a randomized algorithm for asynchronous task allocation, also known as the write-all or do-all problem. Our algorithm has work complexity O(n+k2 log3 k) with high probability, where n the number of tasks and k the number of processes that participate in the computation. Our solution uses O(n) shared memory space that supports atomic test-and-set operations and with high probability each participating process uses O(k) internal memory space. 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.
|Title of host publication||Distributed Computing Systems (ICDCS), 2015 IEEE 35th International Conference on|
|Publisher||Institute of Electrical and Electronics Engineers (IEEE)|
|Number of pages||10|
|Publication status||Published - Jun 2015|