[{"conference":{"name":"20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)","start_date":"2018-11-04","end_date":"2018-11-07","location":"Tokyo"},"doi":"10.1007/978-3-030-03232-6_1","volume":11201,"author":[{"first_name":"Till","id":"39241","full_name":"Knollmann, Till","orcid":"0000-0003-2014-4696","last_name":"Knollmann"},{"id":"20792","full_name":"Scheideler, Christian","last_name":"Scheideler","first_name":"Christian"}],"date_updated":"2022-01-06T07:01:02Z","intvolume":"     11201","citation":{"apa":"Knollmann, T., &#38; Scheideler, C. (2018). A Self-Stabilizing Hashed Patricia Trie. In T. Izumi &#38; P. Kuznetsov (Eds.), <i>Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)</i> (Vol. 11201). Tokyo: Springer, Cham. <a href=\"https://doi.org/10.1007/978-3-030-03232-6_1\">https://doi.org/10.1007/978-3-030-03232-6_1</a>","mla":"Knollmann, Till, and Christian Scheideler. “A Self-Stabilizing Hashed Patricia Trie.” <i>Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)</i>, edited by Taisuke Izumi and Petr Kuznetsov, vol. 11201, Springer, Cham, 2018, doi:<a href=\"https://doi.org/10.1007/978-3-030-03232-6_1\">10.1007/978-3-030-03232-6_1</a>.","short":"T. Knollmann, C. Scheideler, in: T. Izumi, P. Kuznetsov (Eds.), Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), Springer, Cham, 2018.","bibtex":"@inproceedings{Knollmann_Scheideler_2018, series={Lecture Notes of Computer Science}, title={A Self-Stabilizing Hashed Patricia Trie}, volume={11201}, DOI={<a href=\"https://doi.org/10.1007/978-3-030-03232-6_1\">10.1007/978-3-030-03232-6_1</a>}, booktitle={Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)}, publisher={Springer, Cham}, author={Knollmann, Till and Scheideler, Christian}, editor={Izumi, Taisuke and Kuznetsov, PetrEditors}, year={2018}, collection={Lecture Notes of Computer Science} }","chicago":"Knollmann, Till, and Christian Scheideler. “A Self-Stabilizing Hashed Patricia Trie.” In <i>Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)</i>, edited by Taisuke Izumi and Petr Kuznetsov, Vol. 11201. Lecture Notes of Computer Science. Springer, Cham, 2018. <a href=\"https://doi.org/10.1007/978-3-030-03232-6_1\">https://doi.org/10.1007/978-3-030-03232-6_1</a>.","ieee":"T. Knollmann and C. Scheideler, “A Self-Stabilizing Hashed Patricia Trie,” in <i>Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)</i>, Tokyo, 2018, vol. 11201.","ama":"Knollmann T, Scheideler C. A Self-Stabilizing Hashed Patricia Trie. In: Izumi T, Kuznetsov P, eds. <i>Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)</i>. Vol 11201. Lecture Notes of Computer Science. Springer, Cham; 2018. doi:<a href=\"https://doi.org/10.1007/978-3-030-03232-6_1\">10.1007/978-3-030-03232-6_1</a>"},"has_accepted_license":"1","file_date_updated":"2018-11-02T14:38:37Z","department":[{"_id":"63"},{"_id":"79"}],"user_id":"39241","series_title":"Lecture Notes of Computer Science","_id":"4411","project":[{"_id":"1","name":"SFB 901"},{"_id":"2","name":"SFB 901 - Project Area A"},{"_id":"5","name":"SFB 901 - Subproject A1"}],"status":"public","editor":[{"first_name":"Taisuke","full_name":"Izumi, Taisuke","last_name":"Izumi"},{"full_name":"Kuznetsov, Petr","last_name":"Kuznetsov","first_name":"Petr"}],"type":"conference","title":"A Self-Stabilizing Hashed Patricia Trie","date_created":"2018-09-17T13:12:18Z","publisher":"Springer, Cham","year":"2018","language":[{"iso":"eng"}],"keyword":["Self-Stabilizing","Prefix Search","Distributed Data Structure"],"ddc":["000"],"external_id":{"arxiv":["1809.04923"]},"file":[{"content_type":"application/pdf","relation":"main_file","success":1,"creator":"ups","date_created":"2018-11-02T14:38:37Z","date_updated":"2018-11-02T14:38:37Z","file_id":"5277","access_level":"closed","file_name":"ASelf-stabilizingHashedPatrici.pdf","file_size":500005}],"abstract":[{"text":"While a lot of research in distributed computing has covered solutions for self-stabilizing computing and topologies, there is far less work on self-stabilization for distributed data structures.\r\nConsidering crashing peers in peer-to-peer networks, it should not be taken for granted that a distributed data structure remains intact.\r\nIn this work, we present a self-stabilizing protocol for a distributed data structure called the hashed Patricia Trie (Kniesburges and Scheideler WALCOM'11) that enables efficient prefix search on a set of keys.\r\nThe data structure has a wide area of applications including string matching problems while offering low overhead and efficient operations when embedded on top of a distributed hash table.\r\nEspecially, longest prefix matching for $x$ can be done in $\\mathcal{O}(\\log |x|)$ hash table read accesses.\r\nWe show how to maintain the structure in a self-stabilizing way.\r\nOur protocol assures low overhead in a legal state and a total (asymptotically optimal) memory demand of $\\Theta(d)$ bits, where $d$ is the number of bits needed for storing all keys.","lang":"eng"}],"publication":"Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)"}]