Academic Journal
Optimal resilient sorting and searching in the presence of memory faults
| العنوان: | Optimal resilient sorting and searching in the presence of memory faults |
|---|---|
| المؤلفون: | Irene Finocchi, Fabrizio Grandoni |
| المساهمون: | The Pennsylvania State University CiteSeerX Archives |
| المصدر: | http://www.disp.uniroma2.it/users/grandoni/pubblicazioni/fgi09tcs.pdf. |
| سنة النشر: | 2006 |
| المجموعة: | CiteSeerX |
| مصطلحات موضوعية: | computing with |
| الوصف: | We investigate the problem of reliable computation in the presence of faults that may arbitrarily corrupt memory locations. In this framework, we consider the problems of sorting and searching in optimal time while tolerating the largest possible number of memory faults. In particular, we design an O(n log n) time sorting algorithm that can optimally tolerate up to O( p n log n) memory faults. In the special case of integer sorting, we present an algorithm with linear expected running time that can tolerate O( p n) faults. We also present a randomized searching algorithm that can optimally tolerate up to O(log n) memory faults in O(log n) expected time, and an almost optimal deterministic searching algorithm that can tolerate O((log n)1) faults, for any small positive constant , in O(log n) worst-case time. All these results improve over previous bounds. |
| نوع الوثيقة: | text |
| وصف الملف: | application/pdf |
| اللغة: | English |
| Relation: | http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.545.9957; http://www.disp.uniroma2.it/users/grandoni/pubblicazioni/fgi09tcs.pdf |
| الاتاحة: | http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.545.9957 http://www.disp.uniroma2.it/users/grandoni/pubblicazioni/fgi09tcs.pdf |
| Rights: | Metadata may be used without restrictions as long as the oai identifier remains attached to it. |
| رقم الانضمام: | edsbas.D2EC46C1 |
| قاعدة البيانات: | BASE |
| الوصف غير متاح. |