Fault Tolerant Algorithms and Data Structures
Time: November, 19, 2007, 1pm - 2pm
Place: D344, LSRC
Speaker: Thomas Mølhave

In a soft memory error, a bit flips and consequently the content of the corresponding memory cell gets corrupted. Memory devices are getting smaller and more complex and they work at increasingly lower voltages and higher frequencies, and all these improvements increase the likelihood of soft memory errors. Memory corruptions are of particular concern for applications dealing with massive amounts of data, e.g. search engines. The large number of memory devices used to manipulate the data triggers a dramatic increase in the frequency of memory corruptions. This is especially problematic in computing clusters consisting of a large number of standard computers with relatively cheap off-the-shelf components. Taking into account that the amount of cosmic rays increases with altitude, soft memory errors are also of interest in fields like avionics and space research. Finocchi and Italiano recently proposed the ``faulty memory random access machine'' model of computation. In this model 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 possible, and O(1) reliable memory cells are provided. In this model, an algorithm is ``resilient'' if it gives the correct output on the set of uncorrupted elements. In this talk we will introduce the faulty memory RAM and give some recent results. In particular, we will present optimal resilient dictionaries, supporting searches and updates in $O(\log n+\d)$ time and very recent results in the intersection of resilient algorithms and input/output efficient algorithms.