Counting in the Presence of Memory Faults

Gerth Stølting Brodal, Allan Grønlund Jørgensen, Gabriel Moruz, and Thomas Mølhave

In Proc. 20th Annual International Symposium on Algorithms and Computation, volume 5878 of Lecture Notes in Computer Science, pages 842-851. Springer Verlag, Berlin, 2009.

Abstract

The faulty memory RAM presented by Finocchi and Italiano is a variant of the RAM model where the content of any memory cell can get corrupted at any time, and corrupted cells cannot be distinguished from uncorrupted cells. An upper bound, δ, on the number of corruptions and O(1) reliable memory cells are provided.

In this paper we investigate the fundamental problem of counting in faulty memory. Keeping many reliable counters in the faulty memory is easily done by replicating the value of each counter Θ(δ) times and paying Θ(δ) time every time a counter is queried or incremented. In this paper we decrease the expensive increment cost to o(δ) and present upper and lower bound tradeoffs decreasing the increment time at the cost of the accuracy of the counters.

Copyright notice

© Springer-Verlag Berlin Heidelberg 2009. All rights reserved.

Online version

isaac09faults.pdf (140 Kb)

DOI

10.1007/978-3-642-10631-6_85

Links

BIBTEX entry

@incollection{isaac09faults,
  author = "Gerth St{\o}lting Brodal and Allan Gr{\o}nlund J{\o}rgensen and Gabriel Moruz and Thomas M{\o}lhave",
  booktitle = "Proc. 20th Annual International Symposium on Algorithms and Computation",
  doi = "10.1007/978-3-642-10631-6_85",
  isbn = "978-3-642-10630-9",
  pages = "842-851",
  publisher = "Springer {V}erlag, Berlin",
  series = "Lecture Notes in Computer Science",
  title = "Counting in the Presence of Memory Faults",
  volume = "5878",
  year = "2009"
}