Asynchronous Adaptive Task Allocation

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

doi:10.1109/ICDCS.2015.17

Asynchronous Adaptive Task Allocation

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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 language	English
Title of host publication	Distributed Computing Systems (ICDCS), 2015 IEEE 35th International Conference on
Publisher	Institute of Electrical and Electronics Engineers (IEEE)
Pages	83-92
Number of pages	10
ISBN (Electronic)	978-1-4673-7214-5
DOIs	https://doi.org/10.1109/ICDCS.2015.17
Publication status	Published - Jun 2015

Access to Document

10.1109/ICDCS.2015.17

Cite this

@inproceedings{5184b239bc0f4e1ba43b2eee9df17ca5,

title = "Asynchronous Adaptive Task Allocation",

abstract = "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.",

author = "S. Kentros and C. Kari and A. Kiayias and A. Russell",

year = "2015",

month = jun,

doi = "10.1109/ICDCS.2015.17",

language = "English",

pages = "83--92",

booktitle = "Distributed Computing Systems (ICDCS), 2015 IEEE 35th International Conference on",

publisher = "Institute of Electrical and Electronics Engineers (IEEE)",

address = "United States",

}

TY - GEN

T1 - Asynchronous Adaptive Task Allocation

AU - Kentros, S.

AU - Kari, C.

AU - Kiayias, A.

AU - Russell, A.

PY - 2015/6

Y1 - 2015/6

N2 - 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.

AB - 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.

U2 - 10.1109/ICDCS.2015.17

DO - 10.1109/ICDCS.2015.17

M3 - Conference contribution

SP - 83

EP - 92

BT - Distributed Computing Systems (ICDCS), 2015 IEEE 35th International Conference on

PB - Institute of Electrical and Electronics Engineers (IEEE)

ER -

Asynchronous Adaptive Task Allocation

Abstract

Access to Document

Fingerprint

Cite this