The price of resiliency: a case study on sorting with memory faults

DOI10.1007/s00453-008-9264-1zbMath1183.68229OpenAlexW1486279778WikidataQ61609544 ScholiaQ61609544MaRDI QIDQ1016529

Umberto Ferraro-Petrillo, Giuseppe F. Italiano, Irene Finocchi

Publication date: 6 May 2009

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.330.5099

zbMATH Keywords

sortingmemory modelsexperimental algorithmicsfault injectionmemory faultscomputing with unreliable information

Mathematics Subject Classification ID

Searching and sorting (68P10)

Related Items

Recursive merge sort with erroneous comparisons ⋮ Resilient dynamic programming

Uses Software

• CONFID
• Quicksort

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Designing reliable algorithms in unreliable memories
• Sorting and searching in faulty memories
• Searching with known error probability
• Coping with errors in binary search procedures
• Braking the \(\Theta(n\log^ 2 n)\) barrier for sorting with faults
• On Fault-Tolerant Networks for Sorting
• Optimal Resilient Dynamic Dictionaries
• Priority Queues Resilient to Memory Faults
• Optimal Resilient Sorting and Searching in the Presence of Memory Faults
• Fault Tolerant Sorting Networks
• Tight Bounds on the Size of Fault-Tolerant Merging and Sorting Networks with Destructive Faults
• Computing with Noisy Information
• On word-level parallelism in fault-tolerant computing
• Comparison-based search in the presence of errors
• The Price of Resiliency: A Case Study on Sorting with Memory Faults
• Automata, Languages and Programming
• Computer Aided Verification
• Searching games with errors -- fifty years of coping with liars