{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,17]],"date-time":"2026-01-17T20:39:28Z","timestamp":1768682368496,"version":"3.49.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2009,12,1]],"date-time":"2009-12-01T00:00:00Z","timestamp":1259625600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2009,12]]},"abstract":"<jats:p>\n            We address the problem of designing data structures in the presence of faults that may arbitrarily corrupt memory locations. More precisely, we assume that an adaptive adversary can arbitrarily overwrite the content of up to \u03b4 memory locations, that corrupted locations cannot be detected, and that only\n            <jats:italic>O<\/jats:italic>\n            (1) memory locations are safe. In this framework, we call a data structure resilient if it is able to operate correctly (at least) on the set of uncorrupted values. We present a resilient dictionary, implementing search, insert, and delete operations. Our dictionary has\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            + \u03b4) expected amortized time per operation, and\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) space complexity, where\n            <jats:italic>n<\/jats:italic>\n            denotes the current number of keys in the dictionary. We also describe a deterministic resilient dictionary, with the same amortized cost per operation over a sequence of at least \u03b4\n            <jats:sup>\u03f5<\/jats:sup>\n            operations, where \u03f5 &gt; 0 is an arbitrary constant. Finally, we show that any resilient comparison-based dictionary must take \u03a9(log\n            <jats:italic>n<\/jats:italic>\n            + \u03b4) expected time per search. Our results are achieved by means of simple, new techniques which might be of independent interest for the design of other resilient algorithms.\n          <\/jats:p>","DOI":"10.1145\/1644015.1644016","type":"journal-article","created":{"date-parts":[[2010,8,24]],"date-time":"2010-08-24T13:16:40Z","timestamp":1282655800000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Resilient dictionaries"],"prefix":"10.1145","volume":"6","author":[{"given":"Irene","family":"Finocchi","sequence":"first","affiliation":[{"name":"Universit\u00e0 di Roma \u201cLa Sapienza\u201d, Roma, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fabrizio","family":"Grandoni","sequence":"additional","affiliation":[{"name":"Universit\u00e0 di Roma \u201cTor Vergata\u201d, Roma, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giuseppe F.","family":"Italiano","sequence":"additional","affiliation":[{"name":"Universit\u00e0 di Roma \u201cTor Vergata\u201d, Roma, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,12,28]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103469"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 37th IEEE Symposium on Foundations of Computer Science (FOCS'96)","author":"Aumann Y.","unstructured":"Aumann , Y. , and Bender , M. A . 1996. Fault-Tolerant data structures . In Proceedings of the 37th IEEE Symposium on Foundations of Computer Science (FOCS'96) . IEEE, 580--589. Aumann, Y., and Bender, M. A. 1996. Fault-Tolerant data structures. In Proceedings of the 37th IEEE Symposium on Foundations of Computer Science (FOCS'96). IEEE, 580--589."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288683"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01185212"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167129"},{"key":"e_1_2_1_6_1","unstructured":"Boyer R. and Moore S. 1982. Mjrty\u2014A fast majority vote algorithm. Tech. rep. University of Texas.  Boyer R. and Moore S. 1982. Mjrty\u2014A fast majority vote algorithm. Tech. rep. University of Texas."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 15th Annual European Symposium on Algorithms (ESA'07)","volume":"4698","author":"Brodal G. S.","unstructured":"Brodal , G. S. , Fagerberg , R. , Finocchi , I. , Grandoni , F. , Italiano , G. F. , J\u00f8rgensen , A. G. , Moruz , G. , and M\u00f8lhave , T . 2007. Optimal resilient dynamic dictionaries . In Proceedings of the 15th Annual European Symposium on Algorithms (ESA'07) . Lecture Notes in Computer Science , vol. 4698 . Springer, 347--358. Brodal, G. S., Fagerberg, R., Finocchi, I., Grandoni, F., Italiano, G. F., J\u00f8rgensen, A. G., Moruz, G., and M\u00f8lhave, T. 2007. Optimal resilient dynamic dictionaries. In Proceedings of the 15th Annual European Symposium on Algorithms (ESA'07). Lecture Notes in Computer Science, vol. 4698. Springer, 347--358."},{"key":"e_1_2_1_8_1","unstructured":"Cormen T. H. Leiserson C. E. Rivest R. L. and Stein C. 2001. Introduction to Algorithms 2nd Ed. The MIT Press\/McGraw-Hill Book Company.   Cormen T. H. Leiserson C. E. Rivest R. L. and Stein C. 2001. Introduction to Algorithms 2nd Ed. The MIT Press\/McGraw-Hill Book Company."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 3rd ACM-SIAM Symposium on Discrete Algorithms (SODA'92)","author":"Dhagat A.","unstructured":"Dhagat , A. , Gacs , P. , and Winkler , P. 1992. On playing \u201ctwenty questions\u201d with a liar . In Proceedings of the 3rd ACM-SIAM Symposium on Discrete Algorithms (SODA'92) . SIAM, 16--22. Dhagat, A., Gacs, P., and Winkler, P. 1992. On playing \u201ctwenty questions\u201d with a liar. In Proceedings of the 3rd ACM-SIAM Symposium on Discrete Algorithms (SODA'92). SIAM, 16--22."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791195877"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/11786986_26"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA'07)","author":"Finocchi I.","unstructured":"Finocchi , I. , Grandoni , F. , and Italiano , G. F . 2007. Resilient search trees . In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA'07) . SIAM, 547--555. Finocchi, I., Grandoni, F., and Italiano, G. F. 2007. Resilient search trees. In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA'07). SIAM, 547--555."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9088-4"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1978.3"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022802010738"},{"key":"e_1_2_1_16_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP'04)","author":"Henzinger M. R.","unstructured":"Henzinger , M. R. 2004. The past, present and future of Web search engines (invited talk) . In Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP'04) . Lecture Notes in Computer Science . Springer . Henzinger, M. R. 2004. The past, present and future of Web search engines (invited talk). In Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP'04). Lecture Notes in Computer Science. Springer."},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA'07)","author":"Henzinger M. R.","year":"2007","unstructured":"Henzinger , M. R. 2007 . Combinatorial algorithms for Web search engines\u2014Three success stories (invited talk) . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA'07) . SIAM. Henzinger, M. R. 2007. Combinatorial algorithms for Web search engines\u2014Three success stories (invited talk). In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA'07). SIAM."},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 10th Workshop on Algorithms and Data Structures (WADS'07)","author":"J\u00f8rgensen A. G.","unstructured":"J\u00f8rgensen , A. G. , Moruz , G. , and M\u00f8lhave , T . 2007. Priority queues resilient to memory faults . In Proceedings of the 10th Workshop on Algorithms and Data Structures (WADS'07) . Lecture Notes in Computer Science. Springer, 127--138. J\u00f8rgensen, A. G., Moruz, G., and M\u00f8lhave, T. 2007. Priority queues resilient to memory faults. In Proceedings of the 10th Workshop on Algorithms and Data Structures (WADS'07). Lecture Notes in Computer Science. Springer, 127--138."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90014-8"},{"key":"e_1_2_1_20_1","first-page":"263","article-title":"An algorithm for the organization of information","volume":"146","author":"Landis G. M. A.-V. Y. M.","year":"1962","unstructured":"Landis , G. M. A.-V. Y. M. 1962 . An algorithm for the organization of information . Dokl. Akad. Nauk. Sssr 146 , 263 -- 266 . Landis, G. M. A.-V. Y. M. 1962. An algorithm for the organization of information. Dokl. Akad. Nauk. Sssr 146, 263--266.","journal-title":"Dokl. Akad. Nauk. Sssr"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/T-ED.1979.19370"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 5th ACM-SIAM Symposium on Discrete Algorithms (SODA'94)","author":"Muthukrishnan S.","year":"1994","unstructured":"Muthukrishnan , S. 1994 . On optimal strategies for searching in the presence of errors . In Proceedings of the 5th ACM-SIAM Symposium on Discrete Algorithms (SODA'94) . SIAM, 680--689. Muthukrishnan, S. 1994. On optimal strategies for searching in the presence of errors. In Proceedings of the 5th ACM-SIAM Symposium on Discrete Algorithms (SODA'94). SIAM, 680--689."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(89)90077-7"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00303-6"},{"key":"e_1_2_1_25_1","volume-title":"Princeton","author":"von Neumann J.","unstructured":"von Neumann , J. 1956. Probabilistic logics and the synthesis of reliable organisms from unreliable components . In Automata Studies, C. Shannon and J. McCarty, Eds. Princeton University Press , 43--98. von Neumann, J. 1956. Probabilistic logics and the synthesis of reliable organisms from unreliable components. In Automata Studies, C. Shannon and J. McCarty, Eds. Princeton University Press, 43--98."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1644015.1644016","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1644015.1644016","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:26:44Z","timestamp":1750278404000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1644015.1644016"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,12]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,12]]}},"alternative-id":["10.1145\/1644015.1644016"],"URL":"https:\/\/doi.org\/10.1145\/1644015.1644016","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,12]]},"assertion":[{"value":"2007-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-12-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}