Lossless fault-tolerant data structures with additive overhead
12th International Symposium, WADS 2011, New York, NY, USA, August 15-17, 2011. Proceedings
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer Berlin / Heidelberg
2012
|
| Online Access: | http://hdl.handle.net/1721.1/73856 https://orcid.org/0000-0003-3803-5703 |
| _version_ | 1811082065566760960 |
|---|---|
| author | Christiano, Paul F. Demaine, Erik D. Kishore, Shaunak |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Christiano, Paul F. Demaine, Erik D. Kishore, Shaunak |
| author_sort | Christiano, Paul F. |
| collection | MIT |
| description | 12th International Symposium, WADS 2011, New York, NY, USA, August 15-17, 2011. Proceedings |
| first_indexed | 2024-09-23T11:57:01Z |
| format | Article |
| id | mit-1721.1/73856 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:57:01Z |
| publishDate | 2012 |
| publisher | Springer Berlin / Heidelberg |
| record_format | dspace |
| spelling | mit-1721.1/738562022-10-01T07:10:47Z Lossless fault-tolerant data structures with additive overhead Christiano, Paul F. Demaine, Erik D. Kishore, Shaunak Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Christiano, Paul F. Demaine, Erik D. Kishore, Shaunak 12th International Symposium, WADS 2011, New York, NY, USA, August 15-17, 2011. Proceedings We develop the first dynamic data structures that tolerate δ memory faults, lose no data, and incur only an O(δ ) additive overhead in overall space and time per operation. We obtain such data structures for arrays, linked lists, binary search trees, interval trees, predecessor search, and suffix trees. Like previous data structures, δ must be known in advance, but we show how to restore pristine state in linear time, in parallel with queries, making δ just a bound on the rate of memory faults. Our data structures require Θ(δ) words of safe memory during an operation, which may not be theoretically necessary but seems a practical assumption. Center for Massive Data Algorithmics (MADALGO) 2012-10-10T17:33:11Z 2012-10-10T17:33:11Z 2011-08 2011-08 Article http://purl.org/eprint/type/ConferencePaper 978-3-642-22299-3 0302-9743 1611-3349 http://hdl.handle.net/1721.1/73856 Christiano, Paul, Erik D. Demaine, and Shaunak Kishore. “Lossless Fault-Tolerant Data Structures with Additive Overhead.” Algorithms and Data Structures. Ed. Frank Dehne, John Iacono, & Jörg-Rüdiger Sack. LNCS Vol. 6844. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011. 243–254. https://orcid.org/0000-0003-3803-5703 en_US http://dx.doi.org/10.1007/978-3-642-22300-6_21 Algorithms and Data Structures Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Springer Berlin / Heidelberg MIT web domain |
| spellingShingle | Christiano, Paul F. Demaine, Erik D. Kishore, Shaunak Lossless fault-tolerant data structures with additive overhead |
| title | Lossless fault-tolerant data structures with additive overhead |
| title_full | Lossless fault-tolerant data structures with additive overhead |
| title_fullStr | Lossless fault-tolerant data structures with additive overhead |
| title_full_unstemmed | Lossless fault-tolerant data structures with additive overhead |
| title_short | Lossless fault-tolerant data structures with additive overhead |
| title_sort | lossless fault tolerant data structures with additive overhead |
| url | http://hdl.handle.net/1721.1/73856 https://orcid.org/0000-0003-3803-5703 |
| work_keys_str_mv | AT christianopaulf losslessfaulttolerantdatastructureswithadditiveoverhead AT demaineerikd losslessfaulttolerantdatastructureswithadditiveoverhead AT kishoreshaunak losslessfaulttolerantdatastructureswithadditiveoverhead |