Asynchronous Adaptive Task Allocation

S. Kentros, C. Kari, A. Kiayias, A. Russell

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.
Original languageEnglish
Title of host publicationDistributed Computing Systems (ICDCS), 2015 IEEE 35th International Conference on
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages10
ISBN (Electronic)978-1-4673-7214-5
Publication statusPublished - Jun 2015


Dive into the research topics of 'Asynchronous Adaptive Task Allocation'. Together they form a unique fingerprint.

Cite this