Skip to search boxSkip to navigationSkip to main content

An efficient Write-All algorithm for fail-stop PRAM without initialized memory

*Corresponding author for this work
  • Brown University
    ,
  • Hewlett-Packard
Scholary Output:
Contribution to journal
Article
Research
Peer-review

Abstract

The problem of Write-All-using P processors to write 1's into all locations of an array of size N, where P ≤ N-has been used as the basic building block for constructing efficient and fault-tolerant parallel algorithms. All previous Write-All solutions use Ω(P) auxiliary shared memory and assume that this memory is cleared or initialized to some known value. When Write-All building blocks are used in polylogarithmic parallel time algorithms, auxiliary memory initialization cannot be amortized over the computation. Thus, assuming clear memory is a very strong precondition, and for Write-All itself raises a legitimate "chicken-or-egg" objection. Using a determistic bootstraping and balancing argument, we show how to Write-All when auxiliary memory is contaminated with arbitrary values. For any dynamic pattern of fail-stop, no-restart errors on a CRCW PRAM with at least one surviving processor, our new algorithm writes all 1's using O( N + Plog3N (loglog N)2) work, without any initialization assumption. This technique can be combined with any Write-All algorithm to yield efficient simulations of any PRAM and even optimal simulations given processor slack. It can also be used with restartable fail-stop processor simulations.

Publication Information

Output type

Scholary Output:
Contribution to journal
Article
Research
Peer-review

Original language

English (US)

Pages from-to (Number of pages)

Pages 223-232 (10 pages)

Journal (Volume, Issue Number)

Information Processing Letters (Volume 44, Issue 4)

Publication milestones

  • Published - 12/10/1992

Publication status

Published - 12/10/1992

ISSN

0020-0190

Publication IDs

  • Scopus: 0345777691
  • ORCID: /0000-0003-4447-3267/work/97283801

Publication metrics

Metrics

Scopus
citations
Fractional count
1
Fractional count
1
Fractional count
1
Fractional count
1

PlumX, opens in new tab

Citation count
4
Captures
2