Deterministic Computations on a PRAM with Static Processor and Memory Faults

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 O((m/n+ logn)logn). The slowdown of a step-by-step part of the simulation is O(logm).