TY - JOUR
T1 - Writing-all deterministically and optimally using a nontrivial number of asynchronous processors
AU - Kowalski, Dariusz R.
AU - Shvartsman, Alexander A.
N1 - DBLP License: DBLP's bibliographic metadata records provided through http://dblp.org/ are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.
PY - 2008
Y1 - 2008
N2 - The problem of performing n tasks on p asynchronous or undependable processors is a basic problem in distributed computing. This article considers an abstraction of this problem called Write-All: using p processors write 1's into all locations of an array of size n. In this problem writing 1 abstracts the notion of performing a simple task. Despite substantial research, there is a dearth of efficient deterministic asynchronous algorithms for Write-All/. Efficiency of algorithms is measured in terms of work that accounts for all local steps performed by the processors in solving the problem. Thus, an optimal algorithm would have work Θ(n), however it is known that optimality cannot be achieved when p = (n). The quest then is to obtain work-optimal solutions for this problem using a nontrivial, compared to n, number of processors p. The algorithm presented in this article has work complexity of O(n + p2 + ε), and it achieves work optimality for p = O(n 1/(2 + ε)) for any ε > 0, while the previous best result achieved optimality for p4n/log n. Additionally, the new result uses only the atomic read/write memory, without resorting to using the test-and-set primitive that was necessary in the previous solution.
AB - The problem of performing n tasks on p asynchronous or undependable processors is a basic problem in distributed computing. This article considers an abstraction of this problem called Write-All: using p processors write 1's into all locations of an array of size n. In this problem writing 1 abstracts the notion of performing a simple task. Despite substantial research, there is a dearth of efficient deterministic asynchronous algorithms for Write-All/. Efficiency of algorithms is measured in terms of work that accounts for all local steps performed by the processors in solving the problem. Thus, an optimal algorithm would have work Θ(n), however it is known that optimality cannot be achieved when p = (n). The quest then is to obtain work-optimal solutions for this problem using a nontrivial, compared to n, number of processors p. The algorithm presented in this article has work complexity of O(n + p2 + ε), and it achieves work optimality for p = O(n 1/(2 + ε)) for any ε > 0, while the previous best result achieved optimality for p4n/log n. Additionally, the new result uses only the atomic read/write memory, without resorting to using the test-and-set primitive that was necessary in the previous solution.
KW - Asynchrony
KW - Distributed algorithms
KW - Shared memory
KW - Work
KW - Write-All
UR - http://www.scopus.com/inward/record.url?scp=47249162476&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=47249162476&partnerID=8YFLogxK
U2 - 10.1145/1367064.1367073
DO - 10.1145/1367064.1367073
M3 - Article
AN - SCOPUS:47249162476
SN - 1549-6325
VL - 4
SP - 33:1-33:22
JO - ACM Transactions on Algorithms
JF - ACM Transactions on Algorithms
IS - 3
M1 - 33
ER -