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