Deterministic Computations on a PRAM with Static Processor and Memory Faults

Bogdan S. Chlebus, Leszek Ga̧sieniec, Andrzej Pelc

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


We consider Parallel Random Access Machine (PRAM) which has some processors and memory cells faulty. The faults considered are static, i.e., once the machine starts to operate, the operational/faulty status of PRAM components does not change. We develop a deterministic simulation of a fully operational PRAM on a similar faulty machine which has constant fractions of faults among processors and memory cells. The simulating PRAM has n processors and m memory cells, and simulates a PRAM with n processors and a constant fraction of m memory cells. The simulation is in two phases: it starts with preprocessing, which is followed by the simulation proper performed in a step-by-step fashion. Preprocessing is performed in time script O sign ( ( m/n + log n) log n). The slowdown of a step-by-step part of the simulation is script O sign (log m).

Original languageEnglish (US)
Pages (from-to)285-306
Number of pages22
JournalFundamenta Informaticae
Issue number3-4
StatePublished - Jun 1 2003
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Algebra and Number Theory
  • Information Systems
  • Computational Theory and Mathematics


Dive into the research topics of 'Deterministic Computations on a PRAM with Static Processor and Memory Faults'. Together they form a unique fingerprint.

Cite this