Startseite > Publikationen > 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

Abstract

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.

Dateien

hni1853.pdf



Bibtex

@article{hniid=1853,
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

Permalink

https://www.hni.uni-paderborn.de/pub/1853