Priority Queues Resilient to Memory Faults | SpringerLink
Skip to main content
Springer Nature Link
Log in

Priority Queues Resilient to Memory Faults

  • Conference paper
Algorithms and Data Structures (WADS 2007)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 4619))

Included in the following conference series:

Abstract

In the faulty-memory RAM model, the content of memory cells can get corrupted at any time during the execution of an algorithm, and a constant number of uncorruptible registers are available. A resilient data structure in this model works correctly on the set of uncorrupted values. In this paper we introduce a resilient priority queue. The deletemin operation of a resilient priority queue returns either the minimum uncorrupted element or some corrupted element. Our resilient priority queue uses O(n) space to store n elements. Both insert and deletemin operations are performed in O(logn + δ) time amortized, where δ is the maximum amount of corruptions tolerated. Our priority queue matches the performance of classical optimal priority queues in the RAM model when the number of corruptions tolerated is O(logn). We prove matching worst case lower bounds for resilient priority queues storing only structural information in the uncorruptible registers between operations.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Constantinescu, C.: Trends and challenges in VLSI circuit reliability. IEEE micro 23(4), 14–19 (2003)

    Article  Google Scholar 

  2. Tezzaron Semiconductor: Soft errors in electronic memory - a white paper (2004), http://www.tezzaron.com/about/papers/papers.html

  3. van de Goor, A.J.: Testing Semiconductor Memories: Theory and Practice. ComTex Publishing, Gouda, The Netherlands (1998)

    Google Scholar 

  4. Boneh, D., DeMillo, R.A., Lipton, R.J.: On the importance of checking cryptographic protocols for faults. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 37–51. Springer, Heidelberg (1997)

    Google Scholar 

  5. Xu, J., Chen, S., Kalbarczyk, Z., Iyer, R.K.: An experimental study of security vulnerabilities caused by errors. In: Proc. International Conference on Dependable Systems and Networks, pp. 421–430 (2001)

    Google Scholar 

  6. Govindavajhala, S., Appel, A.W.: Using memory errors to attack a virtual machine. In: IEEE Symposium on Security and Privacy, pp. 154–165. IEEE Computer Society Press, Los Alamitos (2003)

    Google Scholar 

  7. Anderson, R., Kuhn, M.: Tamper resistance - a cautionary note. In: Proc. 2nd Usenix Workshop on Electronic Commerce, pp. 1–11 (1996)

    Google Scholar 

  8. Anderson, R., Kuhn, M.: Low cost attacks on tamper resistant devices. In: Christianson, B., Lomas, M. (eds.) Security Protocols. LNCS, vol. 1361, pp. 125–136. Springer, Heidelberg (1997)

    Chapter  Google Scholar 

  9. Skorobogatov, S.P., Anderson, R.J.: Optical fault induction attacks. In: Kaliski Jr., B.S., Koç, Ç.K., Paar, C. (eds.) CHES 2002. LNCS, vol. 2523, pp. 2–12. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  10. Huang, K.H., Abraham, J.A.: Algorithm-based fault tolerance for matrix operations. IEEE Transactions on Computers 33, 518–528 (1984)

    Article  MATH  Google Scholar 

  11. Rela, M.Z., Madeira, H., Silva, J.G.: Experimental evaluation of the fail-silent behaviour in programs with consistency checks. In: Proc. 26th Annual International Symposium on Fault-Tolerant Computing, pp. 394–403 (1996)

    Google Scholar 

  12. Yau, S.S., Chen, F.-C.: An approach to concurrent control flow checking. IEEE Transactions on Software Engineering SE-6(2), 126–137 (1980)

    Article  MathSciNet  Google Scholar 

  13. Pradhan, D.K.: Fault-tolerant computer system design. Prentice-Hall, Inc., Englewood Cliffs (1996)

    Google Scholar 

  14. Finocchi, I., Italiano, G.F.: Sorting and searching in the presence of memory faults (without redundancy). In: Proc. 36th Annual ACM Symposium on Theory of Computing, pp. 101–110. ACM Press, New York (2004)

    Google Scholar 

  15. Aumann, Y., Bender, M.A.: Fault tolerant data structures. In: Proc. 37th Annual Symposium on Foundations of Computer Science, Washington, DC, p. 580. IEEE Computer Society Press, Los Alamitos (1996)

    Google Scholar 

  16. Borgstrom, R.S., Kosaraju, S.R.: Comparison-based search in the presence of errors. In: Proc. 25th Annual ACM symposium on Theory of Computing, pp. 130–136. ACM Press, New York (1993)

    Google Scholar 

  17. Lakshmanan, K.B., Ravikumar, B., Ganesan, K.: Coping with erroneous information while sorting. IEEE Transactions on Computers 40(9), 1081–1084 (1991)

    Article  Google Scholar 

  18. Ravikumar, B.: A fault-tolerant merge sorting algorithm. In: Ibarra, O.H., Zhang, L. (eds.) COCOON 2002. LNCS, vol. 2387, pp. 440–447. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  19. Kutten, S., Peleg, D.: Fault-local distributed mending. Journal of Algorithms 30(1), 144–165 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  20. Kutten, S., Peleg, D.: Tight fault locality. SIAM Journal on Computing 30(1), 247–268 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  21. Diks, K., Pelc, A.: Optimal adaptive broadcasting with a bounded fraction of faulty nodes (extended abstract). In: Burkard, R.E., Woeginger, G.J. (eds.) ESA 1997. LNCS, vol. 1284, pp. 118–129. Springer, Heidelberg (1997)

    Google Scholar 

  22. Gasieniec, L., Pelc, A.: Broadcasting with a bounded fraction of faulty nodes. Journal of Parallel and Distributed Computing 42(1), 11–20 (1997)

    Article  Google Scholar 

  23. Hastad, J., Leighton, T.: Fast computation using faulty hypercubes. In: Proc. 21st Annual ACM Symposium on Theory of Computing, pp. 251–263. ACM Press, New York (1989)

    Google Scholar 

  24. Hastad, J., Leighton, T., Newman, M.: Reconfiguring a hypercube in the presence of faults. In: Proc. 19th Annual ACM Symposium on Theory of Computing, pp. 274–284. ACM Press, New York (1987)

    Google Scholar 

  25. Kaklamanis, C., Karlin, A.R., Leighton, F.T., Milenkovic, V., Raghavan, P., Rao, S., Thomborson, C.D., Tsantilas, A.: Asymptotically tight bounds for computing with faulty arrays of processors (extended abstract). In: Proc. 31st Annual Symposium on Foundations of Computer Science, pp. 285–296 (1990)

    Google Scholar 

  26. Leighton, F.T., Maggs, B.M.: Expanders might be practical: Fast algorithms for routing around faults on multibutterflies. In: Proc. 30th Annual Symposium on Foundations of Computer Science, pp. 384–389 (1989)

    Google Scholar 

  27. Park, S., Bose, B.: All-to-all broadcasting in faulty hypercubes. IEEE Transactions on Computers 46(7), 749–755 (1997)

    Article  Google Scholar 

  28. Finocchi, I., Grandoni, F., Italiano, G.F.: Optimal resilient sorting and searching in the presence of memory faults. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4051, pp. 286–298. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  29. Finocchi, I., Grandoni, F., Italiano, G.F.: Resilient search trees. In: Proc. 18th ACM-SIAM Symposium on Discrete Algorithms (to appear)

    Google Scholar 

  30. Petrillo, U.F., Finocchi, I., Italiano, G.F.: The price of resiliency: a case study on sorting with memory faults. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol. 4168, pp. 768–779. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  31. Arge, L., Bender, M.A., Demaine, E.D., Holland-Minkley, B., Munro, J.I.: Cache-oblivious priority queue and graph algorithm applications. In: Proc. 34th Annual ACM Symposium on Theory of Computing, pp. 268–276. ACM Press, New York (2002)

    Google Scholar 

  32. Boyer, R.S., Moore, J.S.: MJRTY: A fast majority vote algorithm. In: Automated Reasoning: Essays in Honor of Woody Bledsoe, pp. 105–118 (1991)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. BRICS, MADALGO, Department of Computer Science, University of Aarhus, Denmark

    Allan Grønlund Jørgensen, Gabriel Moruz & Thomas Mølhave

Authors
  1. Allan Grønlund Jørgensen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Gabriel Moruz
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Thomas Mølhave
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Frank Dehne Jörg-Rüdiger Sack Norbert Zeh

Rights and permissions

Reprints and permissions

Copyright information

© 2007 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Jørgensen, A.G., Moruz, G., Mølhave, T. (2007). Priority Queues Resilient to Memory Faults. In: Dehne, F., Sack, JR., Zeh, N. (eds) Algorithms and Data Structures. WADS 2007. Lecture Notes in Computer Science, vol 4619. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-73951-7_12

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-73951-7_12

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-73948-7

  • Online ISBN: 978-3-540-73951-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation