BIBLIOGRAPHY

CACHE OBLIVIOUS

[ABD+02] Lars Arge, Michael A. Bender, Erik D. Demaine, Bryan
Holland-Minkley, and J. Ian Munro. Cache-oblivious priority queue and
graph algorithm applications. In Proceedings of the 34th Annual ACM
Symposium on Theory of Computing, pages 268Ð276, Montr«eal, Canada, May
2002.

[BCR02] Michael A. Bender, Richard Cole, and Rajeev Raman. Exponential
structures for efficient cache-oblivious algorithms. In Proceedings of
the 29th International Colloquium on Automata, Languages and
Programming, volume 2380 of Lecture Notes in Computer Science, pages
195Ð207, Malaga, Spain, July 2002.

[BDFC00] Michael A. Bender, Erik D. Demaine, and Martin Farach-Colton.
Cache oblivious B-trees. In Proceedings of the 41st Annual Symposium on
Foundations of Computer Science, pages 399Ð409, Redondo Beach,
California, November 2000.

[BDIW02] Michael A. Bender, Ziyang Duan, John Iacono, and Jing Wu. A
locality preserving cache-oblivious dynamic dictionary. In Proceedings
of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pages
29Ð38, San Francisco, California, January 2002.

[BF02a] Gerth St¿lting Brodal and Rolf Fagerberg. Cache oblivious
distribution sweeping. In Proceedings of the 29th International
Colloquium on Automata, Languages, and Programming, volume 2380 of
Lecture Notes in Computer Science, pages 426Ð438, Malaga, Spain, July
2002.

[BF02b] Gerth St¿lting Brodal and Rolf Fagerberg. Funnel heap Ð a cache
oblivious priority queue. In Proceedings of the 13th Annual
International Symposium on Algorithms and Computation, volume 2518 of
Lecture Notes in Com puter Science, pages 219Ð228, Vancouver, Canada,
November 2002.

[BF03] Gerth St¿lting Brodal and Rolf Fagerberg. On the limits of cache
obliviousness. In Proceedings of the 35th Annual ACM Symposium on Theory
of Computing, San Diego, California, June 2003. 

[BFJ+96] Robert D. Blumofe, Matteo Frigo, Christopher F. Joerg, Charles
E. Leiserson, and Keith H. Randall. An analysis of dag-consistent
distributed shared-memory algorithms. In Proceedings of the 8th Annual
ACM Symposium on Parallel Algorithms and Architectures, pages 297Ð308,
Padua, Italy, June 1996.

[BFJ02] Gerth St¿lting Brodal, Rolf Fagerberg, and Riko Jacob. Cache
oblivious search trees via binary trees of small height. In Proceedings
of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pages
39Ð48, San Francisco, California, January 2002.

FLPR99] Matteo Frigo, Charles E. Leiserson, Harald Prokop, and Sridhar
Ramachandran. Cache-oblivious algorithms. In Proceedings of the 40th An
nual Symposium on Foundations of Computer Science, pages 285Ð297, New
York, October 1999. 

[LFN02] Richard E.
Ladner, Ray Fortna, and Bao-Hoang Nguyen. A comparison of cache aware
and cache oblivious static search trees using program in strumentation.
In Experimental Algorithmics: From Algorithm Design to Robust and
Efficient Software, volume 2547 of Lecture Notes in Computer Science,
pages 78Ð92, 2002. 

[Oha01] Darin Ohashi. Cache oblivious data
structures. MasterÕs thesis, Department of Computer Science, University
of Waterloo, Waterloo, Canada, 2001.  

[Pro99] Harald Prokop.
Cache-oblivious algorithms. MasterÕs thesis, Mas sachusetts Institute of
Technology, Cambridge, MA, June 1999. 

[ST85a] Daniel D. Sleator and
Robert E. Tarjan. Amortized efficiency of list update and paging rules.
Communications of the ACM, 28(2):202Ð208, 1985. 

[vE77] Peter van Emde Boas. Preserving order in a forest in less
than logarithmic time and linear space. Information Processing Letters,
6(3):80Ð82, 1977. 

[vEKZ77] Peter van Emde Boas, R. Kaas, and E.
Zijlstra. Design and implementation of an efficient priority queue.
Mathematical Systems Theory, 10(2):99Ð127, 1977. 


EXTERNAL MEMORY

[Arg95] Lars Arge. The buffer tree: A new technique for optimal
I/O-algorithms. In Proceedings of the 4th International Workshop on
Algorithms and Data Structures, pages 334Ð345, Kingston, Canada, August
1995.

[AV88] Alok Aggarwal and Jeffrey Scott Vitter. The input/output
complexity of sorting and related problems. Communications of the ACM,
31(9):1116Ð 1127, September 1988.


[BCDFC02] Michael A. Bender, Richard Cole, Erik D. Demaine, and Martin
Farach- Colton. Scanning and traversing: Maintaining data for traversals
in a memory hierarchy. In Proceedings of the 10th Annual European
Symposium on Algorithms, volume 2461 of Lecture Notes in Computer
Science, pages 139Ð151, Rome, Italy, September 2002.

[CGGTVV95] Y.-J.Chiang, M.T.Goodrich, E.F.Grove, R.Tamassia, D.E.Vengroff
, and 
J.S.Vitter. External-memory graph algorithms. In Proceedings of the ACM-SIAM 
Symposium on Discrete Algorithms, volume 6, 139-149, January1995¥.

[HK81] Jia-Wei
Hong and H. T. Kung. I/O complexity: The red-blue pebble game. In
Proceedings of the 13th Annual ACM Symposium on Theory of Computation,
pages 326Ð333, Milwaukee, Wisconsin, May 1981. 

[MR99] K. Munagala and A. Ranade. I/O-complexity of graph algorithms. In Proceedings 
of the ACM SIAM Symposium on Discrete Algorithms, volume 10, 687-694, Baltimore, MD,
January 1999. 

[Tol97] Sivan Toledo.
Locality of reference in LU decomposition with partial pivot ing. SIAM
Journal on Matrix Analysis and Applications, 18(4):1065Ð1081, October
1997. 

[Vit98] J.S.Vitter. External memory algorithms. In Proceedings of the European 
Symposium on Algorithms, volume1461 of Lecture Notes in Computer Science, Venice, 
Italy, August1998, Springer-Verlag. Invited paper. 


[Vit99] J.S.Vitter. External memory algorithms and data structures. In J.Abello and 
J.S.Vitter editors, External Memory Algorithms and Visualization, DIMACS Series in 
Discrete Mathematics and Theoretical Computer Science.American Mathematical Society 
Press, Providence RI,1999.

[Vit01] Jeffrey Scott
Vitter. External memory algorithms and data structures: Dealing with
massive data. ACM Computing Surveys, 33(2):209Ð271, June 2001. 

[Wil92]
Dan E. Willard. A density control algorithm for doing insertions and
deletions in a sequentially ordered file in good worst-case time.
Information and Computation, 97(2):150Ð204, April 1992.

RESILIENT

[AK96]
R. Anderson and M. Kuhn. Tamper resistance -- a cautionary note.
 Proc. 2nd Usenix Workshop on Electronic Commerce, 1--11, 1996.

[AK97]
R. Anderson and M. Kuhn. Low cost attacks on tamper resistant devices.
  Proc. International Workshop on Security Protocols, 125--136, 1997.

[AD91]
J.A. Aslam and A. Dhagat.  Searching in the presence of linearly
bounded errors.   Proc.  23rd STOC, 486--493, 1991.

[AU91]
S. Assaf and E. Upfal.  Fault-tolerant sorting networks.  
SIAM J. Discrete Math., 4(4), 472--480, 1991.

[AB96]
Y. Aumann and M.A. Bender.  Fault-tolerant data structures.
 Proc.  37th IEEE Symp.  on Foundations of Computer Science
(FOCS'96), 580--589, 1996.

[BS03]
J. Bloemer and J.P. Seifert.  Fault based cryptanalysis of the
Advanced Encryption Standard (AES).   Proc.  7th International
Conference on Financial Cryptography (FC'03), LNCS 2742, 162--181,
2003.

[BDL97]
D. Boneh, R. A. DeMillo, and R. J. Lipton. On the importance of checking
cryptographic protocols for faults.  Proc. EUROCRYPT\/, 37--51, 1997.

[BK93]
R.S. Borgstrom and S. Rao Kosaraju.  Comparison based search in
the presence of errors.   Proc.  25th STOC, 130--136, 1993.

[BM82]
R. Boyer and S. Moore.  MJRTY - A fast majority vote algorithm.
University of Texas Tech. Report, 1982.

[BFF07]
G. S. Brodal, R. Fagerberg, I. Finocchi, F. Grandoni, G. F.
Italiano, A. G. Jorgensen, G. Moruz e T. Molhave. Optimal
Resilient Dynamic Dictionaries.  Proc. 15th Annual European
Symposium on Algorithms (ESA'07), 347--358, 2007.

[BJMM09]
G. S. Brodal, A. G. Jorgensen, G. Moruz and T. Molhave. Counting in the presence of memory faults.  Proc. 20th Int. Symposium on Algorithms and Computation (ISAAC'09), 842--851, 2009.

[BJM09]
G. S. Brodal, A. G. Jorgensen, and T. Molhave. Fault tolerant external memory algorithms.  Proc. 11th Int. Symposium on Algorithms and Data Structures (WADS'09), 411--422, 2009.

[CGI96]
B. S. Chlebus, A. Gambin and P. Indyk.  Shared-memory simulations on a
faulty-memory DMM.  Proc.  23rd International Colloquium on
Automata, Languages and Programming (ICALP'96), 586--597, 1996.

[CGP03]
B. S. Chlebus, L. Gasieniec and A. Pelc.  Deterministic computations
on a PRAM with static processor and memory faults.   Fundamenta
Informaticae, 55(3-4), 285--306, 2003.

[CK80]
C. R. Cook and D. J. Kim.  Best sorting algorithms for nearly sorted lists.   Comm. of the ACM, 23, 620--624, 1980.

[DGW92]
A. Dhagat, P. Gacs, and P. Winkler.   On playing ``twenty
questions'' with a liar.    Proc.  3rd ACM-SIAM Symp.  on
Discrete Algorithms (SODA'92), 16--22, 1992.

[FPRU94]
U. Feige, P. Raghavan, D. Peleg, and E. Upfal.  Computing with
noisy information.   SIAM J. on Comput., 23,
1001--1018, 1994.

[FFI09]
U. Ferraro-Petrillo, I. Finocchi, and G. F. Italiano.
The Price of Resiliency: a Case Study on Sorting with Memory Faults. 
Algorithmica,  53(4):597--620, 2009.

[FGI10]
U. Ferraro-Petrillo, F. Grandoni, and G. F. Italiano.
Data Structures Resilient to Memory Faults: An Experimental Study of Dictionaries. 
Proc. SEA 2010.

[FGI07]
I. Finocchi, F. Grandoni, and G. F. Italiano.  
Designing reliable algorithms in unreliable memories.   
Computer Science Review, 1(2), 77--87, 2007. 

[FGI06]
I. Finocchi, F. Grandoni, and G. F. Italiano. Optimal sorting and
searching in the presence of memory faults. 
 Theor. Comput. Sci. 410(44):4457-4470, 2009.


[FGI07]
I. Finocchi, F. Grandoni, and G. F. Italiano. Resilient search trees.   
Proc. 18th ACM-SIAM Symposium on Discrete Algorithms (SODA'07), 547--553, 2007.

[FI08]
I. Finocchi and G. F. Italiano.  Sorting and searching in faulty memories.   
Algorithmica, 52(3), 309--332, 2008. Preliminary version in  Proc.  36th ACM STOC, 101--110, 2004.  

[GA03]
S. Govindavajhala and A. W. Appel. Using memory errors to attack a
virtual machine.  Proc. IEEE Symposium on Security and Privacy,
154--165, 2003.

[HAGR03]
S. Hamdioui, Z. Al-Ars, J. Van de Goor, and M. Rodgers.
Dynamic faults in Random-Access-Memories: Concept, faults models and
tests.    Journal of Electronic Testing: Theory and
Applications, 19, 195--205, 2003.


[I96]
P. Indyk.  On word-level parallelism in fault-tolerant computing.
 Proc.  13th Annual Symp.  on Theoretical Aspects of Computer
Science (STACS'96), 193--204, 1996.

[JMM07]
A. G. Jorgensen, G. Moruz and T. Molhave. 
Priority queues resilient to memory faults.    
Proc. 10th Workshop on Algorithms and Data Structures (WADS'07), 127--138, 2007. 

[KMRSW80]
D.J. Kleitman, A.R. Meyer, R.L. Rivest, J. Spencer, and K.
Winklmann.   Coping with errors in binary search procedures.
J. Comp. Syst. Sci., 20:396--404,
1980.

[LR04]
C. Lu and D. A. Reed.  Assessing fault sensitivity in MPI applications.  
Proc. 2004 ACM/IEEE Conf. on Supercomputing (SC'04), 37, 2004.

[MW79]
T. C. May and M. H. Woods.  Alpha-Particle-Induced Soft Errors In 
Dynamic Memories.   IEEE Trans.  Elect.  Dev., 26(2), 1979.

[P89]
A. Pelc.  Searching with known error probability.  
Theoretical Computer Science, 63, 185--202, 1989.

[P02]
A. Pelc.  Searching games with errors: Fifty years of coping with
liars.   Theoret. Comp. Sci., 270, 71--109, 2002.

[PWB07]
E. Pinheiro, W. Weber, and L. A. Barroso.  
Failure trends in large disk drive populations.   
Proc. 5th USENIX Conference on File and Storage Technologies, 2007.

[R02]
B. Ravikumar.  A fault-tolerant merge sorting algorithm.  
Proc. 8th COCOON, LNCS 2387, 440--447, 2002.

[RLM06]
D. A. Reed, C. Lu and C. L. Mendes.  Reliability challenges in large systems.
 Future Gener. Comput. Syst., 22(3), 293--302, 2006.

[S06]
G.K. Saha.  Software based fault tolerance: a survey.
 Ubiquity, 7(25), 1, 2006.

[SA02]
S. Skorobogatov and R. Anderson.  Optical fault induction attacks.
 Proc.  4th International Workshop on Cryptographic Hardware and
Embedded Systems (CHES'02), LNCS 2523, 2--12, 2002.