We investigate the design of algorithms resilient to memory faults, i.e., algorithms that, despite the corruption of some memory values during their execution, are able to produce a correct output on the set of uncorrupted values. In this framework, we consider two fundamental problems: sorting and searching. In particular, we prove that any O(n log n) comparison-based sorting algorithm can tolerate at most O((n log n)1/2) memory faults. Furthermore, we present one comparison-based sorting algorithm with optimal space and running time that is resilient to O((n log n)1/3) faults. We also prove polylogarithmic lower and upper bounds on fault-tolerant searching.
Sorting and searching in the presence of memory faults (without redundancy) / Finocchi, Irene; Giuseppe F., Italiano. - STAMPA. - -:(2004), pp. 101-110. (Intervento presentato al convegno Proceedings of the 36th Annual ACM Symposium on Theory of Computing tenutosi a Chicago, IL nel 13 June 2004 through 15 June 2004) [10.1145/1007352.1007375].
Sorting and searching in the presence of memory faults (without redundancy)
FINOCCHI, Irene;
2004
Abstract
We investigate the design of algorithms resilient to memory faults, i.e., algorithms that, despite the corruption of some memory values during their execution, are able to produce a correct output on the set of uncorrupted values. In this framework, we consider two fundamental problems: sorting and searching. In particular, we prove that any O(n log n) comparison-based sorting algorithm can tolerate at most O((n log n)1/2) memory faults. Furthermore, we present one comparison-based sorting algorithm with optimal space and running time that is resilient to O((n log n)1/3) faults. We also prove polylogarithmic lower and upper bounds on fault-tolerant searching.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
