Startseite > Publikationen > Publikationen


Berenbrink, Petra;Meyer auf der Heide, Friedhelm;Stemann, Volker:

Fault Tolerant Shared Memory Simulations.

Proc. of 13th STACS : S. 181-192, Jun. 1996


We consider the problem of simulating a PRAM on a faulty distributed memory machine (DMM), We locus on dynamic faults, i.e. each processor or memory module independently fails during the simulation of a PRAM step with fixed probability and remains faulty for the rest of the simulation. We build upon randomized hashing-based simulations on non-faulty DMMs from [14], which achieve delay O(log log n), with high probability. We design and analyze routines for handling faults occurring during the simulation. Based on these routines we present simulations on faulty DMMs with the same delay O(log log n) as in the non-faulty case, provided that the failure probability of processors and modules is small enough to guarantee an expected linear number of processors and modules to survive the simulation. Thus the facility of being resilient to memory or processor faults increases the delay of the simulation at most by a constant factor.




author = {Berenbrink, Petra and Meyer auf der Heide, Friedhelm and Stemann, Volker},
title = {Fault Tolerant Shared Memory Simulations},
journal = {Proc. of 13th STACS},
pages = {181-192},
month = jun,
year = {1996},

BibTeX in die Zwischenablage kopieren