Please use this identifier to cite or link to this item:
Title: How to allocate tasks asynchronously
Authors: Alistarh, D.
Bender, M.A.
Gilbert, S. 
Guerraoui, R.
Keywords: deterministic algorithms
distributed computing
randomized algorithms
task allocation
Issue Date: 2012
Citation: Alistarh, D., Bender, M.A., Gilbert, S., Guerraoui, R. (2012). How to allocate tasks asynchronously. Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS : 331-340. ScholarBank@NUS Repository.
Abstract: Asynchronous task allocation is a fundamental problem in distributed computing in which p asynchronous processes must execute a set of m tasks. Also known as write-all or do-all, this problem been studied extensively, both independently and as a key building block for various distributed algorithms. In this paper, we break new ground on this classic problem: we introduce the To-Do Tree concurrent data structure, which improves on the best known randomized and deterministic upper bounds. In the presence of an adaptive adversary, the randomized To-Do Tree algorithm has O(m + p log p log2 m) work complexity. We then show that there exists a deterministic variant of the To-Do Tree algorithm with work complexity O(m + p log5 m log2 max(m, p)). For all values of m and p, our algorithms are within log factors of the Ω(m + p log p) lower bound for this problem. The key technical ingredient in our results is a new approach for analyzing concurrent executions against a strong adaptive scheduler. This technique allows us to handle the complex dependencies between the processes' coin flips and their scheduling, and to tightly bound the work needed to perform subsets of the tasks. © 2012 IEEE.
Source Title: Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN: 02725428
DOI: 10.1109/FOCS.2012.41
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Jan 21, 2019


checked on Jan 21, 2019

Page view(s)

checked on Dec 8, 2018

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.