Shared-memory simulations on a faulty-memory DMM

Bogdan S. Chlebus, Anna Gambin, Piotr Indyk

Research output: Chapter in Book/Report/Conference proceedingConference contribution

13 Scopus citations


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).

Original languageEnglish (US)
Title of host publicationAutomata, Languages and Programming - 23rd International Colloquium, ICALP 1996, Proceedings
EditorsFriedhelm Meyer auf der Heide, Burkhard Monien
PublisherSpringer Verlag
Number of pages12
ISBN (Print)3540614400, 9783540614401
StatePublished - 1996
Externally publishedYes
Event23rd International Colloquium on Automata, Languages, and Programming, ICALP 1996 - Paderborn, Germany
Duration: Jul 8 1996Jul 12 1996

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference23rd International Colloquium on Automata, Languages, and Programming, ICALP 1996

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Shared-memory simulations on a faulty-memory DMM'. Together they form a unique fingerprint.

Cite this