ALGORITHMS FOR THE CERTIFIED WRITE-ALL PROBLEM

Authors
ANDERSON RJ WOLL H
Citation
Rj. Anderson et H. Woll, ALGORITHMS FOR THE CERTIFIED WRITE-ALL PROBLEM, SIAM journal on computing, 26(5), 1997, pp. 1277-1283
Citations number
6
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods",Mathematics
Journal title
SIAM journal on computing → ACNP
ISSN journal
00975397
Volume
26
Issue
5
Year of publication
1997
Pages
1277 - 1283
Database
ISI
SICI code
0097-5397(1997)26:5<1277:AFTCWP>2.0.ZU;2-E
Abstract
In this paper, we prove new upper bounds on the complexity of the cert ified write-all problem with respect to an adaptive adversary. Our str ongest result is that for any epsilon > 0, there exists an O(p(1+epsil on)) work algorithm for the p-processor p-memory cell write-all. We al so give a randomized O(p(2) log p) work algorithm for a p-processor p( 2)-memory cell write-all.