How to allocate tasks asynchronously

D.-A. Alistarh, M. Bender, S. Gilbert, R. Guerraoui, in:, IEEE, 2012, pp. 331–340.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published | English
Author
Alistarh, Dan-AdrianIST Austria; Bender, Michael; Gilbert, Seth; Guerraoui, Rachid
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.
Publishing Year
Date Published
2012-01-01
Page
331 - 340
Conference
FOCS: Foundations of Computer Science
IST-REx-ID
766

Cite this

Alistarh D-A, Bender M, Gilbert S, Guerraoui R. How to allocate tasks asynchronously. In: IEEE; 2012:331-340. doi:10.1109/FOCS.2012.41
Alistarh, D.-A., Bender, M., Gilbert, S., & Guerraoui, R. (2012). How to allocate tasks asynchronously (pp. 331–340). Presented at the FOCS: Foundations of Computer Science, IEEE. https://doi.org/10.1109/FOCS.2012.41
Alistarh, Dan-Adrian, Michael Bender, Seth Gilbert, and Rachid Guerraoui. “How to Allocate Tasks Asynchronously,” 331–40. IEEE, 2012. https://doi.org/10.1109/FOCS.2012.41.
D.-A. Alistarh, M. Bender, S. Gilbert, and R. Guerraoui, “How to allocate tasks asynchronously,” presented at the FOCS: Foundations of Computer Science, 2012, pp. 331–340.
Alistarh D-A, Bender M, Gilbert S, Guerraoui R. 2012. How to allocate tasks asynchronously. FOCS: Foundations of Computer Science 331–340.
Alistarh, Dan-Adrian, et al. How to Allocate Tasks Asynchronously. IEEE, 2012, pp. 331–40, doi:10.1109/FOCS.2012.41.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar