[{"citation":{"ama":"Graffi K, Benter M, Divband M, Kniesburges S, Koutsopoulos A. Ca-Re-Chord: A Churn Resistant Self-stabilizing Chord Overlay Network. In: <i>Proceedings of the Conference on Networked Systems (NetSys)</i>. ; 2013:27-34. doi:<a href=\"https://doi.org/10.1109/NetSys.2013.11\">10.1109/NetSys.2013.11</a>","chicago":"Graffi, Kalman, Markus Benter, Mohammad Divband, Sebastian Kniesburges, and Andreas Koutsopoulos. “Ca-Re-Chord: A Churn Resistant Self-Stabilizing Chord Overlay Network.” In <i>Proceedings of the Conference on Networked Systems (NetSys)</i>, 27–34, 2013. <a href=\"https://doi.org/10.1109/NetSys.2013.11\">https://doi.org/10.1109/NetSys.2013.11</a>.","ieee":"K. Graffi, M. Benter, M. Divband, S. Kniesburges, and A. Koutsopoulos, “Ca-Re-Chord: A Churn Resistant Self-stabilizing Chord Overlay Network,” in <i>Proceedings of the Conference on Networked Systems (NetSys)</i>, 2013, pp. 27–34.","mla":"Graffi, Kalman, et al. “Ca-Re-Chord: A Churn Resistant Self-Stabilizing Chord Overlay Network.” <i>Proceedings of the Conference on Networked Systems (NetSys)</i>, 2013, pp. 27–34, doi:<a href=\"https://doi.org/10.1109/NetSys.2013.11\">10.1109/NetSys.2013.11</a>.","short":"K. Graffi, M. Benter, M. Divband, S. Kniesburges, A. Koutsopoulos, in: Proceedings of the Conference on Networked Systems (NetSys), 2013, pp. 27–34.","bibtex":"@inproceedings{Graffi_Benter_Divband_Kniesburges_Koutsopoulos_2013, title={Ca-Re-Chord: A Churn Resistant Self-stabilizing Chord Overlay Network}, DOI={<a href=\"https://doi.org/10.1109/NetSys.2013.11\">10.1109/NetSys.2013.11</a>}, booktitle={Proceedings of the Conference on Networked Systems (NetSys)}, author={Graffi, Kalman and Benter, Markus and Divband, Mohammad and Kniesburges, Sebastian and Koutsopoulos, Andreas}, year={2013}, pages={27–34} }","apa":"Graffi, K., Benter, M., Divband, M., Kniesburges, S., &#38; Koutsopoulos, A. (2013). Ca-Re-Chord: A Churn Resistant Self-stabilizing Chord Overlay Network. In <i>Proceedings of the Conference on Networked Systems (NetSys)</i> (pp. 27–34). <a href=\"https://doi.org/10.1109/NetSys.2013.11\">https://doi.org/10.1109/NetSys.2013.11</a>"},"page":"27-34","year":"2013","has_accepted_license":"1","doi":"10.1109/NetSys.2013.11","title":"Ca-Re-Chord: A Churn Resistant Self-stabilizing Chord Overlay Network","author":[{"first_name":"Kalman","last_name":"Graffi","full_name":"Graffi, Kalman"},{"first_name":"Markus","last_name":"Benter","full_name":"Benter, Markus"},{"first_name":"Mohammad","last_name":"Divband","full_name":"Divband, Mohammad"},{"last_name":"Kniesburges","full_name":"Kniesburges, Sebastian","first_name":"Sebastian"},{"last_name":"Koutsopoulos","full_name":"Koutsopoulos, Andreas","first_name":"Andreas"}],"date_created":"2017-10-17T12:42:38Z","date_updated":"2022-01-06T07:01:55Z","file":[{"date_updated":"2018-03-15T10:30:42Z","creator":"florida","date_created":"2018-03-15T10:30:42Z","file_size":244841,"file_name":"546-Kalman.Graffi_CaReChord.A.Churn.Resistant.Selfstabilizing.Chord.Overlay.Network_02.pdf","file_id":"1286","access_level":"closed","content_type":"application/pdf","success":1,"relation":"main_file"}],"status":"public","abstract":[{"lang":"eng","text":"Self-stabilization is the property of a system to transfer itself regardless of the initial state into a legitimate state. Chord as a simple, decentralized and scalable distributed hash table is an ideal showcase to introduce self-stabilization for p2p overlays. In this paper, we present Re-Chord, a self-stabilizing version of Chord. We show, that the stabilization process is functional, but prone to strong churn. For that, we present Ca-Re-Chord, a churn resistant version of Re-Chord, that allows the creation of a useful DHT in any kind of graph regardless of the initial state. Simulation results attest the churn resistance and good performance of Ca-Re-Chord."}],"type":"conference","publication":"Proceedings of the Conference on Networked Systems (NetSys)","file_date_updated":"2018-03-15T10:30:42Z","ddc":["040"],"user_id":"15504","department":[{"_id":"79"}],"project":[{"name":"SFB 901","_id":"1"},{"name":"SFB 901 - Subprojekt A1","_id":"5"},{"_id":"13","name":"SFB 901 - Subproject C1"},{"_id":"2","name":"SFB 901 - Project Area A"},{"name":"SFB 901 - Project Area C","_id":"4"}],"_id":"546"},{"publication":"Proceedings of the International Conference on Peer-to-Peer Computing (P2P'13)","type":"conference","abstract":[{"text":"Peer-to-peer systems scale to millions of nodes and provide routing and storage functions with best effort quality. In order to provide a guaranteed quality of the overlay functions, even under strong dynamics in the network with regard to peer capacities, online participation and usage patterns, we propose to calibrate the peer-to-peer overlay and to autonomously learn which qualities can be reached. For that, we simulate the peer-to-peer overlay systematically under a wide range of parameter configurations and use neural networks to learn the effects of the configurations on the quality metrics. Thus, by choosing a specific quality setting by the overlay operator, the network can tune itself to the learned parameter configurations that lead to the desired quality. Evaluation shows that the presented self-calibration succeeds in learning the configuration-quality interdependencies and that peer-to-peer systems can learn and adapt their behavior according to desired quality goals.","lang":"eng"}],"status":"public","file":[{"file_size":629234,"file_name":"548-Bootstrapping.Skynet.Calibration.and.Autonomic.Self-Control.of.Structured.P2P.Networks_01.pdf","file_id":"1285","access_level":"closed","date_updated":"2018-03-15T10:30:09Z","date_created":"2018-03-15T10:30:09Z","creator":"florida","success":1,"relation":"main_file","content_type":"application/pdf"}],"_id":"548","project":[{"_id":"1","name":"SFB 901"},{"_id":"5","name":"SFB 901 - Subprojekt A1"},{"name":"SFB 901 - Project Area A","_id":"2"}],"department":[{"_id":"79"}],"user_id":"477","ddc":["040"],"language":[{"iso":"eng"}],"file_date_updated":"2018-03-15T10:30:09Z","has_accepted_license":"1","year":"2013","page":"1-5","citation":{"apa":"Graffi, K., &#38; Klerx, T. (2013). Bootstrapping Skynet: Calibration and Autonomic Self-Control of Structured Peer-to-Peer Networks. In <i>Proceedings of the International Conference on Peer-to-Peer Computing (P2P’13)</i> (pp. 1–5). <a href=\"https://doi.org/10.1109/P2P.2013.6688720\">https://doi.org/10.1109/P2P.2013.6688720</a>","short":"K. Graffi, T. Klerx, in: Proceedings of the International Conference on Peer-to-Peer Computing (P2P’13), 2013, pp. 1–5.","bibtex":"@inproceedings{Graffi_Klerx_2013, title={Bootstrapping Skynet: Calibration and Autonomic Self-Control of Structured Peer-to-Peer Networks}, DOI={<a href=\"https://doi.org/10.1109/P2P.2013.6688720\">10.1109/P2P.2013.6688720</a>}, booktitle={Proceedings of the International Conference on Peer-to-Peer Computing (P2P’13)}, author={Graffi, Kalman and Klerx, Timo}, year={2013}, pages={1–5} }","mla":"Graffi, Kalman, and Timo Klerx. “Bootstrapping Skynet: Calibration and Autonomic Self-Control of Structured Peer-to-Peer Networks.” <i>Proceedings of the International Conference on Peer-to-Peer Computing (P2P’13)</i>, 2013, pp. 1–5, doi:<a href=\"https://doi.org/10.1109/P2P.2013.6688720\">10.1109/P2P.2013.6688720</a>.","ama":"Graffi K, Klerx T. Bootstrapping Skynet: Calibration and Autonomic Self-Control of Structured Peer-to-Peer Networks. In: <i>Proceedings of the International Conference on Peer-to-Peer Computing (P2P’13)</i>. ; 2013:1-5. doi:<a href=\"https://doi.org/10.1109/P2P.2013.6688720\">10.1109/P2P.2013.6688720</a>","ieee":"K. Graffi and T. Klerx, “Bootstrapping Skynet: Calibration and Autonomic Self-Control of Structured Peer-to-Peer Networks,” in <i>Proceedings of the International Conference on Peer-to-Peer Computing (P2P’13)</i>, 2013, pp. 1–5.","chicago":"Graffi, Kalman, and Timo Klerx. “Bootstrapping Skynet: Calibration and Autonomic Self-Control of Structured Peer-to-Peer Networks.” In <i>Proceedings of the International Conference on Peer-to-Peer Computing (P2P’13)</i>, 1–5, 2013. <a href=\"https://doi.org/10.1109/P2P.2013.6688720\">https://doi.org/10.1109/P2P.2013.6688720</a>."},"date_updated":"2022-01-06T07:01:56Z","date_created":"2017-10-17T12:42:39Z","author":[{"last_name":"Graffi","full_name":"Graffi, Kalman","first_name":"Kalman"},{"full_name":"Klerx, Timo","last_name":"Klerx","first_name":"Timo"}],"title":"Bootstrapping Skynet: Calibration and Autonomic Self-Control of Structured Peer-to-Peer Networks","doi":"10.1109/P2P.2013.6688720"},{"citation":{"apa":"Setzer, A. (2013). <i>Approximation Algorithms for the Linear Arrangement of Special Classes of Graphs</i>. Universität Paderborn.","mla":"Setzer, Alexander. <i>Approximation Algorithms for the Linear Arrangement of Special Classes of Graphs</i>. Universität Paderborn, 2013.","bibtex":"@book{Setzer_2013, title={Approximation Algorithms for the Linear Arrangement of Special Classes of Graphs}, publisher={Universität Paderborn}, author={Setzer, Alexander}, year={2013} }","short":"A. Setzer, Approximation Algorithms for the Linear Arrangement of Special Classes of Graphs, Universität Paderborn, 2013.","ieee":"A. Setzer, <i>Approximation Algorithms for the Linear Arrangement of Special Classes of Graphs</i>. Universität Paderborn, 2013.","chicago":"Setzer, Alexander. <i>Approximation Algorithms for the Linear Arrangement of Special Classes of Graphs</i>. Universität Paderborn, 2013.","ama":"Setzer A. <i>Approximation Algorithms for the Linear Arrangement of Special Classes of Graphs</i>. Universität Paderborn; 2013."},"year":"2013","author":[{"first_name":"Alexander","last_name":"Setzer","full_name":"Setzer, Alexander","id":"11108"}],"date_created":"2017-10-17T12:42:40Z","publisher":"Universität Paderborn","date_updated":"2022-01-06T07:01:59Z","title":"Approximation Algorithms for the Linear Arrangement of Special Classes of Graphs","type":"mastersthesis","status":"public","user_id":"477","department":[{"_id":"79"}],"project":[{"_id":"1","name":"SFB 901"},{"name":"SFB 901 - Subprojekt A1","_id":"5"},{"name":"SFB 901 - Project Area A","_id":"2"}],"_id":"555"},{"type":"conference_editor","editor":[{"full_name":"Flocchini, Paola","last_name":"Flocchini","first_name":"Paola"},{"full_name":"Gao, Jie","last_name":"Gao","first_name":"Jie"},{"last_name":"Kranakis","full_name":"Kranakis, Evangelos","first_name":"Evangelos"},{"last_name":"Meyer auf der Heide","full_name":"Meyer auf der Heide, Friedhelm","id":"15523","first_name":"Friedhelm"}],"status":"public","_id":"558","project":[{"_id":"1","name":"SFB 901"},{"name":"SFB 901 - Subprojekt A1","_id":"5"},{"name":"SFB 901 - Project Area A","_id":"2"}],"department":[{"_id":"63"}],"user_id":"477","series_title":"LNCS","file_date_updated":"2018-11-02T16:29:07Z","has_accepted_license":"1","intvolume":"      8243","citation":{"ama":"Flocchini P, Gao J, Kranakis E, Meyer auf der Heide F, eds. <i>Algorithms for Sensor Systems - 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics</i>. Vol 8243. Springer; 2013. doi:<a href=\"https://doi.org/10.1007/978-3-642-45346-5\">10.1007/978-3-642-45346-5</a>","ieee":"P. Flocchini, J. Gao, E. Kranakis, and F. Meyer auf der Heide, Eds., <i>Algorithms for Sensor Systems - 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics</i>, vol. 8243. Springer, 2013.","chicago":"Flocchini, Paola, Jie Gao, Evangelos Kranakis, and Friedhelm Meyer auf der Heide, eds. <i>Algorithms for Sensor Systems - 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics</i>. Vol. 8243. LNCS. Springer, 2013. <a href=\"https://doi.org/10.1007/978-3-642-45346-5\">https://doi.org/10.1007/978-3-642-45346-5</a>.","bibtex":"@book{Flocchini_Gao_Kranakis_Meyer auf der Heide_2013, series={LNCS}, title={Algorithms for Sensor Systems - 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics}, volume={8243}, DOI={<a href=\"https://doi.org/10.1007/978-3-642-45346-5\">10.1007/978-3-642-45346-5</a>}, publisher={Springer}, year={2013}, collection={LNCS} }","short":"P. Flocchini, J. Gao, E. Kranakis, F. Meyer auf der Heide, eds., Algorithms for Sensor Systems - 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, Springer, 2013.","mla":"Flocchini, Paola, et al., editors. <i>Algorithms for Sensor Systems - 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics</i>. Vol. 8243, Springer, 2013, doi:<a href=\"https://doi.org/10.1007/978-3-642-45346-5\">10.1007/978-3-642-45346-5</a>.","apa":"Flocchini, P., Gao, J., Kranakis, E., &#38; Meyer auf der Heide, F. (Eds.). (2013). <i>Algorithms for Sensor Systems - 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics</i> (Vol. 8243). Presented at the ALGOSENSORS 2013, Sophia Antipolis, France: Springer. <a href=\"https://doi.org/10.1007/978-3-642-45346-5\">https://doi.org/10.1007/978-3-642-45346-5</a>"},"date_updated":"2022-01-06T07:02:02Z","volume":8243,"conference":{"end_date":"2013-09-06","location":"Sophia Antipolis, France","name":"ALGOSENSORS 2013","start_date":"2013-09-05"},"doi":"10.1007/978-3-642-45346-5","file":[{"date_created":"2018-11-02T16:29:07Z","creator":"ups","date_updated":"2018-11-02T16:29:07Z","access_level":"closed","file_id":"5327","file_name":"2014_Book_AlgorithmsForSensorSystems-1.pdf","file_size":9186107,"content_type":"application/pdf","relation":"main_file","success":1}],"ddc":["000"],"language":[{"iso":"eng"}],"year":"2013","publisher":"Springer","date_created":"2017-10-17T12:42:41Z","title":"Algorithms for Sensor Systems - 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics"},{"date_updated":"2022-01-06T07:02:04Z","author":[{"first_name":"Philip","full_name":"Wette, Philip","last_name":"Wette"},{"last_name":"Graffi","full_name":"Graffi, Kalman","first_name":"Kalman"}],"date_created":"2017-10-17T12:42:41Z","title":"Adding Capacity-Aware Storage Indirection to Homogeneous Distributed Hash Tables","doi":"10.1109/NetSys.2013.9","has_accepted_license":"1","year":"2013","page":"35-42","citation":{"apa":"Wette, P., &#38; Graffi, K. (2013). Adding Capacity-Aware Storage Indirection to Homogeneous Distributed Hash Tables. In <i>Proceedings of the Conference on Networked Systems (NetSys)</i> (pp. 35–42). <a href=\"https://doi.org/10.1109/NetSys.2013.9\">https://doi.org/10.1109/NetSys.2013.9</a>","short":"P. Wette, K. Graffi, in: Proceedings of the Conference on Networked Systems (NetSys), 2013, pp. 35–42.","bibtex":"@inproceedings{Wette_Graffi_2013, title={Adding Capacity-Aware Storage Indirection to Homogeneous Distributed Hash Tables}, DOI={<a href=\"https://doi.org/10.1109/NetSys.2013.9\">10.1109/NetSys.2013.9</a>}, booktitle={Proceedings of the Conference on Networked Systems (NetSys)}, author={Wette, Philip and Graffi, Kalman}, year={2013}, pages={35–42} }","mla":"Wette, Philip, and Kalman Graffi. “Adding Capacity-Aware Storage Indirection to Homogeneous Distributed Hash Tables.” <i>Proceedings of the Conference on Networked Systems (NetSys)</i>, 2013, pp. 35–42, doi:<a href=\"https://doi.org/10.1109/NetSys.2013.9\">10.1109/NetSys.2013.9</a>.","chicago":"Wette, Philip, and Kalman Graffi. “Adding Capacity-Aware Storage Indirection to Homogeneous Distributed Hash Tables.” In <i>Proceedings of the Conference on Networked Systems (NetSys)</i>, 35–42, 2013. <a href=\"https://doi.org/10.1109/NetSys.2013.9\">https://doi.org/10.1109/NetSys.2013.9</a>.","ieee":"P. Wette and K. Graffi, “Adding Capacity-Aware Storage Indirection to Homogeneous Distributed Hash Tables,” in <i>Proceedings of the Conference on Networked Systems (NetSys)</i>, 2013, pp. 35–42.","ama":"Wette P, Graffi K. Adding Capacity-Aware Storage Indirection to Homogeneous Distributed Hash Tables. In: <i>Proceedings of the Conference on Networked Systems (NetSys)</i>. ; 2013:35-42. doi:<a href=\"https://doi.org/10.1109/NetSys.2013.9\">10.1109/NetSys.2013.9</a>"},"_id":"559","project":[{"name":"SFB 901","_id":"1"},{"_id":"5","name":"SFB 901 - Subprojekt A1"},{"_id":"2","name":"SFB 901 - Project Area A"}],"department":[{"_id":"79"}],"user_id":"477","ddc":["040"],"language":[{"iso":"eng"}],"file_date_updated":"2018-03-15T10:27:21Z","publication":"Proceedings of the Conference on Networked Systems (NetSys)","type":"conference","abstract":[{"lang":"eng","text":"Distributed hash tables are very versatile to use, as distributed storage is a desirable feature for various applications. Typical structured overlays like Chord, Pastry or Kademlia consider only homogeneous nodes with equal capacities, which does not resemble reality. In a practical use case, nodes might get overloaded by storing popular data. In this paper, we present a general approach to enable capacity awareness and load-balancing capability of homogeneous structured overlays. We introduce a hierarchical second structured overlay aside, which allows efficient capacity-based access on the nodes in the system as hosting mirrors. Simulation results show that the structured overlay is able to store various contents, such as of a social network, with only a negligible number of overloaded peers. Content, even if very popular, is hosted by easily findable capable peers. Thus, long-existing and well-evaluated overlays like Chord or Pastry can be used to create attractive DHT-based applications."}],"status":"public","file":[{"file_name":"559-Adding.Capacity.Aware.Storage.Indirection.to.Homogeneous.Distributed.Hash.Tables.pdf","file_id":"1282","access_level":"closed","file_size":734618,"creator":"florida","date_created":"2018-03-15T10:27:21Z","date_updated":"2018-03-15T10:27:21Z","relation":"main_file","success":1,"content_type":"application/pdf"}]},{"department":[{"_id":"75"},{"_id":"63"}],"user_id":"477","_id":"562","project":[{"name":"SFB 901","_id":"1"},{"name":"SFB 901 - Subprojekt A2","_id":"6"},{"_id":"5","name":"SFB 901 - Subproject A1"},{"name":"SFB 901 - Project Area A","_id":"2"}],"file_date_updated":"2018-03-15T10:25:45Z","language":[{"iso":"eng"}],"ddc":["040"],"publication":"Proceedings of the 6th International Conference on Utility and Cloud Computing (UCC) workshop on Distributed cloud computing","type":"conference","status":"public","file":[{"relation":"main_file","success":1,"content_type":"application/pdf","file_id":"1279","access_level":"closed","file_name":"562-dcc13_paper.pdf","file_size":347873,"creator":"florida","date_created":"2018-03-15T10:25:45Z","date_updated":"2018-03-15T10:25:45Z"}],"abstract":[{"text":"In Distributed Cloud Computing, applications are deployed across many data centres at topologically diverse locations to improved network-related quality of service (QoS). As we focus on interactive applications, we minimize the latency between users and an application by allocating Cloud resources nearby the customers. Allocating resources at all locations will result in the best latency but also in the highest expenses. So we need to find an optimal subset of locations which reduces the latency but also the expenses – the facility location problem (FLP). In addition, we consider resource capacity restrictions, as a resource can only serve a limited amount of users. An FLP can be globally solved. Additionally, we propose a local, distributed heuristic. This heuristic is running within the network and does not depend on a global component. No distributed, local approximations for the capacitated FLP have been proposed so far due to the complexity of the problem. We compared the heuristic with an optimal solution obtained from a mixed integer program for different network topologies. We investigated the influence of different parameters like overall resource utilization or different latency weights.","lang":"eng"}],"author":[{"last_name":"Keller","full_name":"Keller, Matthias","first_name":"Matthias"},{"first_name":"Stefan","full_name":"Pawlik, Stefan","last_name":"Pawlik"},{"first_name":"Peter","full_name":"Pietrzyk, Peter","last_name":"Pietrzyk"},{"first_name":"Holger","id":"126","full_name":"Karl, Holger","last_name":"Karl"}],"date_created":"2017-10-17T12:42:41Z","date_updated":"2022-01-06T07:02:11Z","doi":"10.1109/UCC.2013.85","title":"A Local Heuristic for Latency-Optimized Distributed Cloud Deployment","has_accepted_license":"1","page":"429-434","citation":{"apa":"Keller, M., Pawlik, S., Pietrzyk, P., &#38; Karl, H. (2013). A Local Heuristic for Latency-Optimized Distributed Cloud Deployment. In <i>Proceedings of the 6th International Conference on Utility and Cloud Computing (UCC) workshop on Distributed cloud computing</i> (pp. 429–434). <a href=\"https://doi.org/10.1109/UCC.2013.85\">https://doi.org/10.1109/UCC.2013.85</a>","short":"M. Keller, S. Pawlik, P. Pietrzyk, H. Karl, in: Proceedings of the 6th International Conference on Utility and Cloud Computing (UCC) Workshop on Distributed Cloud Computing, 2013, pp. 429–434.","mla":"Keller, Matthias, et al. “A Local Heuristic for Latency-Optimized Distributed Cloud Deployment.” <i>Proceedings of the 6th International Conference on Utility and Cloud Computing (UCC) Workshop on Distributed Cloud Computing</i>, 2013, pp. 429–34, doi:<a href=\"https://doi.org/10.1109/UCC.2013.85\">10.1109/UCC.2013.85</a>.","bibtex":"@inproceedings{Keller_Pawlik_Pietrzyk_Karl_2013, title={A Local Heuristic for Latency-Optimized Distributed Cloud Deployment}, DOI={<a href=\"https://doi.org/10.1109/UCC.2013.85\">10.1109/UCC.2013.85</a>}, booktitle={Proceedings of the 6th International Conference on Utility and Cloud Computing (UCC) workshop on Distributed cloud computing}, author={Keller, Matthias and Pawlik, Stefan and Pietrzyk, Peter and Karl, Holger}, year={2013}, pages={429–434} }","ama":"Keller M, Pawlik S, Pietrzyk P, Karl H. A Local Heuristic for Latency-Optimized Distributed Cloud Deployment. In: <i>Proceedings of the 6th International Conference on Utility and Cloud Computing (UCC) Workshop on Distributed Cloud Computing</i>. ; 2013:429-434. doi:<a href=\"https://doi.org/10.1109/UCC.2013.85\">10.1109/UCC.2013.85</a>","chicago":"Keller, Matthias, Stefan Pawlik, Peter Pietrzyk, and Holger Karl. “A Local Heuristic for Latency-Optimized Distributed Cloud Deployment.” In <i>Proceedings of the 6th International Conference on Utility and Cloud Computing (UCC) Workshop on Distributed Cloud Computing</i>, 429–34, 2013. <a href=\"https://doi.org/10.1109/UCC.2013.85\">https://doi.org/10.1109/UCC.2013.85</a>.","ieee":"M. Keller, S. Pawlik, P. Pietrzyk, and H. Karl, “A Local Heuristic for Latency-Optimized Distributed Cloud Deployment,” in <i>Proceedings of the 6th International Conference on Utility and Cloud Computing (UCC) workshop on Distributed cloud computing</i>, 2013, pp. 429–434."},"year":"2013"},{"file_date_updated":"2018-03-15T10:25:15Z","ddc":["040"],"user_id":"477","series_title":"LNCS","department":[{"_id":"63"}],"project":[{"name":"SFB 901","_id":"1"},{"name":"SFB 901 - Subprojekt A1","_id":"5"},{"name":"SFB 901 - Project Area A","_id":"2"}],"_id":"563","file":[{"content_type":"application/pdf","relation":"main_file","success":1,"creator":"florida","date_created":"2018-03-15T10:25:15Z","date_updated":"2018-03-15T10:25:15Z","file_id":"1278","file_name":"563-978-3-642-45346-5_16.pdf","access_level":"closed","file_size":348191}],"status":"public","abstract":[{"lang":"eng","text":"Dominating set based virtual backbones are used for rou-ting in wireless ad-hoc networks. Such backbones receive and transmit messages from/to every node in the network. Existing distributed algorithms only consider undirected graphs, which model symmetric networks with uniform transmission ranges. We are particularly interested in the well-established disk graphs, which model asymmetric networks with non-uniform transmission ranges. The corresponding graph theoretic problem seeks a strongly connected dominating-absorbent set of minimum cardinality in a digraph. A subset of nodes in a digraph is a strongly connected dominating-absorbent set if the subgraph induced by these nodes is strongly connected and each node in the graph is either in the set or has both an in-neighbor and an out-neighbor in it. We introduce the first distributed algorithm for this problem in disk graphs. The algorithm gives an O(k^4) -approximation ratio and has a runtime bound of O(Diam) where Diam is the diameter of the graph and k denotes the transmission ratio r_{max}/r_{min} with r_{max} and r_{min} being the maximum and minimum transmission range, respectively. Moreover, we apply our algorithm on the subgraph of disk graphs consisting of only bidirectional edges. Our algorithm gives an O(ln k) -approximation and a runtime bound of O(k^8 log^∗ n) , which, for bounded k , is an optimal approximation for the problem, following Lenzen and Wattenhofer’s Ω(log^∗ n) runtime lower bound for distributed constant approximation in disk graphs."}],"type":"conference","publication":"Proceedings of the 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS)","doi":"10.1007/978-3-642-45346-5_16","title":"A Distributed Approximation Algorithm for Strongly Connected Dominating-Absorbent Sets in Asymmetric Wireless Ad-Hoc Networks","author":[{"last_name":"Markarian","id":"37612","full_name":"Markarian, Christine","first_name":"Christine"},{"last_name":"Meyer auf der Heide","id":"15523","full_name":"Meyer auf der Heide, Friedhelm","first_name":"Friedhelm"},{"first_name":"Michael","last_name":"Schubert","full_name":"Schubert, Michael"}],"date_created":"2017-10-17T12:42:42Z","date_updated":"2022-01-06T07:02:13Z","citation":{"ama":"Markarian C, Meyer auf der Heide F, Schubert M. A Distributed Approximation Algorithm for Strongly Connected Dominating-Absorbent Sets in Asymmetric Wireless Ad-Hoc Networks. In: <i>Proceedings of the 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS)</i>. LNCS. ; 2013:217-227. doi:<a href=\"https://doi.org/10.1007/978-3-642-45346-5_16\">10.1007/978-3-642-45346-5_16</a>","chicago":"Markarian, Christine, Friedhelm Meyer auf der Heide, and Michael Schubert. “A Distributed Approximation Algorithm for Strongly Connected Dominating-Absorbent Sets in Asymmetric Wireless Ad-Hoc Networks.” In <i>Proceedings of the 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS)</i>, 217–27. LNCS, 2013. <a href=\"https://doi.org/10.1007/978-3-642-45346-5_16\">https://doi.org/10.1007/978-3-642-45346-5_16</a>.","ieee":"C. Markarian, F. Meyer auf der Heide, and M. Schubert, “A Distributed Approximation Algorithm for Strongly Connected Dominating-Absorbent Sets in Asymmetric Wireless Ad-Hoc Networks,” in <i>Proceedings of the 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS)</i>, 2013, pp. 217–227.","apa":"Markarian, C., Meyer auf der Heide, F., &#38; Schubert, M. (2013). A Distributed Approximation Algorithm for Strongly Connected Dominating-Absorbent Sets in Asymmetric Wireless Ad-Hoc Networks. In <i>Proceedings of the 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS)</i> (pp. 217–227). <a href=\"https://doi.org/10.1007/978-3-642-45346-5_16\">https://doi.org/10.1007/978-3-642-45346-5_16</a>","mla":"Markarian, Christine, et al. “A Distributed Approximation Algorithm for Strongly Connected Dominating-Absorbent Sets in Asymmetric Wireless Ad-Hoc Networks.” <i>Proceedings of the 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS)</i>, 2013, pp. 217–27, doi:<a href=\"https://doi.org/10.1007/978-3-642-45346-5_16\">10.1007/978-3-642-45346-5_16</a>.","bibtex":"@inproceedings{Markarian_Meyer auf der Heide_Schubert_2013, series={LNCS}, title={A Distributed Approximation Algorithm for Strongly Connected Dominating-Absorbent Sets in Asymmetric Wireless Ad-Hoc Networks}, DOI={<a href=\"https://doi.org/10.1007/978-3-642-45346-5_16\">10.1007/978-3-642-45346-5_16</a>}, booktitle={Proceedings of the 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS)}, author={Markarian, Christine and Meyer auf der Heide, Friedhelm and Schubert, Michael}, year={2013}, pages={217–227}, collection={LNCS} }","short":"C. Markarian, F. Meyer auf der Heide, M. Schubert, in: Proceedings of the 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS), 2013, pp. 217–227."},"page":"217-227","year":"2013","has_accepted_license":"1"},{"title":"A Deterministic Worst-Case Message Complexity Optimal Solution for Resource Discovery","doi":"10.1007/978-3-319-03578-9_14","date_updated":"2022-01-06T07:02:17Z","date_created":"2017-10-17T12:42:42Z","author":[{"first_name":"Sebastian","last_name":"Kniesburges","full_name":"Kniesburges, Sebastian"},{"first_name":"Andreas","full_name":"Koutsopoulos, Andreas","last_name":"Koutsopoulos"},{"id":"20792","full_name":"Scheideler, Christian","last_name":"Scheideler","first_name":"Christian"}],"year":"2013","citation":{"mla":"Kniesburges, Sebastian, et al. “A Deterministic Worst-Case Message Complexity Optimal Solution for Resource Discovery.” <i>Proceedings of 20th International Colloqium on Structural Information and Communication Complexity (SIROCCO)</i>, 2013, pp. 165–76, doi:<a href=\"https://doi.org/10.1007/978-3-319-03578-9_14\">10.1007/978-3-319-03578-9_14</a>.","bibtex":"@inproceedings{Kniesburges_Koutsopoulos_Scheideler_2013, series={Lecture Notes in Computer Science}, title={A Deterministic Worst-Case Message Complexity Optimal Solution for Resource Discovery}, DOI={<a href=\"https://doi.org/10.1007/978-3-319-03578-9_14\">10.1007/978-3-319-03578-9_14</a>}, booktitle={Proceedings of 20th International Colloqium on Structural Information and Communication Complexity (SIROCCO)}, author={Kniesburges, Sebastian and Koutsopoulos, Andreas and Scheideler, Christian}, year={2013}, pages={165–176}, collection={Lecture Notes in Computer Science} }","short":"S. Kniesburges, A. Koutsopoulos, C. Scheideler, in: Proceedings of 20th International Colloqium on Structural Information and Communication Complexity (SIROCCO), 2013, pp. 165–176.","apa":"Kniesburges, S., Koutsopoulos, A., &#38; Scheideler, C. (2013). A Deterministic Worst-Case Message Complexity Optimal Solution for Resource Discovery. In <i>Proceedings of 20th International Colloqium on Structural Information and Communication Complexity (SIROCCO)</i> (pp. 165–176). <a href=\"https://doi.org/10.1007/978-3-319-03578-9_14\">https://doi.org/10.1007/978-3-319-03578-9_14</a>","ama":"Kniesburges S, Koutsopoulos A, Scheideler C. A Deterministic Worst-Case Message Complexity Optimal Solution for Resource Discovery. In: <i>Proceedings of 20th International Colloqium on Structural Information and Communication Complexity (SIROCCO)</i>. Lecture Notes in Computer Science. ; 2013:165-176. doi:<a href=\"https://doi.org/10.1007/978-3-319-03578-9_14\">10.1007/978-3-319-03578-9_14</a>","chicago":"Kniesburges, Sebastian, Andreas Koutsopoulos, and Christian Scheideler. “A Deterministic Worst-Case Message Complexity Optimal Solution for Resource Discovery.” In <i>Proceedings of 20th International Colloqium on Structural Information and Communication Complexity (SIROCCO)</i>, 165–76. Lecture Notes in Computer Science, 2013. <a href=\"https://doi.org/10.1007/978-3-319-03578-9_14\">https://doi.org/10.1007/978-3-319-03578-9_14</a>.","ieee":"S. Kniesburges, A. Koutsopoulos, and C. Scheideler, “A Deterministic Worst-Case Message Complexity Optimal Solution for Resource Discovery,” in <i>Proceedings of 20th International Colloqium on Structural Information and Communication Complexity (SIROCCO)</i>, 2013, pp. 165–176."},"page":"165-176","has_accepted_license":"1","ddc":["040"],"file_date_updated":"2018-03-15T10:24:40Z","project":[{"_id":"1","name":"SFB 901"},{"name":"SFB 901 - Subprojekt A1","_id":"5"},{"_id":"2","name":"SFB 901 - Project Area A"}],"_id":"564","user_id":"15504","series_title":"Lecture Notes in Computer Science","department":[{"_id":"79"}],"abstract":[{"lang":"eng","text":"We consider the problem of resource discovery in distributed systems. In particular we give an algorithm, such that each node in a network discovers the add ress of any other node in the network. We model the knowledge of the nodes as a virtual overlay network given by a directed graph such that complete knowledge of all nodes corresponds to a complete graph in the overlay network. Although there are several solutions for resource discovery, our solution is the first that achieves worst-case optimal work for each node, i.e. the number of addresses (O(n)) or bits (O(nlogn)) a node receives or sendscoincides with the lower bound, while ensuring only a linearruntime (O(n)) on the number of rounds."}],"file":[{"content_type":"application/pdf","relation":"main_file","success":1,"date_created":"2018-03-15T10:24:40Z","creator":"florida","date_updated":"2018-03-15T10:24:40Z","file_id":"1277","file_name":"564-SIROCCO13.pdf","access_level":"closed","file_size":168884}],"status":"public","type":"conference","publication":"Proceedings of 20th International Colloqium on Structural Information and Communication Complexity (SIROCCO)"},{"file":[{"content_type":"application/pdf","success":1,"relation":"main_file","date_updated":"2018-03-15T10:16:20Z","creator":"florida","date_created":"2018-03-15T10:16:20Z","file_size":250051,"file_id":"1272","file_name":"570-Delaunay-Journal.pdf","access_level":"closed"}],"status":"public","abstract":[{"lang":"eng","text":"This article studies the construction of self-stabilizing topologies for distributed systems. While recent research has focused on chain topologies where nodes need to be linearized with respect to their identiers, we explore a natural and relevant 2-dimensional generalization. In particular, we present a local self-stabilizing algorithm DStab which is based on the concept of \\local Delaunay graphs\" and which forwards temporary edges in greedy fashion reminiscent of compass routing. DStab constructs a Delaunay graph from any initial connected topology and in a distributed manner in time O(n3) in the worst-case; if the initial network contains the Delaunay graph, the convergence time is only O(n) rounds. DStab also ensures that individual node joins and leaves aect a small part of the network only. Such self-stabilizing Delaunay networks have interesting applications and our construction gives insights into the necessary geometric reasoning that is required for higherdimensional linearization problems.Keywords: Distributed Algorithms, Topology Control, Social Networks"}],"type":"journal_article","publication":"Theoretical Computer Science","file_date_updated":"2018-03-15T10:16:20Z","ddc":["040"],"user_id":"477","department":[{"_id":"79"}],"project":[{"name":"SFB 901","_id":"1"},{"name":"SFB 901 - Subprojekt A1","_id":"5"},{"_id":"2","name":"SFB 901 - Project Area A"}],"_id":"570","citation":{"apa":"Jacob, R., Ritscher, S., Scheideler, C., &#38; Schmid, S. (2012). Towards higher-dimensional topological self-stabilization: A distributed algorithm for Delaunay graphs. <i>Theoretical Computer Science</i>, 137–148. <a href=\"https://doi.org/10.1016/j.tcs.2012.07.029\">https://doi.org/10.1016/j.tcs.2012.07.029</a>","mla":"Jacob, Riko, et al. “Towards Higher-Dimensional Topological Self-Stabilization: A Distributed Algorithm for Delaunay Graphs.” <i>Theoretical Computer Science</i>, Elsevier, 2012, pp. 137–48, doi:<a href=\"https://doi.org/10.1016/j.tcs.2012.07.029\">10.1016/j.tcs.2012.07.029</a>.","bibtex":"@article{Jacob_Ritscher_Scheideler_Schmid_2012, title={Towards higher-dimensional topological self-stabilization: A distributed algorithm for Delaunay graphs}, DOI={<a href=\"https://doi.org/10.1016/j.tcs.2012.07.029\">10.1016/j.tcs.2012.07.029</a>}, journal={Theoretical Computer Science}, publisher={Elsevier}, author={Jacob, Riko and Ritscher, Stephan and Scheideler, Christian and Schmid, Stefan}, year={2012}, pages={137–148} }","short":"R. Jacob, S. Ritscher, C. Scheideler, S. Schmid, Theoretical Computer Science (2012) 137–148.","ieee":"R. Jacob, S. Ritscher, C. Scheideler, and S. Schmid, “Towards higher-dimensional topological self-stabilization: A distributed algorithm for Delaunay graphs,” <i>Theoretical Computer Science</i>, pp. 137–148, 2012.","chicago":"Jacob, Riko, Stephan Ritscher, Christian Scheideler, and Stefan Schmid. “Towards Higher-Dimensional Topological Self-Stabilization: A Distributed Algorithm for Delaunay Graphs.” <i>Theoretical Computer Science</i>, 2012, 137–48. <a href=\"https://doi.org/10.1016/j.tcs.2012.07.029\">https://doi.org/10.1016/j.tcs.2012.07.029</a>.","ama":"Jacob R, Ritscher S, Scheideler C, Schmid S. Towards higher-dimensional topological self-stabilization: A distributed algorithm for Delaunay graphs. <i>Theoretical Computer Science</i>. 2012:137-148. doi:<a href=\"https://doi.org/10.1016/j.tcs.2012.07.029\">10.1016/j.tcs.2012.07.029</a>"},"page":"137-148","year":"2012","has_accepted_license":"1","doi":"10.1016/j.tcs.2012.07.029","title":"Towards higher-dimensional topological self-stabilization: A distributed algorithm for Delaunay graphs","author":[{"first_name":"Riko","full_name":"Jacob, Riko","last_name":"Jacob"},{"first_name":"Stephan","last_name":"Ritscher","full_name":"Ritscher, Stephan"},{"id":"20792","full_name":"Scheideler, Christian","last_name":"Scheideler","first_name":"Christian"},{"first_name":"Stefan","last_name":"Schmid","full_name":"Schmid, Stefan"}],"date_created":"2017-10-17T12:42:43Z","publisher":"Elsevier","date_updated":"2022-01-06T07:02:36Z"},{"has_accepted_license":"1","page":"18-35","citation":{"ama":"Clouser T, Nesterenko M, Scheideler C. Tiara: A self-stabilizing deterministic skip list and skip graph. <i>Theoretical Computer Science</i>. 2012:18-35. doi:<a href=\"https://doi.org/10.1016/j.tcs.2011.12.079\">10.1016/j.tcs.2011.12.079</a>","chicago":"Clouser, Thomas, Mikhail Nesterenko, and Christian Scheideler. “Tiara: A Self-Stabilizing Deterministic Skip List and Skip Graph.” <i>Theoretical Computer Science</i>, 2012, 18–35. <a href=\"https://doi.org/10.1016/j.tcs.2011.12.079\">https://doi.org/10.1016/j.tcs.2011.12.079</a>.","ieee":"T. Clouser, M. Nesterenko, and C. Scheideler, “Tiara: A self-stabilizing deterministic skip list and skip graph,” <i>Theoretical Computer Science</i>, pp. 18–35, 2012.","apa":"Clouser, T., Nesterenko, M., &#38; Scheideler, C. (2012). Tiara: A self-stabilizing deterministic skip list and skip graph. <i>Theoretical Computer Science</i>, 18–35. <a href=\"https://doi.org/10.1016/j.tcs.2011.12.079\">https://doi.org/10.1016/j.tcs.2011.12.079</a>","mla":"Clouser, Thomas, et al. “Tiara: A Self-Stabilizing Deterministic Skip List and Skip Graph.” <i>Theoretical Computer Science</i>, Elsevier, 2012, pp. 18–35, doi:<a href=\"https://doi.org/10.1016/j.tcs.2011.12.079\">10.1016/j.tcs.2011.12.079</a>.","short":"T. Clouser, M. Nesterenko, C. Scheideler, Theoretical Computer Science (2012) 18–35.","bibtex":"@article{Clouser_Nesterenko_Scheideler_2012, title={Tiara: A self-stabilizing deterministic skip list and skip graph}, DOI={<a href=\"https://doi.org/10.1016/j.tcs.2011.12.079\">10.1016/j.tcs.2011.12.079</a>}, journal={Theoretical Computer Science}, publisher={Elsevier}, author={Clouser, Thomas and Nesterenko, Mikhail and Scheideler, Christian}, year={2012}, pages={18–35} }"},"year":"2012","date_created":"2017-10-17T12:42:44Z","author":[{"last_name":"Clouser","full_name":"Clouser, Thomas","first_name":"Thomas"},{"full_name":"Nesterenko, Mikhail","last_name":"Nesterenko","first_name":"Mikhail"},{"first_name":"Christian","last_name":"Scheideler","full_name":"Scheideler, Christian","id":"20792"}],"publisher":"Elsevier","date_updated":"2022-01-06T07:02:38Z","doi":"10.1016/j.tcs.2011.12.079","title":"Tiara: A self-stabilizing deterministic skip list and skip graph","publication":"Theoretical Computer Science","type":"journal_article","status":"public","file":[{"content_type":"application/pdf","success":1,"relation":"main_file","date_updated":"2018-03-15T09:09:29Z","creator":"florida","date_created":"2018-03-15T09:09:29Z","file_size":315843,"file_name":"574-tiara.pdf","file_id":"1268","access_level":"closed"}],"abstract":[{"lang":"eng","text":"We present Tiara — a self-stabilizing peer-to-peer network maintenance algorithm. Tiara is truly deterministic which allows it to achieve exact performance bounds. Tiara allows logarithmic searches and topology updates. It is based on a novel sparse 0-1 skip list. We then describe its extension to a ringed structure and to a skip-graph.Key words: Peer-to-peer networks, overlay networks, self-stabilization."}],"department":[{"_id":"79"}],"user_id":"477","_id":"574","project":[{"_id":"1","name":"SFB 901"},{"name":"SFB 901 - Subprojekt A1","_id":"5"},{"name":"SFB 901 - Project Area A","_id":"2"}],"file_date_updated":"2018-03-15T09:09:29Z","ddc":["040"]},{"type":"mastersthesis","year":"2012","citation":{"bibtex":"@book{Bremer_2012, title={Symbiotic Coupling of Peer-to-Peer and Cloud Systems}, publisher={Universität Paderborn}, author={Bremer, Lars}, year={2012} }","short":"L. Bremer, Symbiotic Coupling of Peer-to-Peer and Cloud Systems, Universität Paderborn, 2012.","mla":"Bremer, Lars. <i>Symbiotic Coupling of Peer-to-Peer and Cloud Systems</i>. Universität Paderborn, 2012.","apa":"Bremer, L. (2012). <i>Symbiotic Coupling of Peer-to-Peer and Cloud Systems</i>. Universität Paderborn.","chicago":"Bremer, Lars. <i>Symbiotic Coupling of Peer-to-Peer and Cloud Systems</i>. Universität Paderborn, 2012.","ieee":"L. Bremer, <i>Symbiotic Coupling of Peer-to-Peer and Cloud Systems</i>. Universität Paderborn, 2012.","ama":"Bremer L. <i>Symbiotic Coupling of Peer-to-Peer and Cloud Systems</i>. Universität Paderborn; 2012."},"status":"public","date_updated":"2022-01-06T07:02:38Z","project":[{"_id":"1","name":"SFB 901"},{"_id":"5","name":"SFB 901 - Subprojekt A1"},{"name":"SFB 901 - Project Area A","_id":"2"}],"publisher":"Universität Paderborn","_id":"575","author":[{"last_name":"Bremer","full_name":"Bremer, Lars","first_name":"Lars"}],"date_created":"2017-10-17T12:42:44Z","user_id":"15504","title":"Symbiotic Coupling of Peer-to-Peer and Cloud Systems"},{"has_accepted_license":"1","issue":"3","year":"2012","page":"30","citation":{"ama":"Damerow V, Manthey B, Meyer auf der Heide F, et al. Smoothed analysis of left-to-right maxima with applications. <i>Transactions on Algorithms</i>. 2012;(3):30. doi:<a href=\"https://doi.org/10.1145/2229163.2229174\">10.1145/2229163.2229174</a>","chicago":"Damerow, Valentina, Bodo Manthey, Friedhelm Meyer auf der Heide, Harald Räcke, Christian Scheideler, Christian Sohler, and Till Tantau. “Smoothed Analysis of Left-to-Right Maxima with Applications.” <i>Transactions on Algorithms</i>, no. 3 (2012): 30. <a href=\"https://doi.org/10.1145/2229163.2229174\">https://doi.org/10.1145/2229163.2229174</a>.","ieee":"V. Damerow <i>et al.</i>, “Smoothed analysis of left-to-right maxima with applications,” <i>Transactions on Algorithms</i>, no. 3, p. 30, 2012.","apa":"Damerow, V., Manthey, B., Meyer auf der Heide, F., Räcke, H., Scheideler, C., Sohler, C., &#38; Tantau, T. (2012). Smoothed analysis of left-to-right maxima with applications. <i>Transactions on Algorithms</i>, (3), 30. <a href=\"https://doi.org/10.1145/2229163.2229174\">https://doi.org/10.1145/2229163.2229174</a>","bibtex":"@article{Damerow_Manthey_Meyer auf der Heide_Räcke_Scheideler_Sohler_Tantau_2012, title={Smoothed analysis of left-to-right maxima with applications}, DOI={<a href=\"https://doi.org/10.1145/2229163.2229174\">10.1145/2229163.2229174</a>}, number={3}, journal={Transactions on Algorithms}, publisher={ACM}, author={Damerow, Valentina and Manthey, Bodo and Meyer auf der Heide, Friedhelm and Räcke, Harald and Scheideler, Christian and Sohler, Christian and Tantau, Till}, year={2012}, pages={30} }","short":"V. Damerow, B. Manthey, F. Meyer auf der Heide, H. Räcke, C. Scheideler, C. Sohler, T. Tantau, Transactions on Algorithms (2012) 30.","mla":"Damerow, Valentina, et al. “Smoothed Analysis of Left-to-Right Maxima with Applications.” <i>Transactions on Algorithms</i>, no. 3, ACM, 2012, p. 30, doi:<a href=\"https://doi.org/10.1145/2229163.2229174\">10.1145/2229163.2229174</a>."},"date_updated":"2022-01-06T07:02:41Z","publisher":"ACM","date_created":"2017-10-17T12:42:45Z","author":[{"first_name":"Valentina","last_name":"Damerow","full_name":"Damerow, Valentina"},{"last_name":"Manthey","full_name":"Manthey, Bodo","first_name":"Bodo"},{"first_name":"Friedhelm","last_name":"Meyer auf der Heide","id":"15523","full_name":"Meyer auf der Heide, Friedhelm"},{"last_name":"Räcke","full_name":"Räcke, Harald","first_name":"Harald"},{"first_name":"Christian","last_name":"Scheideler","full_name":"Scheideler, Christian","id":"20792"},{"first_name":"Christian","full_name":"Sohler, Christian","last_name":"Sohler"},{"last_name":"Tantau","full_name":"Tantau, Till","first_name":"Till"}],"title":"Smoothed analysis of left-to-right maxima with applications","doi":"10.1145/2229163.2229174","publication":"Transactions on Algorithms","type":"journal_article","abstract":[{"lang":"eng","text":"A left-to-right maximum in a sequence of n numbers s_1, …, s_n is a number that is strictly larger than all preceding numbers. In this article we present a smoothed analysis of the number of left-to-right maxima in the presence of additive random noise. We show that for every sequence of n numbers s_i ∈ [0,1] that are perturbed by uniform noise from the interval [-ε,ε], the expected number of left-to-right maxima is Θ(&sqrt;n/ε + log n) for ε>1/n. For Gaussian noise with standard deviation σ we obtain a bound of O((log3/2 n)/σ + log n).We apply our results to the analysis of the smoothed height of binary search trees and the smoothed number of comparisons in the quicksort algorithm and prove bounds of Θ(&sqrt;n/ε + log n) and Θ(n/ε+1&sqrt;n/ε + n log n), respectively, for uniform random noise from the interval [-ε,ε]. Our results can also be applied to bound the smoothed number of points on a convex hull of points in the two-dimensional plane and to smoothed motion complexity, a concept we describe in this article. We bound how often one needs to update a data structure storing the smallest axis-aligned box enclosing a set of points moving in d-dimensional space."}],"status":"public","file":[{"file_size":329282,"file_id":"1266","access_level":"closed","file_name":"579-a30-damerow.pdf","date_updated":"2018-03-15T09:04:58Z","date_created":"2018-03-15T09:04:58Z","creator":"florida","success":1,"relation":"main_file","content_type":"application/pdf"}],"_id":"579","project":[{"_id":"1","name":"SFB 901"},{"name":"SFB 901 - Subprojekt A1","_id":"5"},{"_id":"2","name":"SFB 901 - Project Area A"}],"department":[{"_id":"79"},{"_id":"63"}],"user_id":"477","ddc":["040"],"file_date_updated":"2018-03-15T09:04:58Z"},{"year":"2012","citation":{"mla":"Strothmann, Thim Frederik. <i>Self-Optimizing Binary Search Trees - A Game Theoretic Approach</i>. Universität Paderborn, 2012.","bibtex":"@book{Strothmann_2012, title={Self-Optimizing Binary Search Trees - A Game Theoretic Approach}, publisher={Universität Paderborn}, author={Strothmann, Thim Frederik}, year={2012} }","short":"T.F. Strothmann, Self-Optimizing Binary Search Trees - A Game Theoretic Approach, Universität Paderborn, 2012.","apa":"Strothmann, T. F. (2012). <i>Self-Optimizing Binary Search Trees - A Game Theoretic Approach</i>. Universität Paderborn.","chicago":"Strothmann, Thim Frederik. <i>Self-Optimizing Binary Search Trees - A Game Theoretic Approach</i>. Universität Paderborn, 2012.","ieee":"T. F. Strothmann, <i>Self-Optimizing Binary Search Trees - A Game Theoretic Approach</i>. Universität Paderborn, 2012.","ama":"Strothmann TF. <i>Self-Optimizing Binary Search Trees - A Game Theoretic Approach</i>. Universität Paderborn; 2012."},"title":"Self-Optimizing Binary Search Trees - A Game Theoretic Approach","date_updated":"2022-01-06T07:02:42Z","publisher":"Universität Paderborn","date_created":"2017-10-17T12:42:45Z","author":[{"first_name":"Thim Frederik","last_name":"Strothmann","id":"11319","full_name":"Strothmann, Thim Frederik"}],"status":"public","type":"mastersthesis","language":[{"iso":"eng"}],"_id":"582","project":[{"_id":"1","name":"SFB 901"},{"_id":"5","name":"SFB 901 - Subprojekt A1"},{"_id":"2","name":"SFB 901 - Project Area A"}],"department":[{"_id":"79"}],"user_id":"477"},{"citation":{"chicago":"Klerx, Timo. <i>Online Parameteroptimierung in P2P-Netzwerken mit Hilfe von Neuronalen Netzen</i>. Universität Paderborn, 2012.","ieee":"T. Klerx, <i>Online Parameteroptimierung in P2P-Netzwerken mit Hilfe von Neuronalen Netzen</i>. Universität Paderborn, 2012.","ama":"Klerx T. <i>Online Parameteroptimierung in P2P-Netzwerken mit Hilfe von Neuronalen Netzen</i>. Universität Paderborn; 2012.","bibtex":"@book{Klerx_2012, title={Online Parameteroptimierung in P2P-Netzwerken mit Hilfe von Neuronalen Netzen}, publisher={Universität Paderborn}, author={Klerx, Timo}, year={2012} }","short":"T. Klerx, Online Parameteroptimierung in P2P-Netzwerken mit Hilfe von Neuronalen Netzen, Universität Paderborn, 2012.","mla":"Klerx, Timo. <i>Online Parameteroptimierung in P2P-Netzwerken mit Hilfe von Neuronalen Netzen</i>. Universität Paderborn, 2012.","apa":"Klerx, T. (2012). <i>Online Parameteroptimierung in P2P-Netzwerken mit Hilfe von Neuronalen Netzen</i>. Universität Paderborn."},"year":"2012","title":"Online Parameteroptimierung in P2P-Netzwerken mit Hilfe von Neuronalen Netzen","date_created":"2017-10-17T12:42:47Z","author":[{"full_name":"Klerx, Timo","last_name":"Klerx","first_name":"Timo"}],"date_updated":"2022-01-06T07:02:48Z","publisher":"Universität Paderborn","status":"public","type":"mastersthesis","language":[{"iso":"ger"}],"user_id":"477","_id":"594","project":[{"_id":"1","name":"SFB 901"},{"name":"SFB 901 - Subprojekt A1","_id":"5"},{"_id":"2","name":"SFB 901 - Project Area A"}]},{"status":"public","type":"bachelorsthesis","language":[{"iso":"ger"}],"user_id":"477","project":[{"_id":"1","name":"SFB 901"},{"name":"SFB 901 - Subprojekt A1","_id":"5"},{"_id":"2","name":"SFB 901 - Project Area A"}],"_id":"600","citation":{"chicago":"Feldkord, Björn. <i>Lokale Swaps und überholte Informationen in Basic Network Creation Games</i>. Universität Paderborn, 2012.","ieee":"B. Feldkord, <i>Lokale Swaps und überholte Informationen in Basic Network Creation Games</i>. Universität Paderborn, 2012.","ama":"Feldkord B. <i>Lokale Swaps und überholte Informationen in Basic Network Creation Games</i>. Universität Paderborn; 2012.","short":"B. Feldkord, Lokale Swaps und überholte Informationen in Basic Network Creation Games, Universität Paderborn, 2012.","bibtex":"@book{Feldkord_2012, title={Lokale Swaps und überholte Informationen in Basic Network Creation Games}, publisher={Universität Paderborn}, author={Feldkord, Björn}, year={2012} }","mla":"Feldkord, Björn. <i>Lokale Swaps und überholte Informationen in Basic Network Creation Games</i>. Universität Paderborn, 2012.","apa":"Feldkord, B. (2012). <i>Lokale Swaps und überholte Informationen in Basic Network Creation Games</i>. Universität Paderborn."},"year":"2012","title":"Lokale Swaps und überholte Informationen in Basic Network Creation Games","author":[{"first_name":"Björn","id":"22704","full_name":"Feldkord, Björn","last_name":"Feldkord"}],"date_created":"2017-10-17T12:42:49Z","publisher":"Universität Paderborn","date_updated":"2022-01-06T07:02:49Z"},{"year":"2012","title":"Local strategies for robot formation problems","date_created":"2017-10-17T12:42:49Z","publisher":"Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn","file":[{"success":1,"relation":"main_file","content_type":"application/pdf","file_size":3805310,"file_name":"601-Kempkes-PhD.pdf","file_id":"1252","access_level":"closed","date_updated":"2018-03-15T08:16:44Z","date_created":"2018-03-15T08:16:44Z","creator":"florida"}],"abstract":[{"lang":"eng","text":"Wir betrachten eine Gruppe von mobilen, autonomen Robotern in einem ebenen Gel{\\\"a}nde. Es gibt keine zentrale Steuerung und die Roboter m{\\\"u}ssen sich selbst koordinieren. Zentrale Herausforderung dabei ist, dass jeder Roboter nur seine unmittelbare Nachbarschaft sieht und auch nur mit Robotern in seiner unmittelbaren Nachbarschaft kommunizieren kann. Daraus ergeben sich viele algorithmische Fragestellungen. In dieser Arbeit wird untersucht, unter welchen Voraussetzungen die Roboter sich auf einem Punkt versammeln bzw. eine Linie zwischen zwei festen Stationen bilden k{\\\"o}nnen. Daf{\\\"u}r werden mehrere Roboter-Strategien in verschiedenen Bewegungsmodellen vorgestellt. Diese Strategien werden auf ihre Effizienz hin untersucht. Es werden obere und untere Schranken f{\\\"u}r die ben{\\\"o}tigte Anzahl Runden und die Bewegungsdistanz gezeigt. In einigen F{\\\"a}llen wird außerdem die ben{\\\"o}tigte Bewegungsdistanz mit derjenigen Bewegungsdistanz verglichen, die eine optimale globale Strategie auf der gleichen Instanz ben{\\\"o}tigen w{\\\"u}rde. So werden kompetititve Faktoren hergeleitet."}],"language":[{"iso":"eng"}],"ddc":["040"],"citation":{"apa":"Kempkes, B. (2012). <i>Local strategies for robot formation problems</i> (Vol. 302). Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn.","bibtex":"@book{Kempkes_2012, series={Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}, title={Local strategies for robot formation problems}, volume={302}, publisher={Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}, author={Kempkes, Barbara}, year={2012}, collection={Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn} }","short":"B. Kempkes, Local Strategies for Robot Formation Problems, Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn, 2012.","mla":"Kempkes, Barbara. <i>Local Strategies for Robot Formation Problems</i>. Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn, 2012.","ieee":"B. Kempkes, <i>Local strategies for robot formation problems</i>, vol. 302. Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn, 2012.","chicago":"Kempkes, Barbara. <i>Local Strategies for Robot Formation Problems</i>. Vol. 302. Verlagsschriftenreihe Des Heinz Nixdorf Instituts, Paderborn. Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn, 2012.","ama":"Kempkes B. <i>Local Strategies for Robot Formation Problems</i>. Vol 302. Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn; 2012."},"intvolume":"       302","has_accepted_license":"1","publication_identifier":{"isbn":["978-3-942647-21-2"]},"author":[{"full_name":"Kempkes, Barbara","last_name":"Kempkes","first_name":"Barbara"}],"supervisor":[{"first_name":"Friedhelm","full_name":"Meyer auf der Heide, Friedhelm","id":"15523","last_name":"Meyer auf der Heide"}],"volume":302,"date_updated":"2022-01-06T07:02:50Z","status":"public","type":"dissertation","file_date_updated":"2018-03-15T08:16:44Z","user_id":"5786","series_title":"Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn","department":[{"_id":"63"},{"_id":"26"}],"project":[{"_id":"1","name":"SFB 901"},{"_id":"5","name":"SFB 901 - Subprojekt A1"},{"_id":"2","name":"SFB 901 - Project Area A"}],"_id":"601"},{"citation":{"ama":"Kurras S. <i>Distributed Sampling of Regular Graphs</i>. Universität Paderborn; 2012.","chicago":"Kurras, Sven. <i>Distributed Sampling of Regular Graphs</i>. Universität Paderborn, 2012.","ieee":"S. Kurras, <i>Distributed Sampling of Regular Graphs</i>. Universität Paderborn, 2012.","apa":"Kurras, S. (2012). <i>Distributed Sampling of Regular Graphs</i>. Universität Paderborn.","bibtex":"@book{Kurras_2012, title={Distributed Sampling of Regular Graphs}, publisher={Universität Paderborn}, author={Kurras, Sven}, year={2012} }","short":"S. Kurras, Distributed Sampling of Regular Graphs, Universität Paderborn, 2012.","mla":"Kurras, Sven. <i>Distributed Sampling of Regular Graphs</i>. Universität Paderborn, 2012."},"status":"public","year":"2012","type":"mastersthesis","title":"Distributed Sampling of Regular Graphs","date_created":"2017-10-17T12:42:52Z","author":[{"first_name":"Sven","last_name":"Kurras","full_name":"Kurras, Sven"}],"user_id":"15504","date_updated":"2022-01-06T07:02:55Z","project":[{"_id":"1","name":"SFB 901"},{"name":"SFB 901 - Subprojekt A1","_id":"5"},{"name":"SFB 901 - Project Area A","_id":"2"}],"publisher":"Universität Paderborn","_id":"618"},{"year":"2012","page":"9-14","citation":{"ama":"Brandes P, Meyer auf der Heide F. Distributed Computing in Fault-Prone Dynamic Networks. In: <i>Proceedings of the 4th Workshop on Theoretical Aspects of Dynamic Distributed Systems (TADDS)</i>. ICPS. ; 2012:9-14. doi:<a href=\"https://doi.org/10.1145/2414815.2414818\">10.1145/2414815.2414818</a>","ieee":"P. Brandes and F. Meyer auf der Heide, “Distributed Computing in Fault-Prone Dynamic Networks,” in <i>Proceedings of the 4th Workshop on Theoretical Aspects of Dynamic Distributed Systems (TADDS)</i>, 2012, pp. 9–14.","chicago":"Brandes, Philipp, and Friedhelm Meyer auf der Heide. “Distributed Computing in Fault-Prone Dynamic Networks.” In <i>Proceedings of the 4th Workshop on Theoretical Aspects of Dynamic Distributed Systems (TADDS)</i>, 9–14. ICPS, 2012. <a href=\"https://doi.org/10.1145/2414815.2414818\">https://doi.org/10.1145/2414815.2414818</a>.","mla":"Brandes, Philipp, and Friedhelm Meyer auf der Heide. “Distributed Computing in Fault-Prone Dynamic Networks.” <i>Proceedings of the 4th Workshop on Theoretical Aspects of Dynamic Distributed Systems (TADDS)</i>, 2012, pp. 9–14, doi:<a href=\"https://doi.org/10.1145/2414815.2414818\">10.1145/2414815.2414818</a>.","short":"P. Brandes, F. Meyer auf der Heide, in: Proceedings of the 4th Workshop on Theoretical Aspects of Dynamic Distributed Systems (TADDS), 2012, pp. 9–14.","bibtex":"@inproceedings{Brandes_Meyer auf der Heide_2012, series={ICPS}, title={Distributed Computing in Fault-Prone Dynamic Networks}, DOI={<a href=\"https://doi.org/10.1145/2414815.2414818\">10.1145/2414815.2414818</a>}, booktitle={Proceedings of the 4th Workshop on Theoretical Aspects of Dynamic Distributed Systems (TADDS)}, author={Brandes, Philipp and Meyer auf der Heide, Friedhelm}, year={2012}, pages={9–14}, collection={ICPS} }","apa":"Brandes, P., &#38; Meyer auf der Heide, F. (2012). Distributed Computing in Fault-Prone Dynamic Networks. In <i>Proceedings of the 4th Workshop on Theoretical Aspects of Dynamic Distributed Systems (TADDS)</i> (pp. 9–14). <a href=\"https://doi.org/10.1145/2414815.2414818\">https://doi.org/10.1145/2414815.2414818</a>"},"has_accepted_license":"1","title":"Distributed Computing in Fault-Prone Dynamic Networks","doi":"10.1145/2414815.2414818","date_updated":"2022-01-06T07:02:56Z","date_created":"2017-10-17T12:42:52Z","author":[{"full_name":"Brandes, Philipp","last_name":"Brandes","first_name":"Philipp"},{"last_name":"Meyer auf der Heide","id":"15523","full_name":"Meyer auf der Heide, Friedhelm","first_name":"Friedhelm"}],"abstract":[{"text":"Dynamics in networks is caused by a variety of reasons, like nodes moving in 2D (or 3D) in multihop cellphone networks, joins and leaves in peer-to-peer networks, evolution in social networks, and many others. In order to understand such kinds of dynamics, and to design distributed algorithms that behave well under dynamics, many ways to model dynamics are introduced and analyzed w.r.t. correctness and eciency of distributed algorithms. In [16], Kuhn, Lynch, and Oshman have introduced a very general, worst case type model of dynamics: The edge set of the network may change arbitrarily from step to step, the only restriction is that it is connected at all times and the set of nodes does not change. An extended model demands that a xed connected subnetwork is maintained over each time interval of length T (T-interval dynamics). They have presented, among others, algorithms for counting the number of nodes under such general models of dynamics.In this paper, we generalize their models and algorithms by adding random edge faults, i.e., we consider fault-prone dynamic networks: We assume that an edge currently existing may fail to transmit data with some probability p. We rst observe that strong counting, i.e., each node knows the correct count and stops, is not possible in a model with random edge faults. Our main two positive results are feasibility and runtime bounds for weak counting, i.e., stopping is no longer required (but still a correct count in each node), and for strong counting with an upper bound, i.e., an upper bound N on n is known to all nodes.","lang":"eng"}],"status":"public","file":[{"creator":"florida","date_created":"2018-03-15T06:47:15Z","date_updated":"2018-03-15T06:47:15Z","access_level":"closed","file_id":"1244","file_name":"619-Brandes_MadHTADDS12_01.pdf","file_size":346044,"content_type":"application/pdf","relation":"main_file","success":1}],"publication":"Proceedings of the 4th Workshop on Theoretical Aspects of Dynamic Distributed Systems (TADDS)","type":"conference","ddc":["040"],"file_date_updated":"2018-03-15T06:47:15Z","_id":"619","project":[{"name":"SFB 901","_id":"1"},{"_id":"5","name":"SFB 901 - Subprojekt A1"},{"name":"SFB 901 - Project Area A","_id":"2"}],"department":[{"_id":"63"}],"user_id":"15504","series_title":"ICPS"},{"abstract":[{"text":"This paper initiates the study of self-adjusting distributed data structures for networks. In particular, we present SplayNets: a binary search tree based network that is self-adjusting to routing request.We derive entropy bounds on the amortized routing cost and show that our splaying algorithm has some interesting properties.","lang":"eng"}],"file":[{"file_size":717284,"access_level":"closed","file_id":"1240","file_name":"625-disc12adjBAshort.pdf","date_updated":"2018-03-15T06:44:09Z","date_created":"2018-03-15T06:44:09Z","creator":"florida","success":1,"relation":"main_file","content_type":"application/pdf"}],"status":"public","type":"conference","publication":"Proceedings of the 26th International Symposium on Distributed Computing (DISC)","ddc":["040"],"file_date_updated":"2018-03-15T06:44:09Z","project":[{"_id":"1","name":"SFB 901"},{"name":"SFB 901 - Subprojekt A1","_id":"5"},{"name":"SFB 901 - Project Area A","_id":"2"}],"_id":"625","user_id":"15504","series_title":"LNCS","department":[{"_id":"79"}],"year":"2012","citation":{"ieee":"S. Schmid, C. Avin, C. Scheideler, B. Häupler, and Z. Lotker, “Brief Announcement: SplayNets - Towards Self-Adjusting Distributed Data Structures,” in <i>Proceedings of the 26th International Symposium on Distributed Computing (DISC)</i>, 2012, pp. 439–440.","chicago":"Schmid, Stefan, Chen Avin, Christian Scheideler, Bernhard Häupler, and Zvi Lotker. “Brief Announcement: SplayNets - Towards Self-Adjusting Distributed Data Structures.” In <i>Proceedings of the 26th International Symposium on Distributed Computing (DISC)</i>, 439–40. LNCS, 2012. <a href=\"https://doi.org/10.1007/978-3-642-33651-5_47\">https://doi.org/10.1007/978-3-642-33651-5_47</a>.","ama":"Schmid S, Avin C, Scheideler C, Häupler B, Lotker Z. Brief Announcement: SplayNets - Towards Self-Adjusting Distributed Data Structures. In: <i>Proceedings of the 26th International Symposium on Distributed Computing (DISC)</i>. LNCS. ; 2012:439-440. doi:<a href=\"https://doi.org/10.1007/978-3-642-33651-5_47\">10.1007/978-3-642-33651-5_47</a>","mla":"Schmid, Stefan, et al. “Brief Announcement: SplayNets - Towards Self-Adjusting Distributed Data Structures.” <i>Proceedings of the 26th International Symposium on Distributed Computing (DISC)</i>, 2012, pp. 439–40, doi:<a href=\"https://doi.org/10.1007/978-3-642-33651-5_47\">10.1007/978-3-642-33651-5_47</a>.","bibtex":"@inproceedings{Schmid_Avin_Scheideler_Häupler_Lotker_2012, series={LNCS}, title={Brief Announcement: SplayNets - Towards Self-Adjusting Distributed Data Structures}, DOI={<a href=\"https://doi.org/10.1007/978-3-642-33651-5_47\">10.1007/978-3-642-33651-5_47</a>}, booktitle={Proceedings of the 26th International Symposium on Distributed Computing (DISC)}, author={Schmid, Stefan and Avin, Chen and Scheideler, Christian and Häupler, Bernhard and Lotker, Zvi}, year={2012}, pages={439–440}, collection={LNCS} }","short":"S. Schmid, C. Avin, C. Scheideler, B. Häupler, Z. Lotker, in: Proceedings of the 26th International Symposium on Distributed Computing (DISC), 2012, pp. 439–440.","apa":"Schmid, S., Avin, C., Scheideler, C., Häupler, B., &#38; Lotker, Z. (2012). Brief Announcement: SplayNets - Towards Self-Adjusting Distributed Data Structures. In <i>Proceedings of the 26th International Symposium on Distributed Computing (DISC)</i> (pp. 439–440). <a href=\"https://doi.org/10.1007/978-3-642-33651-5_47\">https://doi.org/10.1007/978-3-642-33651-5_47</a>"},"page":"439-440","has_accepted_license":"1","title":"Brief Announcement: SplayNets - Towards Self-Adjusting Distributed Data Structures","doi":"10.1007/978-3-642-33651-5_47","date_updated":"2022-01-06T07:02:58Z","author":[{"first_name":"Stefan","full_name":"Schmid, Stefan","last_name":"Schmid"},{"last_name":"Avin","full_name":"Avin, Chen","first_name":"Chen"},{"id":"20792","full_name":"Scheideler, Christian","last_name":"Scheideler","first_name":"Christian"},{"last_name":"Häupler","full_name":"Häupler, Bernhard","first_name":"Bernhard"},{"last_name":"Lotker","full_name":"Lotker, Zvi","first_name":"Zvi"}],"date_created":"2017-10-17T12:42:53Z"},{"author":[{"first_name":"Sebastian","last_name":"Kniesburges","full_name":"Kniesburges, Sebastian"},{"full_name":"Scheideler, Christian","id":"20792","last_name":"Scheideler","first_name":"Christian"}],"date_created":"2017-10-17T12:42:54Z","date_updated":"2022-01-06T07:02:59Z","doi":"10.1007/978-3-642-33651-5_45","title":"Brief Announcement: Hashed Predecessor Patricia Trie - A Data Structure for Efficient Predecessor Queries in Peer-to-Peer Systems","has_accepted_license":"1","page":"435-436","citation":{"ama":"Kniesburges S, Scheideler C. Brief Announcement: Hashed Predecessor Patricia Trie - A Data Structure for Efficient Predecessor Queries in Peer-to-Peer Systems. In: <i>Proceedings of the 26th International Symposium on Distributed Computing (DISC)</i>. LNCS. ; 2012:435-436. doi:<a href=\"https://doi.org/10.1007/978-3-642-33651-5_45\">10.1007/978-3-642-33651-5_45</a>","ieee":"S. Kniesburges and C. Scheideler, “Brief Announcement: Hashed Predecessor Patricia Trie - A Data Structure for Efficient Predecessor Queries in Peer-to-Peer Systems,” in <i>Proceedings of the 26th International Symposium on Distributed Computing (DISC)</i>, 2012, pp. 435–436.","chicago":"Kniesburges, Sebastian, and Christian Scheideler. “Brief Announcement: Hashed Predecessor Patricia Trie - A Data Structure for Efficient Predecessor Queries in Peer-to-Peer Systems.” In <i>Proceedings of the 26th International Symposium on Distributed Computing (DISC)</i>, 435–36. LNCS, 2012. <a href=\"https://doi.org/10.1007/978-3-642-33651-5_45\">https://doi.org/10.1007/978-3-642-33651-5_45</a>.","short":"S. Kniesburges, C. Scheideler, in: Proceedings of the 26th International Symposium on Distributed Computing (DISC), 2012, pp. 435–436.","bibtex":"@inproceedings{Kniesburges_Scheideler_2012, series={LNCS}, title={Brief Announcement: Hashed Predecessor Patricia Trie - A Data Structure for Efficient Predecessor Queries in Peer-to-Peer Systems}, DOI={<a href=\"https://doi.org/10.1007/978-3-642-33651-5_45\">10.1007/978-3-642-33651-5_45</a>}, booktitle={Proceedings of the 26th International Symposium on Distributed Computing (DISC)}, author={Kniesburges, Sebastian and Scheideler, Christian}, year={2012}, pages={435–436}, collection={LNCS} }","mla":"Kniesburges, Sebastian, and Christian Scheideler. “Brief Announcement: Hashed Predecessor Patricia Trie - A Data Structure for Efficient Predecessor Queries in Peer-to-Peer Systems.” <i>Proceedings of the 26th International Symposium on Distributed Computing (DISC)</i>, 2012, pp. 435–36, doi:<a href=\"https://doi.org/10.1007/978-3-642-33651-5_45\">10.1007/978-3-642-33651-5_45</a>.","apa":"Kniesburges, S., &#38; Scheideler, C. (2012). Brief Announcement: Hashed Predecessor Patricia Trie - A Data Structure for Efficient Predecessor Queries in Peer-to-Peer Systems. In <i>Proceedings of the 26th International Symposium on Distributed Computing (DISC)</i> (pp. 435–436). <a href=\"https://doi.org/10.1007/978-3-642-33651-5_45\">https://doi.org/10.1007/978-3-642-33651-5_45</a>"},"year":"2012","department":[{"_id":"79"}],"series_title":"LNCS","user_id":"15504","_id":"626","project":[{"name":"SFB 901","_id":"1"},{"_id":"5","name":"SFB 901 - Subprojekt A1"},{"name":"SFB 901 - Project Area A","_id":"2"}],"file_date_updated":"2018-03-15T06:42:40Z","ddc":["040"],"publication":"Proceedings of the 26th International Symposium on Distributed Computing (DISC)","type":"conference","status":"public","file":[{"file_name":"626-Predecessor-Kniesburges_Scheideler.pdf","access_level":"closed","file_id":"1239","file_size":184095,"creator":"florida","date_created":"2018-03-15T06:42:40Z","date_updated":"2018-03-15T06:42:40Z","relation":"main_file","success":1,"content_type":"application/pdf"}],"abstract":[{"text":"The design of ecient search structures for peer-to-peer systems has attracted a lot of attention in recent years. In this announcement we address the problem of nding the predecessor in a key set and present an ecient data structure called hashed Predecessor Patricia trie. Our hashed Predecessor Patricia trie supports PredecessorSearch(x) and Insert(x) and Delete(x) in O(log log u) hash table accesses when u is the size of the universe of the keys. That is the costs only depend on u and not the size of the data structure. One feature of our approach is that it only uses the lookup interface of the hash table and therefore hash table accesses may be realized by any distributed hash table (DHT).","lang":"eng"}]}]