@inproceedings{f3c812fea1b946728c56ba440bbd4c9e,
title = "Shared-memory simulations on a faulty-memory DMM",
abstract = "We study the Distributed Memory Machine (DMM) with faults in memory. The DMM consists of n synchronized processors together with n memory units (MUs). A MU can be accessed by at most one processor at a time. The total number of memory faults is assumed to be at most a fixed fraction of the total number of words. We develop two fast randomized simulations of the PRAM on such a faulty DMM. A simulation consists of two phases: the preprocessing is followed by the simulation proper done in a step-by-step fashion. One simulation is of an n log n-processor PRAM and it operates with the optimal expected slowdown O(log n), the other is of a PRAM with n/log n processors and has the slowdown O(log log n).",
author = "Chlebus, {Bogdan S.} and Anna Gambin and Piotr Indyk",
year = "1996",
doi = "10.1007/3-540-61440-0_161",
language = "English (US)",
isbn = "3540614400",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "586--597",
editor = "{Meyer auf der Heide}, Friedhelm and Burkhard Monien",
booktitle = "Automata, Languages and Programming - 23rd International Colloquium, ICALP 1996, Proceedings",
note = "23rd International Colloquium on Automata, Languages, and Programming, ICALP 1996 ; Conference date: 08-07-1996 Through 12-07-1996",
}