[{"_id":"4411","project":[{"_id":"1","name":"SFB 901"},{"name":"SFB 901 - Project Area A","_id":"2"},{"_id":"5","name":"SFB 901 - Subproject A1"}],"department":[{"_id":"63"},{"_id":"79"}],"series_title":"Lecture Notes of Computer Science","user_id":"39241","file_date_updated":"2018-11-02T14:38:37Z","type":"conference","editor":[{"first_name":"Taisuke","full_name":"Izumi, Taisuke","last_name":"Izumi"},{"first_name":"Petr","full_name":"Kuznetsov, Petr","last_name":"Kuznetsov"}],"status":"public","date_updated":"2022-01-06T07:01:02Z","volume":11201,"author":[{"id":"39241","full_name":"Knollmann, Till","orcid":"0000-0003-2014-4696","last_name":"Knollmann","first_name":"Till"},{"first_name":"Christian","last_name":"Scheideler","id":"20792","full_name":"Scheideler, Christian"}],"doi":"10.1007/978-3-030-03232-6_1","conference":{"end_date":"2018-11-07","location":"Tokyo","name":"20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)","start_date":"2018-11-04"},"has_accepted_license":"1","intvolume":"     11201","citation":{"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>","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.","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} }","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>"},"external_id":{"arxiv":["1809.04923"]},"keyword":["Self-Stabilizing","Prefix Search","Distributed Data Structure"],"ddc":["000"],"language":[{"iso":"eng"}],"publication":"Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)","abstract":[{"lang":"eng","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."}],"file":[{"file_size":500005,"access_level":"closed","file_id":"5277","file_name":"ASelf-stabilizingHashedPatrici.pdf","date_updated":"2018-11-02T14:38:37Z","date_created":"2018-11-02T14:38:37Z","creator":"ups","success":1,"relation":"main_file","content_type":"application/pdf"}],"publisher":"Springer, Cham","date_created":"2018-09-17T13:12:18Z","title":"A Self-Stabilizing Hashed Patricia Trie","year":"2018"}]