[{"language":[{"iso":"eng"}],"_id":"18520","project":[{"name":"SFB 901","_id":"1"},{"_id":"4","name":"SFB 901 - Project Area C"},{"name":"SFB 901 - Subproject C1","_id":"13"}],"department":[{"_id":"79"}],"user_id":"477","status":"public","type":"dissertation","title":"Local Graph Transformation Primitives For Some Basic Problems In Overlay Networks","doi":"10.17619/UNIPB/1-1026","publisher":"Universität Paderborn","date_updated":"2022-01-06T06:53:36Z","date_created":"2020-08-28T06:50:29Z","author":[{"full_name":"Setzer, Alexander","id":"11108","last_name":"Setzer","first_name":"Alexander"}],"supervisor":[{"id":"20792","full_name":"Scheideler, Christian","last_name":"Scheideler","first_name":"Christian"}],"year":"2020","citation":{"apa":"Setzer, A. (2020). <i>Local Graph Transformation Primitives For Some Basic Problems In Overlay Networks</i>. Universität Paderborn. <a href=\"https://doi.org/10.17619/UNIPB/1-1026\">https://doi.org/10.17619/UNIPB/1-1026</a>","mla":"Setzer, Alexander. <i>Local Graph Transformation Primitives For Some Basic Problems In Overlay Networks</i>. Universität Paderborn, 2020, doi:<a href=\"https://doi.org/10.17619/UNIPB/1-1026\">10.17619/UNIPB/1-1026</a>.","bibtex":"@book{Setzer_2020, title={Local Graph Transformation Primitives For Some Basic Problems In Overlay Networks}, DOI={<a href=\"https://doi.org/10.17619/UNIPB/1-1026\">10.17619/UNIPB/1-1026</a>}, publisher={Universität Paderborn}, author={Setzer, Alexander}, year={2020} }","short":"A. Setzer, Local Graph Transformation Primitives For Some Basic Problems In Overlay Networks, Universität Paderborn, 2020.","ama":"Setzer A. <i>Local Graph Transformation Primitives For Some Basic Problems In Overlay Networks</i>. Universität Paderborn; 2020. doi:<a href=\"https://doi.org/10.17619/UNIPB/1-1026\">10.17619/UNIPB/1-1026</a>","chicago":"Setzer, Alexander. <i>Local Graph Transformation Primitives For Some Basic Problems In Overlay Networks</i>. Universität Paderborn, 2020. <a href=\"https://doi.org/10.17619/UNIPB/1-1026\">https://doi.org/10.17619/UNIPB/1-1026</a>.","ieee":"A. Setzer, <i>Local Graph Transformation Primitives For Some Basic Problems In Overlay Networks</i>. Universität Paderborn, 2020."}},{"year":"2019","title":"On the Complexity of Local Graph Transformations","publisher":"Dagstuhl Publishing","date_created":"2019-07-08T17:19:01Z","abstract":[{"text":"We consider the problem of transforming a given graph G_s into a desired graph G_t by applying a minimum number of primitives from a particular set of local graph transformation primitives. These primitives are local in the sense that each node can apply them based on local knowledge and by affecting only its 1-neighborhood. Although the specific set of primitives we consider makes it possible to transform any (weakly) connected graph into any other (weakly) connected graph consisting of the same nodes, they cannot disconnect the graph or introduce new nodes into the graph, making them ideal in the context of supervised overlay network transformations. We prove that computing a minimum sequence of primitive applications (even centralized) for arbitrary G_s and G_t is NP-hard, which we conjecture to hold for any set of local graph transformation primitives satisfying the aforementioned properties. On the other hand, we show that this problem admits a polynomial time algorithm with a constant approximation ratio.","lang":"eng"}],"file":[{"file_size":537649,"file_name":"LIPIcs-ICALP-2019-150.pdf","access_level":"closed","file_id":"12955","date_updated":"2019-08-26T09:21:27Z","creator":"ups","date_created":"2019-08-26T09:21:27Z","success":1,"relation":"main_file","content_type":"application/pdf"}],"publication":"Proceedings of the 46th International Colloquium on Automata, Languages, and Programming","ddc":["004"],"keyword":["Graphs transformations","NP-hardness","approximation algorithms"],"language":[{"iso":"eng"}],"citation":{"bibtex":"@inproceedings{Scheideler_Setzer_2019, series={LIPIcs}, title={On the Complexity of Local Graph Transformations}, volume={132}, DOI={<a href=\"https://doi.org/10.4230/LIPICS.ICALP.2019.150\">10.4230/LIPICS.ICALP.2019.150</a>}, booktitle={Proceedings of the 46th International Colloquium on Automata, Languages, and Programming}, publisher={Dagstuhl Publishing}, author={Scheideler, Christian and Setzer, Alexander}, year={2019}, pages={150:1--150:14}, collection={LIPIcs} }","short":"C. Scheideler, A. Setzer, in: Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, Dagstuhl Publishing, 2019, pp. 150:1--150:14.","mla":"Scheideler, Christian, and Alexander Setzer. “On the Complexity of Local Graph Transformations.” <i>Proceedings of the 46th International Colloquium on Automata, Languages, and Programming</i>, vol. 132, Dagstuhl Publishing, 2019, pp. 150:1--150:14, doi:<a href=\"https://doi.org/10.4230/LIPICS.ICALP.2019.150\">10.4230/LIPICS.ICALP.2019.150</a>.","apa":"Scheideler, C., &#38; Setzer, A. (2019). On the Complexity of Local Graph Transformations. In <i>Proceedings of the 46th International Colloquium on Automata, Languages, and Programming</i> (Vol. 132, pp. 150:1--150:14). Patras, Greece: Dagstuhl Publishing. <a href=\"https://doi.org/10.4230/LIPICS.ICALP.2019.150\">https://doi.org/10.4230/LIPICS.ICALP.2019.150</a>","ieee":"C. Scheideler and A. Setzer, “On the Complexity of Local Graph Transformations,” in <i>Proceedings of the 46th International Colloquium on Automata, Languages, and Programming</i>, Patras, Greece, 2019, vol. 132, pp. 150:1--150:14.","chicago":"Scheideler, Christian, and Alexander Setzer. “On the Complexity of Local Graph Transformations.” In <i>Proceedings of the 46th International Colloquium on Automata, Languages, and Programming</i>, 132:150:1--150:14. LIPIcs. Dagstuhl Publishing, 2019. <a href=\"https://doi.org/10.4230/LIPICS.ICALP.2019.150\">https://doi.org/10.4230/LIPICS.ICALP.2019.150</a>.","ama":"Scheideler C, Setzer A. On the Complexity of Local Graph Transformations. In: <i>Proceedings of the 46th International Colloquium on Automata, Languages, and Programming</i>. Vol 132. LIPIcs. Dagstuhl Publishing; 2019:150:1--150:14. doi:<a href=\"https://doi.org/10.4230/LIPICS.ICALP.2019.150\">10.4230/LIPICS.ICALP.2019.150</a>"},"intvolume":"       132","page":"150:1--150:14","publication_status":"published","has_accepted_license":"1","conference":{"start_date":"2019-07-09","name":"ICALP 2019","location":"Patras, Greece","end_date":"2019-07-12"},"doi":"10.4230/LIPICS.ICALP.2019.150","date_updated":"2022-01-06T06:50:45Z","author":[{"first_name":"Christian","full_name":"Scheideler, Christian","id":"20792","last_name":"Scheideler"},{"id":"11108","full_name":"Setzer, Alexander","last_name":"Setzer","first_name":"Alexander"}],"volume":132,"status":"public","type":"conference","file_date_updated":"2019-08-26T09:21:27Z","project":[{"name":"SFB 901","_id":"1"},{"_id":"5","name":"SFB 901 - Subproject A1"},{"_id":"2","name":"SFB 901 - Project Area A"}],"_id":"10586","user_id":"477","series_title":"LIPIcs","department":[{"_id":"79"}]},{"language":[{"iso":"eng"}],"ddc":["040"],"keyword":["distributed consensus","randomized algorithm","adaptive adversary","complexity lower bound"],"publication":"Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)","file":[{"relation":"main_file","success":1,"content_type":"application/pdf","file_id":"5215","file_name":"p173-robinson.pdf","access_level":"closed","file_size":1675407,"date_created":"2018-10-31T13:30:40Z","creator":"asetzer","date_updated":"2018-10-31T13:30:40Z"}],"abstract":[{"lang":"eng","text":"We study the consensus problem in a synchronous distributed system of n nodes under an adaptive adversary that has a slightly outdated view of the system and can block all incoming and outgoing communication of a constant fraction of the nodes in each round. Motivated by a result of Ben-Or and Bar-Joseph (1998), showing that any consensus algorithm that is resilient against a linear number of crash faults requires $\\tilde \\Omega(\\sqrt n)$ rounds in an n-node network against an adaptive adversary, we consider a late adaptive adversary, who has full knowledge of the network state at the beginning of the previous round and unlimited computational power, but is oblivious to the current state of the nodes. \r\n\r\nOur main contributions are randomized distributed algorithms that achieve consensus with high probability among all except a small constant fraction of the nodes (i.e., \"almost-everywhere'') against a late adaptive adversary who can block up to ε n$ nodes in each round, for a small constant ε >0$. Our first protocol achieves binary almost-everywhere consensus and also guarantees a decision on the majority input value, thus ensuring plurality consensus. We also present an algorithm that achieves the same time complexity for multi-value consensus. Both of our algorithms succeed in $O(log n)$ rounds with high probability, thus showing an exponential gap to the $\\tilde\\Omega(\\sqrt n)$ lower bound of Ben-Or and Bar-Joseph for strongly adaptive crash-failure adversaries, which can be strengthened to $\\Omega(n)$ when allowing the adversary to block nodes instead of permanently crashing them. Our algorithms are scalable to large systems as each node contacts only an (amortized) constant number of peers in each communication round. We show that our algorithms are optimal up to constant (resp.\\ sub-logarithmic) factors by proving that every almost-everywhere consensus protocol takes $\\Omega(log_d n)$ rounds in the worst case, where d is an upper bound on the number of communication requests initiated per node in each round. We complement our theoretical results with an experimental evaluation of the binary almost-everywhere consensus protocol revealing a short convergence time even against an adversary blocking a large fraction of nodes."}],"date_created":"2018-07-04T08:55:45Z","title":"Breaking the $\\tilde\\Omega(\\sqrt{n})$ Barrier: Fast Consensus under a Late Adversary","year":"2018","user_id":"11108","department":[{"_id":"79"},{"_id":"34"},{"_id":"7"}],"project":[{"_id":"1","name":"SFB 901"},{"name":"SFB 901 - Project Area C","_id":"4"},{"name":"SFB 901 - Subproject C1","_id":"13"}],"_id":"3422","file_date_updated":"2018-10-31T13:30:40Z","type":"conference","status":"public","author":[{"full_name":"Robinson, Peter","last_name":"Robinson","first_name":"Peter"},{"id":"20792","full_name":"Scheideler, Christian","last_name":"Scheideler","first_name":"Christian"},{"first_name":"Alexander","last_name":"Setzer","id":"11108","full_name":"Setzer, Alexander"}],"date_updated":"2022-01-06T06:59:16Z","conference":{"end_date":"2018-07-18","location":"Wien","name":"30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)","start_date":"2018-07-16"},"doi":"10.1145/3210377.3210399","publication_status":"accepted","publication_identifier":{"isbn":["978-1-4503-5799-9/18/07"]},"has_accepted_license":"1","citation":{"ama":"Robinson P, Scheideler C, Setzer A. Breaking the $\\tilde\\Omega(\\sqrt{n})$ Barrier: Fast Consensus under a Late Adversary. In: <i>Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)</i>. doi:<a href=\"https://doi.org/10.1145/3210377.3210399\">10.1145/3210377.3210399</a>","ieee":"P. Robinson, C. Scheideler, and A. Setzer, “Breaking the $\\tilde\\Omega(\\sqrt{n})$ Barrier: Fast Consensus under a Late Adversary,” in <i>Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)</i>, Wien.","chicago":"Robinson, Peter, Christian Scheideler, and Alexander Setzer. “Breaking the $\\tilde\\Omega(\\sqrt{n})$ Barrier: Fast Consensus under a Late Adversary.” In <i>Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)</i>, n.d. <a href=\"https://doi.org/10.1145/3210377.3210399\">https://doi.org/10.1145/3210377.3210399</a>.","mla":"Robinson, Peter, et al. “Breaking the $\\tilde\\Omega(\\sqrt{n})$ Barrier: Fast Consensus under a Late Adversary.” <i>Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)</i>, doi:<a href=\"https://doi.org/10.1145/3210377.3210399\">10.1145/3210377.3210399</a>.","bibtex":"@inproceedings{Robinson_Scheideler_Setzer, title={Breaking the $\\tilde\\Omega(\\sqrt{n})$ Barrier: Fast Consensus under a Late Adversary}, DOI={<a href=\"https://doi.org/10.1145/3210377.3210399\">10.1145/3210377.3210399</a>}, booktitle={Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)}, author={Robinson, Peter and Scheideler, Christian and Setzer, Alexander} }","short":"P. Robinson, C. Scheideler, A. Setzer, in: Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), n.d.","apa":"Robinson, P., Scheideler, C., &#38; Setzer, A. (n.d.). Breaking the $\\tilde\\Omega(\\sqrt{n})$ Barrier: Fast Consensus under a Late Adversary. In <i>Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)</i>. Wien. <a href=\"https://doi.org/10.1145/3210377.3210399\">https://doi.org/10.1145/3210377.3210399</a>"}},{"abstract":[{"lang":"eng","text":"We propose a distributed protocol for a queue, called Skueue, which spreads its data fairly onto multiple processes, avoiding bottlenecks in high throughput scenarios.\r\nSkueuecan be used in highly dynamic environments, through the addition of join and leave requests to the standard queue operations enqueue and dequeue.\r\nFurthermore Skueue satisfies sequential consistency in the asynchronous message passing model.\r\nScalability is achieved by aggregating multiple requests to a batch, which can then be processed in a distributed fashion without hurting the queue semantics.\r\nOperations in Skueue need a logarithmic number of rounds w.h.p. until they are processed, even under a high rate of incoming requests."}],"file":[{"content_type":"application/pdf","relation":"main_file","success":1,"date_created":"2018-10-31T13:29:26Z","creator":"mfeldma2","date_updated":"2018-10-31T13:29:26Z","file_id":"5212","file_name":"08425257.pdf","access_level":"closed","file_size":218420}],"publication":"Proceedings of the 32nd IEEE International Parallel & Distributed Processing Symposium (IPDPS)","ddc":["040"],"language":[{"iso":"eng"}],"external_id":{"arxiv":["1802.07504"]},"year":"2018","title":"Skueue: A Scalable and Sequentially Consistent Distributed Queue","publisher":"IEEE","date_created":"2018-02-01T14:00:36Z","status":"public","type":"conference","file_date_updated":"2018-10-31T13:29:26Z","project":[{"_id":"1","name":"SFB 901"},{"_id":"2","name":"SFB 901 - Project Area A"},{"name":"SFB 901 - Subproject A1","_id":"5"}],"_id":"1164","user_id":"23538","department":[{"_id":"79"}],"citation":{"ama":"Feldmann M, Scheideler C, Setzer A. Skueue: A Scalable and Sequentially Consistent Distributed Queue. In: <i>Proceedings of the 32nd IEEE International Parallel &#38; Distributed Processing Symposium (IPDPS)</i>. IEEE; 2018. doi:<a href=\"https://doi.org/10.1109/IPDPS.2018.00113\">10.1109/IPDPS.2018.00113</a>","ieee":"M. Feldmann, C. Scheideler, and A. Setzer, “Skueue: A Scalable and Sequentially Consistent Distributed Queue,” in <i>Proceedings of the 32nd IEEE International Parallel &#38; Distributed Processing Symposium (IPDPS)</i>, Vancouver, 2018.","chicago":"Feldmann, Michael, Christian Scheideler, and Alexander Setzer. “Skueue: A Scalable and Sequentially Consistent Distributed Queue.” In <i>Proceedings of the 32nd IEEE International Parallel &#38; Distributed Processing Symposium (IPDPS)</i>. IEEE, 2018. <a href=\"https://doi.org/10.1109/IPDPS.2018.00113\">https://doi.org/10.1109/IPDPS.2018.00113</a>.","bibtex":"@inproceedings{Feldmann_Scheideler_Setzer_2018, title={Skueue: A Scalable and Sequentially Consistent Distributed Queue}, DOI={<a href=\"https://doi.org/10.1109/IPDPS.2018.00113\">10.1109/IPDPS.2018.00113</a>}, booktitle={Proceedings of the 32nd IEEE International Parallel &#38; Distributed Processing Symposium (IPDPS)}, publisher={IEEE}, author={Feldmann, Michael and Scheideler, Christian and Setzer, Alexander}, year={2018} }","mla":"Feldmann, Michael, et al. “Skueue: A Scalable and Sequentially Consistent Distributed Queue.” <i>Proceedings of the 32nd IEEE International Parallel &#38; Distributed Processing Symposium (IPDPS)</i>, IEEE, 2018, doi:<a href=\"https://doi.org/10.1109/IPDPS.2018.00113\">10.1109/IPDPS.2018.00113</a>.","short":"M. Feldmann, C. Scheideler, A. Setzer, in: Proceedings of the 32nd IEEE International Parallel &#38; Distributed Processing Symposium (IPDPS), IEEE, 2018.","apa":"Feldmann, M., Scheideler, C., &#38; Setzer, A. (2018). Skueue: A Scalable and Sequentially Consistent Distributed Queue. In <i>Proceedings of the 32nd IEEE International Parallel &#38; Distributed Processing Symposium (IPDPS)</i>. Vancouver: IEEE. <a href=\"https://doi.org/10.1109/IPDPS.2018.00113\">https://doi.org/10.1109/IPDPS.2018.00113</a>"},"has_accepted_license":"1","doi":"10.1109/IPDPS.2018.00113","conference":{"location":"Vancouver","end_date":"2018-5-24","start_date":"2018-5-22","name":"32nd IEEE International Parallel & Distributed Processing Symposium (IPDPS)"},"date_updated":"2022-01-06T06:51:05Z","author":[{"full_name":"Feldmann, Michael","id":"23538","last_name":"Feldmann","first_name":"Michael"},{"first_name":"Christian","id":"20792","full_name":"Scheideler, Christian","last_name":"Scheideler"},{"first_name":"Alexander","full_name":"Setzer, Alexander","id":"11108","last_name":"Setzer"}]},{"type":"working_paper","file":[{"access_level":"closed","file_name":"draft-2018.pdf","file_id":"6435","file_size":470968,"date_created":"2018-12-31T09:55:30Z","creator":"jbobolz","date_updated":"2018-12-31T09:55:30Z","relation":"main_file","success":1,"content_type":"application/pdf"}],"status":"public","abstract":[{"lang":"eng","text":"In this paper, we investigate the use of trusted execution environments (TEEs, such as Intel's SGX) for an anonymous communication infrastructure over untrusted networks.\r\nFor this, we present the general idea of exploiting trusted execution environments for the purpose of anonymous communication, including a continuous-time security framework that models strong anonymity guarantees in the presence of an adversary that observes all network traffic and can adaptively corrupt a constant fraction of participating nodes.\r\nIn our framework, a participating node can generate a number of unlinkable pseudonyms. Messages are sent from and to pseudonyms, allowing both senders and receivers of messages to remain anonymous. We introduce a concrete construction, which shows viability of our TEE-based approach to anonymous communication. The construction draws from techniques from cryptography and overlay networks. \r\nOur techniques are very general and can be used as a basis for future constructions with similar goals."}],"user_id":"27207","department":[{"_id":"7"},{"_id":"64"},{"_id":"79"}],"project":[{"name":"SFB 901","_id":"1"},{"name":"SFB 901 - Project Area C","_id":"4"},{"name":"SFB 901 - Subproject C1","_id":"13"}],"_id":"5820","file_date_updated":"2018-12-31T09:55:30Z","language":[{"iso":"eng"}],"ddc":["000"],"publication_status":"draft","has_accepted_license":"1","citation":{"bibtex":"@book{Blömer_Bobolz_Scheideler_Setzer, title={Provably Anonymous Communication Based on Trusted Execution Environments}, author={Blömer, Johannes and Bobolz, Jan and Scheideler, Christian and Setzer, Alexander} }","short":"J. Blömer, J. Bobolz, C. Scheideler, A. Setzer, Provably Anonymous Communication Based on Trusted Execution Environments, n.d.","mla":"Blömer, Johannes, et al. <i>Provably Anonymous Communication Based on Trusted Execution Environments</i>.","apa":"Blömer, J., Bobolz, J., Scheideler, C., &#38; Setzer, A. (n.d.). <i>Provably Anonymous Communication Based on Trusted Execution Environments</i>.","ama":"Blömer J, Bobolz J, Scheideler C, Setzer A. <i>Provably Anonymous Communication Based on Trusted Execution Environments</i>.","chicago":"Blömer, Johannes, Jan Bobolz, Christian Scheideler, and Alexander Setzer. <i>Provably Anonymous Communication Based on Trusted Execution Environments</i>, n.d.","ieee":"J. Blömer, J. Bobolz, C. Scheideler, and A. Setzer, <i>Provably Anonymous Communication Based on Trusted Execution Environments</i>. ."},"year":"2018","date_created":"2018-11-25T08:08:40Z","author":[{"full_name":"Blömer, Johannes","id":"23","last_name":"Blömer","first_name":"Johannes"},{"first_name":"Jan","last_name":"Bobolz","full_name":"Bobolz, Jan","id":"27207"},{"full_name":"Scheideler, Christian","id":"20792","last_name":"Scheideler","first_name":"Christian"},{"first_name":"Alexander","id":"11108","full_name":"Setzer, Alexander","last_name":"Setzer"}],"date_updated":"2022-01-06T07:02:43Z","title":"Provably Anonymous Communication Based on Trusted Execution Environments"},{"type":"conference","publication":"Proceedings of the 4th International Symposium on Algorithmic Aspects of Cloud Computing (ALGOCLOUD)","abstract":[{"text":"We present a peer-to-peer network that supports the efficient processing of orthogonal range queries $R=\\bigtimes_{i=1}^{d}[a_i,\\,b_i]$ in a $d$-dimensional point space.\\\\\r\nThe  network is the same for each dimension, namely a distance halving network like the one introduced by Naor and Wieder (ACM TALG'07).\r\nWe show how to execute such range queries using $\\mathcal{O}\\left(2^{d'}d\\,\\log m + d\\,|R|\\right)$ hops (and the same number of messages) in total. Here $[m]^d$ is the ground set, $|R|$ is the size and $d'$ the dimension of the queried range.\r\nFurthermore, if the peers form a distributed network, the query can be answered in $\\mathcal{O}\\left(d\\,\\log m + d\\,\\sum_{i=1}^{d}(b_i-a_i+1)\\right)$ communication rounds.\r\nOur algorithms are based on a mapping of the Hilbert Curve through $[m]^d$ to the peers.","lang":"eng"}],"file":[{"content_type":"application/pdf","success":1,"relation":"main_file","date_updated":"2018-11-27T10:03:33Z","creator":"tillk","date_created":"2018-11-27T10:03:33Z","file_size":1122875,"file_name":"A Peer-to-Peer based Cloud Storage supporting orthogonal Range Queries of arbitrary Dimension.pdf","file_id":"5863","access_level":"closed"}],"status":"public","project":[{"name":"SFB 901","_id":"1"},{"_id":"2","name":"SFB 901 - Project Area A"},{"_id":"5","name":"SFB 901 - Subproject A1"}],"_id":"4375","user_id":"14955","department":[{"_id":"63"},{"_id":"79"}],"ddc":["000"],"keyword":["Distributed Storage","Multi-Dimensional Range Queries","Peer-to-Peer","Hilbert Curve"],"language":[{"iso":"eng"}],"file_date_updated":"2018-11-27T10:03:33Z","has_accepted_license":"1","year":"2018","citation":{"short":"M. Benter, T. Knollmann, F. Meyer auf der Heide, A. Setzer, J. Sundermeier, in: Proceedings of the 4th International Symposium on Algorithmic Aspects of Cloud Computing (ALGOCLOUD), 2018.","bibtex":"@inproceedings{Benter_Knollmann_Meyer auf der Heide_Setzer_Sundermeier_2018, title={A Peer-to-Peer based Cloud Storage supporting orthogonal Range Queries of arbitrary Dimension}, DOI={<a href=\"https://doi.org/10.1007/978-3-030-19759-9_4\">10.1007/978-3-030-19759-9_4</a>}, booktitle={Proceedings of the 4th International Symposium on Algorithmic Aspects of Cloud Computing (ALGOCLOUD)}, author={Benter, Markus and Knollmann, Till and Meyer auf der Heide, Friedhelm and Setzer, Alexander and Sundermeier, Jannik}, year={2018} }","mla":"Benter, Markus, et al. “A Peer-to-Peer Based Cloud Storage Supporting Orthogonal Range Queries of Arbitrary Dimension.” <i>Proceedings of the 4th International Symposium on Algorithmic Aspects of Cloud Computing (ALGOCLOUD)</i>, 2018, doi:<a href=\"https://doi.org/10.1007/978-3-030-19759-9_4\">10.1007/978-3-030-19759-9_4</a>.","apa":"Benter, M., Knollmann, T., Meyer auf der Heide, F., Setzer, A., &#38; Sundermeier, J. (2018). A Peer-to-Peer based Cloud Storage supporting orthogonal Range Queries of arbitrary Dimension. In <i>Proceedings of the 4th International Symposium on Algorithmic Aspects of Cloud Computing (ALGOCLOUD)</i>. Helsinki. <a href=\"https://doi.org/10.1007/978-3-030-19759-9_4\">https://doi.org/10.1007/978-3-030-19759-9_4</a>","ieee":"M. Benter, T. Knollmann, F. Meyer auf der Heide, A. Setzer, and J. Sundermeier, “A Peer-to-Peer based Cloud Storage supporting orthogonal Range Queries of arbitrary Dimension,” in <i>Proceedings of the 4th International Symposium on Algorithmic Aspects of Cloud Computing (ALGOCLOUD)</i>, Helsinki, 2018.","chicago":"Benter, Markus, Till Knollmann, Friedhelm Meyer auf der Heide, Alexander Setzer, and Jannik Sundermeier. “A Peer-to-Peer Based Cloud Storage Supporting Orthogonal Range Queries of Arbitrary Dimension.” In <i>Proceedings of the 4th International Symposium on Algorithmic Aspects of Cloud Computing (ALGOCLOUD)</i>, 2018. <a href=\"https://doi.org/10.1007/978-3-030-19759-9_4\">https://doi.org/10.1007/978-3-030-19759-9_4</a>.","ama":"Benter M, Knollmann T, Meyer auf der Heide F, Setzer A, Sundermeier J. A Peer-to-Peer based Cloud Storage supporting orthogonal Range Queries of arbitrary Dimension. In: <i>Proceedings of the 4th International Symposium on Algorithmic Aspects of Cloud Computing (ALGOCLOUD)</i>. ; 2018. doi:<a href=\"https://doi.org/10.1007/978-3-030-19759-9_4\">10.1007/978-3-030-19759-9_4</a>"},"date_updated":"2022-01-06T07:01:00Z","date_created":"2018-09-11T05:26:59Z","author":[{"full_name":"Benter, Markus","last_name":"Benter","first_name":"Markus"},{"first_name":"Till","last_name":"Knollmann","orcid":"0000-0003-2014-4696","full_name":"Knollmann, Till","id":"39241"},{"last_name":"Meyer auf der Heide","id":"15523","full_name":"Meyer auf der Heide, Friedhelm","first_name":"Friedhelm"},{"id":"11108","full_name":"Setzer, Alexander","last_name":"Setzer","first_name":"Alexander"},{"id":"38705","full_name":"Sundermeier, Jannik","last_name":"Sundermeier","first_name":"Jannik"}],"title":"A Peer-to-Peer based Cloud Storage supporting orthogonal Range Queries of arbitrary Dimension","conference":{"start_date":"2018-08-20","name":"4th International Symposium on Algorithmic Aspects of Cloud Computing (ALGOCLOUD)","location":"Helsinki","end_date":"2018-08-21"},"doi":"10.1007/978-3-030-19759-9_4"},{"status":"public","type":"conference","file_date_updated":"2018-10-31T16:09:48Z","_id":"5216","project":[{"_id":"1","name":"SFB 901"},{"name":"SFB 901 - Project Area C","_id":"4"},{"name":"SFB 901 - Subproject C1","_id":"13"}],"department":[{"_id":"79"}],"user_id":"11108","citation":{"apa":"Scheideler, C., &#38; Setzer, A. (2018). Relays: A New Approach for the Finite Departure Problem in Overlay Networks. In <i>Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2018)</i>. Tokyo, Japan. <a href=\"https://doi.org/10.1007/978-3-030-03232-6_16\">https://doi.org/10.1007/978-3-030-03232-6_16</a>","bibtex":"@inproceedings{Scheideler_Setzer_2018, title={Relays: A New Approach for the Finite Departure Problem in Overlay Networks}, DOI={<a href=\"https://doi.org/10.1007/978-3-030-03232-6_16\">10.1007/978-3-030-03232-6_16</a>}, booktitle={Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2018)}, author={Scheideler, Christian and Setzer, Alexander}, year={2018} }","mla":"Scheideler, Christian, and Alexander Setzer. “Relays: A New Approach for the Finite Departure Problem in Overlay Networks.” <i>Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2018)</i>, 2018, doi:<a href=\"https://doi.org/10.1007/978-3-030-03232-6_16\">10.1007/978-3-030-03232-6_16</a>.","short":"C. Scheideler, A. Setzer, in: Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2018), 2018.","ieee":"C. Scheideler and A. Setzer, “Relays: A New Approach for the Finite Departure Problem in Overlay Networks,” in <i>Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2018)</i>, Tokyo, Japan, 2018.","chicago":"Scheideler, Christian, and Alexander Setzer. “Relays: A New Approach for the Finite Departure Problem in Overlay Networks.” In <i>Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2018)</i>, 2018. <a href=\"https://doi.org/10.1007/978-3-030-03232-6_16\">https://doi.org/10.1007/978-3-030-03232-6_16</a>.","ama":"Scheideler C, Setzer A. Relays: A New Approach for the Finite Departure Problem in Overlay Networks. In: <i>Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2018)</i>. ; 2018. doi:<a href=\"https://doi.org/10.1007/978-3-030-03232-6_16\">10.1007/978-3-030-03232-6_16</a>"},"has_accepted_license":"1","publication_status":"published","doi":"10.1007/978-3-030-03232-6_16","conference":{"location":"Tokyo, Japan","name":"20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2018)"},"date_updated":"2022-01-06T07:01:47Z","author":[{"first_name":"Christian","last_name":"Scheideler","full_name":"Scheideler, Christian","id":"20792"},{"first_name":"Alexander","last_name":"Setzer","id":"11108","full_name":"Setzer, Alexander"}],"abstract":[{"text":"A fundamental problem for overlay networks is to safely exclude leaving nodes, i.e., the nodes requesting to leave the overlay network are excluded from it without affecting its connectivity. To rigorously study self-stabilizing solutions to this problem, the Finite Departure Problem (FDP) has been proposed [9]. In the FDP we are given a network of processes in an arbitrary state, and the goal is to eventually arrive at (and stay in) a state in which all leaving processes irrevocably decided to leave the system while for all weakly-connected components in the initial overlay network, all staying processes in that component will still form a weakly connected component. In the standard interconnection model, the FDP is known to be unsolvable by local control protocols, so oracles have been investigated that allow the problem to be solved [9]. To avoid the use of oracles, we introduce a new interconnection model based on relays. Despite the relay model appearing to be rather restrictive, we show that it is universal, i.e., it is possible to transform any weakly-connected topology into any other weakly-connected topology, which is important for being a useful interconnection model for overlay networks. Apart from this, our model allows processes to grant and revoke access rights, which is why we believe it to be of interest beyond the scope of this paper. We show how to implement the relay layer in a self-stabilizing way and identify properties protocols need to satisfy so that the relay layer can recover while serving protocol requests.","lang":"eng"}],"file":[{"relation":"main_file","content_type":"application/pdf","file_name":"Scheideler-Setzer2018_Chapter_RelaysANewApproachForTheFinite.pdf","access_level":"closed","file_id":"5223","file_size":369818,"creator":"asetzer","date_created":"2018-10-31T15:51:45Z","date_updated":"2018-10-31T16:09:48Z"}],"publication":"Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2018)","ddc":["040"],"language":[{"iso":"eng"}],"year":"2018","title":"Relays: A New Approach for the Finite Departure Problem in Overlay Networks","date_created":"2018-10-31T13:33:05Z"},{"publisher":"Springer","date_created":"2018-10-31T15:44:30Z","title":"On Underlay-Aware Self-Stabilizing Overlay Networks","year":"2018","ddc":["040"],"language":[{"iso":"eng"}],"publication":"Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2018)","abstract":[{"text":"We present a self-stabilizing protocol for an overlay network that constructs the Minimum Spanning Tree (MST) for an underlay that is modeled by a weighted tree. The weight of an overlay edge between two nodes is the weighted length of their shortest path in the tree. We rigorously prove that our protocol works correctly under asynchronous and non-FIFO message delivery. Further, the protocol stabilizes after O(N^2) asynchronous rounds where N is the number of nodes in the overlay. ","lang":"eng"}],"file":[{"file_size":367812,"file_id":"5224","file_name":"sss18_camera.pdf","access_level":"closed","date_updated":"2018-10-31T15:59:26Z","creator":"thgoette","date_created":"2018-10-31T15:59:26Z","success":1,"relation":"main_file","content_type":"application/pdf"}],"date_updated":"2022-01-06T07:01:47Z","volume":11201,"author":[{"first_name":"Thorsten","last_name":"Götte","id":"34727","full_name":"Götte, Thorsten"},{"id":"20792","full_name":"Scheideler, Christian","last_name":"Scheideler","first_name":"Christian"},{"id":"11108","full_name":"Setzer, Alexander","last_name":"Setzer","first_name":"Alexander"}],"conference":{"location":"Tokyo, Japan","name":" 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2018)"},"has_accepted_license":"1","intvolume":"     11201","page":"50-64","citation":{"bibtex":"@inproceedings{Götte_Scheideler_Setzer_2018, series={Lecture Notes in Computer Science}, title={On Underlay-Aware Self-Stabilizing Overlay Networks}, volume={11201}, booktitle={Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2018)}, publisher={Springer}, author={Götte, Thorsten and Scheideler, Christian and Setzer, Alexander}, year={2018}, pages={50–64}, collection={Lecture Notes in Computer Science} }","mla":"Götte, Thorsten, et al. “On Underlay-Aware Self-Stabilizing Overlay Networks.” <i>Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2018)</i>, vol. 11201, Springer, 2018, pp. 50–64.","short":"T. Götte, C. Scheideler, A. Setzer, in: Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2018), Springer, 2018, pp. 50–64.","apa":"Götte, T., Scheideler, C., &#38; Setzer, A. (2018). On Underlay-Aware Self-Stabilizing Overlay Networks. In <i>Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2018)</i> (Vol. 11201, pp. 50–64). Tokyo, Japan: Springer.","chicago":"Götte, Thorsten, Christian Scheideler, and Alexander Setzer. “On Underlay-Aware Self-Stabilizing Overlay Networks.” In <i>Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2018)</i>, 11201:50–64. Lecture Notes in Computer Science. Springer, 2018.","ieee":"T. Götte, C. Scheideler, and A. Setzer, “On Underlay-Aware Self-Stabilizing Overlay Networks,” in <i>Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2018)</i>, Tokyo, Japan, 2018, vol. 11201, pp. 50–64.","ama":"Götte T, Scheideler C, Setzer A. On Underlay-Aware Self-Stabilizing Overlay Networks. In: <i>Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2018)</i>. Vol 11201. Lecture Notes in Computer Science. Springer; 2018:50-64."},"_id":"5222","project":[{"_id":"1","name":"SFB 901"},{"name":"SFB 901 - Project Area A","_id":"2"},{"name":"SFB 901 - Subproject A1","_id":"5"}],"department":[{"_id":"79"}],"user_id":"477","series_title":"Lecture Notes in Computer Science","file_date_updated":"2018-10-31T15:59:26Z","type":"conference","status":"public"},{"abstract":[{"lang":"eng","text":"For overlay networks, the ability to recover from a variety of problems like membership changes or faults is a key element to preserve their functionality. In recent years, various self-stabilizing overlay networks have been proposed that have the advantage of being able to recover from any illegal state. However, the vast majority of these networks cannot give any guarantees on its functionality while the recovery process is going on. We are especially interested in searchability, i.e., the functionality that search messages for a specific identifier are answered successfully if a node with that identifier exists in the network. We investigate overlay networks that are not only self-stabilizing but that also ensure that monotonic searchability is maintained while the recovery process is going on, as long as there are no corrupted messages in the system. More precisely, once a search message from node u to another node v is successfully delivered, all future search messages from u to v succeed as well. Monotonic searchability was recently introduced in OPODIS 2015, in which the authors provide a solution for a simple line topology.We present the first universal approach to maintain monotonic searchability that is applicable to a wide range of topologies. As the base for our approach, we introduce a set of primitives for manipulating overlay networks that allows us to maintain searchability and show how existing protocols can be transformed to use theses primitives.We complement this result with a generic search protocol that together with the use of our primitives guarantees monotonic searchability.As an additional feature, searching existing nodes with the generic search protocol is as fast as searching a node with any other fixed routing protocol once the topology has stabilized."}],"status":"public","file":[{"file_id":"1558","access_level":"closed","file_name":"142-SchSetStrDISC16.pdf","file_size":209638,"date_created":"2018-03-21T12:59:29Z","creator":"florida","date_updated":"2018-03-21T12:59:29Z","relation":"main_file","success":1,"content_type":"application/pdf"}],"publication":"Proceedings of the 30th International Symposium on Distributed Computing (DISC)","type":"conference","ddc":["040"],"file_date_updated":"2018-03-21T12:59:29Z","language":[{"iso":"eng"}],"_id":"142","project":[{"name":"SFB 901","_id":"1"},{"_id":"5","name":"SFB 901 - Subprojekt A1"},{"_id":"2","name":"SFB 901 - Project Area A"}],"department":[{"_id":"79"}],"series_title":"LNCS","user_id":"477","year":"2016","page":"71--84","citation":{"mla":"Scheideler, Christian, et al. “Towards a Universal Approach for Monotonic Searchability in Self-Stabilizing Overlay Networks.” <i>Proceedings of the 30th International Symposium on Distributed Computing (DISC)</i>, 2016, pp. 71--84, doi:<a href=\"https://doi.org/10.1007/978-3-662-53426-7_6\">10.1007/978-3-662-53426-7_6</a>.","short":"C. Scheideler, A. Setzer, T.F. Strothmann, in: Proceedings of the 30th International Symposium on Distributed Computing (DISC), 2016, pp. 71--84.","bibtex":"@inproceedings{Scheideler_Setzer_Strothmann_2016, series={LNCS}, title={Towards a Universal Approach for Monotonic Searchability in Self-stabilizing Overlay Networks}, DOI={<a href=\"https://doi.org/10.1007/978-3-662-53426-7_6\">10.1007/978-3-662-53426-7_6</a>}, booktitle={Proceedings of the 30th International Symposium on Distributed Computing (DISC)}, author={Scheideler, Christian and Setzer, Alexander and Strothmann, Thim Frederik}, year={2016}, pages={71--84}, collection={LNCS} }","apa":"Scheideler, C., Setzer, A., &#38; Strothmann, T. F. (2016). Towards a Universal Approach for Monotonic Searchability in Self-stabilizing Overlay Networks. In <i>Proceedings of the 30th International Symposium on Distributed Computing (DISC)</i> (pp. 71--84). <a href=\"https://doi.org/10.1007/978-3-662-53426-7_6\">https://doi.org/10.1007/978-3-662-53426-7_6</a>","ama":"Scheideler C, Setzer A, Strothmann TF. Towards a Universal Approach for Monotonic Searchability in Self-stabilizing Overlay Networks. In: <i>Proceedings of the 30th International Symposium on Distributed Computing (DISC)</i>. LNCS. ; 2016:71--84. doi:<a href=\"https://doi.org/10.1007/978-3-662-53426-7_6\">10.1007/978-3-662-53426-7_6</a>","chicago":"Scheideler, Christian, Alexander Setzer, and Thim Frederik Strothmann. “Towards a Universal Approach for Monotonic Searchability in Self-Stabilizing Overlay Networks.” In <i>Proceedings of the 30th International Symposium on Distributed Computing (DISC)</i>, 71--84. LNCS, 2016. <a href=\"https://doi.org/10.1007/978-3-662-53426-7_6\">https://doi.org/10.1007/978-3-662-53426-7_6</a>.","ieee":"C. Scheideler, A. Setzer, and T. F. Strothmann, “Towards a Universal Approach for Monotonic Searchability in Self-stabilizing Overlay Networks,” in <i>Proceedings of the 30th International Symposium on Distributed Computing (DISC)</i>, 2016, pp. 71--84."},"has_accepted_license":"1","title":"Towards a Universal Approach for Monotonic Searchability in Self-stabilizing Overlay Networks","doi":"10.1007/978-3-662-53426-7_6","date_updated":"2022-01-06T06:51:56Z","date_created":"2017-10-17T12:41:19Z","author":[{"full_name":"Scheideler, Christian","id":"20792","last_name":"Scheideler","first_name":"Christian"},{"last_name":"Setzer","full_name":"Setzer, Alexander","id":"11108","first_name":"Alexander"},{"id":"11319","full_name":"Strothmann, Thim Frederik","last_name":"Strothmann","first_name":"Thim Frederik"}]},{"type":"conference","publication":"Proceedings of the 19th International Conference on Principles of Distributed Systems (OPODIS)","abstract":[{"lang":"eng","text":"Distributed applications are commonly based on overlay networks interconnecting their sites so that they can exchange information. For these overlay networks to preserve their functionality, they should be able to recover from various problems like membership changes or faults. Various self-stabilizing overlay networks have already been proposed in recent years, which have the advantage of being able to recover from any illegal state, but none of these networks can give any guarantees on its functionality while the recovery process is going on. We initiate research on overlay networks that are not only self-stabilizing but that also ensure that searchability is maintained while the recovery process is going on, as long as there are no corrupted messages in the system. More precisely, once a search message from node u to another node v is successfully delivered, all future search messages from u to v succeed as well. We call this property monotonic searchability. We show that in general it is impossible to provide monotonic searchability if corrupted messages are present in the system, which justifies the restriction to system states without corrupted messages. Furthermore, we provide a self-stabilizing protocol for the line for which we can also show monotonic searchability. It turns out that even for the line it is non-trivial to achieve this property. Additionally, we extend our protocol to deal with node departures in terms of the Finite Departure Problem of Foreback et. al (SSS 2014). This makes our protocol even capable of handling node dynamics."}],"file":[{"date_created":"2018-03-21T10:28:21Z","creator":"florida","date_updated":"2018-03-21T10:28:21Z","file_name":"241-ScheidelerSetzerStrothmann2015.pdf","file_id":"1497","access_level":"closed","file_size":692363,"content_type":"application/pdf","relation":"main_file","success":1}],"status":"public","project":[{"_id":"1","name":"SFB 901"},{"_id":"5","name":"SFB 901 - Subprojekt A1"},{"_id":"2","name":"SFB 901 - Project Area A"}],"_id":"241","user_id":"477","series_title":"Leibniz International Proceedings in Informatics (LIPIcs)","department":[{"_id":"79"}],"ddc":["040"],"file_date_updated":"2018-03-21T10:28:21Z","language":[{"iso":"eng"}],"has_accepted_license":"1","year":"2015","citation":{"ama":"Scheideler C, Setzer A, Strothmann TF. Towards Establishing Monotonic Searchability in Self-Stabilizing Data Structures. In: <i>Proceedings of the 19th International Conference on Principles of Distributed Systems (OPODIS)</i>. Leibniz International Proceedings in Informatics (LIPIcs). ; 2015. doi:<a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2015.24\">10.4230/LIPIcs.OPODIS.2015.24</a>","ieee":"C. Scheideler, A. Setzer, and T. F. Strothmann, “Towards Establishing Monotonic Searchability in Self-Stabilizing Data Structures,” in <i>Proceedings of the 19th International Conference on Principles of Distributed Systems (OPODIS)</i>, 2015.","chicago":"Scheideler, Christian, Alexander Setzer, and Thim Frederik Strothmann. “Towards Establishing Monotonic Searchability in Self-Stabilizing Data Structures.” In <i>Proceedings of the 19th International Conference on Principles of Distributed Systems (OPODIS)</i>. Leibniz International Proceedings in Informatics (LIPIcs), 2015. <a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2015.24\">https://doi.org/10.4230/LIPIcs.OPODIS.2015.24</a>.","mla":"Scheideler, Christian, et al. “Towards Establishing Monotonic Searchability in Self-Stabilizing Data Structures.” <i>Proceedings of the 19th International Conference on Principles of Distributed Systems (OPODIS)</i>, 2015, doi:<a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2015.24\">10.4230/LIPIcs.OPODIS.2015.24</a>.","bibtex":"@inproceedings{Scheideler_Setzer_Strothmann_2015, series={Leibniz International Proceedings in Informatics (LIPIcs)}, title={Towards Establishing Monotonic Searchability in Self-Stabilizing Data Structures}, DOI={<a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2015.24\">10.4230/LIPIcs.OPODIS.2015.24</a>}, booktitle={Proceedings of the 19th International Conference on Principles of Distributed Systems (OPODIS)}, author={Scheideler, Christian and Setzer, Alexander and Strothmann, Thim Frederik}, year={2015}, collection={Leibniz International Proceedings in Informatics (LIPIcs)} }","short":"C. Scheideler, A. Setzer, T.F. Strothmann, in: Proceedings of the 19th International Conference on Principles of Distributed Systems (OPODIS), 2015.","apa":"Scheideler, C., Setzer, A., &#38; Strothmann, T. F. (2015). Towards Establishing Monotonic Searchability in Self-Stabilizing Data Structures. In <i>Proceedings of the 19th International Conference on Principles of Distributed Systems (OPODIS)</i>. <a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2015.24\">https://doi.org/10.4230/LIPIcs.OPODIS.2015.24</a>"},"date_updated":"2022-01-06T06:56:07Z","date_created":"2017-10-17T12:41:39Z","author":[{"first_name":"Christian","last_name":"Scheideler","full_name":"Scheideler, Christian","id":"20792"},{"first_name":"Alexander","last_name":"Setzer","full_name":"Setzer, Alexander","id":"11108"},{"last_name":"Strothmann","full_name":"Strothmann, Thim Frederik","id":"11319","first_name":"Thim Frederik"}],"title":"Towards Establishing Monotonic Searchability in Self-Stabilizing Data Structures","doi":"10.4230/LIPIcs.OPODIS.2015.24"},{"year":"2014","citation":{"apa":"Scheideler, C., Setzer, A., &#38; Eikel, M. (2014). RoBuSt: A Crash-Failure-Resistant Distributed Storage System. In <i>Proceedings of the 18th International Conference on Principles of Distributed Systems (OPODIS)</i> (pp. 107--122). <a href=\"https://doi.org/10.1007/978-3-319-14472-6_8\">https://doi.org/10.1007/978-3-319-14472-6_8</a>","short":"C. Scheideler, A. Setzer, M. Eikel, in: Proceedings of the 18th International Conference on Principles of Distributed Systems (OPODIS), 2014, pp. 107--122.","bibtex":"@inproceedings{Scheideler_Setzer_Eikel_2014, series={LNCS}, title={RoBuSt: A Crash-Failure-Resistant Distributed Storage System}, DOI={<a href=\"https://doi.org/10.1007/978-3-319-14472-6_8\">10.1007/978-3-319-14472-6_8</a>}, booktitle={Proceedings of the 18th International Conference on Principles of Distributed Systems (OPODIS)}, author={Scheideler, Christian and Setzer, Alexander and Eikel, Martina}, year={2014}, pages={107--122}, collection={LNCS} }","mla":"Scheideler, Christian, et al. “RoBuSt: A Crash-Failure-Resistant Distributed Storage System.” <i>Proceedings of the 18th International Conference on Principles of Distributed Systems (OPODIS)</i>, 2014, pp. 107--122, doi:<a href=\"https://doi.org/10.1007/978-3-319-14472-6_8\">10.1007/978-3-319-14472-6_8</a>.","ama":"Scheideler C, Setzer A, Eikel M. RoBuSt: A Crash-Failure-Resistant Distributed Storage System. In: <i>Proceedings of the 18th International Conference on Principles of Distributed Systems (OPODIS)</i>. LNCS. ; 2014:107--122. doi:<a href=\"https://doi.org/10.1007/978-3-319-14472-6_8\">10.1007/978-3-319-14472-6_8</a>","chicago":"Scheideler, Christian, Alexander Setzer, and Martina Eikel. “RoBuSt: A Crash-Failure-Resistant Distributed Storage System.” In <i>Proceedings of the 18th International Conference on Principles of Distributed Systems (OPODIS)</i>, 107--122. LNCS, 2014. <a href=\"https://doi.org/10.1007/978-3-319-14472-6_8\">https://doi.org/10.1007/978-3-319-14472-6_8</a>.","ieee":"C. Scheideler, A. Setzer, and M. Eikel, “RoBuSt: A Crash-Failure-Resistant Distributed Storage System,” in <i>Proceedings of the 18th International Conference on Principles of Distributed Systems (OPODIS)</i>, 2014, pp. 107--122."},"page":"107--122","has_accepted_license":"1","title":"RoBuSt: A Crash-Failure-Resistant Distributed Storage System","doi":"10.1007/978-3-319-14472-6_8","date_updated":"2022-01-06T06:59:31Z","author":[{"first_name":"Christian","last_name":"Scheideler","full_name":"Scheideler, Christian","id":"20792"},{"first_name":"Alexander","full_name":"Setzer, Alexander","id":"11108","last_name":"Setzer"},{"first_name":"Martina","last_name":"Eikel","full_name":"Eikel, Martina"}],"date_created":"2017-10-17T12:42:04Z","abstract":[{"text":"In this work we present the first distributed storage system that is provably robust against crash failures issued by an adaptive adversary, i.e., for each batch of requests the adversary can decide based on the entire system state which servers will be unavailable for that batch of requests. Despite up to \\gamma n^{1/\\log\\log n} crashed servers, with \\gamma>0 constant and n denoting the number of servers, our system can correctly process any batch of lookup and write requests (with at most a polylogarithmic number of requests issued at each non-crashed server) in at most a polylogarithmic number of communication rounds, with at most polylogarithmic time and work at each server and only a logarithmic storage overhead. Our system is based on previous work by Eikel and Scheideler (SPAA 2013), who presented IRIS, a distributed information system that is provably robust against the same kind of crash failures. However, IRIS is only able to serve lookup requests. Handling both lookup and write requests has turned out to require major changes in the design of IRIS.","lang":"eng"}],"file":[{"relation":"main_file","success":1,"content_type":"application/pdf","file_id":"1401","access_level":"closed","file_name":"371-RoBuSt-OPODIS.pdf","file_size":269941,"creator":"florida","date_created":"2018-03-20T07:16:32Z","date_updated":"2018-03-20T07:16:32Z"}],"status":"public","type":"conference","publication":"Proceedings of the 18th International Conference on Principles of Distributed Systems (OPODIS)","ddc":["040"],"file_date_updated":"2018-03-20T07:16:32Z","project":[{"name":"SFB 901","_id":"1"},{"_id":"13","name":"SFB 901 - Subprojekt C1"},{"_id":"4","name":"SFB 901 - Project Area C"}],"_id":"371","user_id":"15504","series_title":"LNCS","department":[{"_id":"79"}]},{"file":[{"success":1,"relation":"main_file","content_type":"application/pdf","file_size":365818,"file_id":"1381","access_level":"closed","file_name":"397-WAOA14_01.pdf","date_updated":"2018-03-20T06:58:44Z","creator":"florida","date_created":"2018-03-20T06:58:44Z"}],"status":"public","abstract":[{"text":"We present a factor $14D^2$ approximation algorithm for the minimum linear arrangement problem on series-parallel graphs, where $D$ is the maximum degree in the graph. Given a suitable decomposition of the graph, our algorithm runs in time $O(|E|)$ and is very easy to implement. Its divide-and-conquer approach allows for an effective parallelization. Note that a suitable decomposition can also be computed in time $O(|E|\\log{|E|})$ (or even $O(\\log{|E|}\\log^*{|E|})$ on an EREW PRAM using $O(|E|)$ processors). For the proof of the approximation ratio, we use a sophisticated charging method that uses techniques similar to amortized analysis in advanced data structures. On general graphs, the minimum linear arrangement problem is known to be NP-hard. To the best of our knowledge, the minimum linear arrangement problem on series-parallel graphs has not been studied before.","lang":"eng"}],"type":"conference","publication":"Proceedings of the 12th Workshop on Approximation and Online Algorithms (WAOA)","file_date_updated":"2018-03-20T06:58:44Z","ddc":["040"],"series_title":"LNCS","user_id":"15504","department":[{"_id":"79"}],"project":[{"name":"SFB 901","_id":"1"},{"_id":"5","name":"SFB 901 - Subprojekt A1"},{"_id":"2","name":"SFB 901 - Project Area A"}],"_id":"397","citation":{"apa":"Scheideler, C., Eikel, M., &#38; Setzer, A. (2014). Minimum Linear Arrangement of Series-Parallel Graphs. In <i>Proceedings of the 12th Workshop on Approximation and Online Algorithms (WAOA)</i> (pp. 168--180).","short":"C. Scheideler, M. Eikel, A. Setzer, in: Proceedings of the 12th Workshop on Approximation and Online Algorithms (WAOA), 2014, pp. 168--180.","mla":"Scheideler, Christian, et al. “Minimum Linear Arrangement of Series-Parallel Graphs.” <i>Proceedings of the 12th Workshop on Approximation and Online Algorithms (WAOA)</i>, 2014, pp. 168--180.","bibtex":"@inproceedings{Scheideler_Eikel_Setzer_2014, series={LNCS}, title={Minimum Linear Arrangement of Series-Parallel Graphs}, booktitle={Proceedings of the 12th Workshop on Approximation and Online Algorithms (WAOA)}, author={Scheideler, Christian and Eikel, Martina and Setzer, Alexander}, year={2014}, pages={168--180}, collection={LNCS} }","ieee":"C. Scheideler, M. Eikel, and A. Setzer, “Minimum Linear Arrangement of Series-Parallel Graphs,” in <i>Proceedings of the 12th Workshop on Approximation and Online Algorithms (WAOA)</i>, 2014, pp. 168--180.","chicago":"Scheideler, Christian, Martina Eikel, and Alexander Setzer. “Minimum Linear Arrangement of Series-Parallel Graphs.” In <i>Proceedings of the 12th Workshop on Approximation and Online Algorithms (WAOA)</i>, 168--180. LNCS, 2014.","ama":"Scheideler C, Eikel M, Setzer A. Minimum Linear Arrangement of Series-Parallel Graphs. In: <i>Proceedings of the 12th Workshop on Approximation and Online Algorithms (WAOA)</i>. LNCS. ; 2014:168--180."},"page":"168--180","year":"2014","has_accepted_license":"1","title":"Minimum Linear Arrangement of Series-Parallel Graphs","author":[{"first_name":"Christian","last_name":"Scheideler","full_name":"Scheideler, Christian","id":"20792"},{"last_name":"Eikel","full_name":"Eikel, Martina","first_name":"Martina"},{"first_name":"Alexander","last_name":"Setzer","id":"11108","full_name":"Setzer, Alexander"}],"date_created":"2017-10-17T12:42:09Z","date_updated":"2022-01-06T07:00:02Z"},{"year":"2013","citation":{"chicago":"Setzer, Alexander. <i>Approximation Algorithms for the Linear Arrangement of Special Classes of Graphs</i>. Universität Paderborn, 2013.","ieee":"A. Setzer, <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.","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.","mla":"Setzer, Alexander. <i>Approximation Algorithms for the Linear Arrangement of Special Classes of Graphs</i>. Universität Paderborn, 2013.","apa":"Setzer, A. (2013). <i>Approximation Algorithms for the Linear Arrangement of Special Classes of Graphs</i>. Universität Paderborn."},"title":"Approximation Algorithms for the Linear Arrangement of Special Classes of Graphs","publisher":"Universität Paderborn","date_updated":"2022-01-06T07:01:59Z","author":[{"last_name":"Setzer","full_name":"Setzer, Alexander","id":"11108","first_name":"Alexander"}],"date_created":"2017-10-17T12:42:40Z","status":"public","type":"mastersthesis","_id":"555","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"},{"date_updated":"2022-01-06T07:02:59Z","date_created":"2017-10-17T12:42:54Z","author":[{"first_name":"Andreas","full_name":"Cord-Landwehr, Andreas","last_name":"Cord-Landwehr"},{"full_name":"Huellmann (married name: Eikel), Martina","last_name":"Huellmann (married name: Eikel)","first_name":"Martina"},{"first_name":"Peter","full_name":"Kling, Peter","last_name":"Kling"},{"id":"11108","full_name":"Setzer, Alexander","last_name":"Setzer","first_name":"Alexander"}],"title":"Basic Network Creation Games with Communication Interests","doi":"10.1007/978-3-642-33996-7_7","has_accepted_license":"1","year":"2012","citation":{"bibtex":"@inproceedings{Cord-Landwehr_Huellmann (married name: Eikel)_Kling_Setzer_2012, series={LNCS}, title={Basic Network Creation Games with Communication Interests}, DOI={<a href=\"https://doi.org/10.1007/978-3-642-33996-7_7\">10.1007/978-3-642-33996-7_7</a>}, booktitle={Proceedings of the 5th International Symposium on Algorithmic Game Theory (SAGT)}, author={Cord-Landwehr, Andreas and Huellmann (married name: Eikel), Martina and Kling, Peter and Setzer, Alexander}, year={2012}, pages={72--83}, collection={LNCS} }","short":"A. Cord-Landwehr, M. Huellmann (married name: Eikel), P. Kling, A. Setzer, in: Proceedings of the 5th International Symposium on Algorithmic Game Theory (SAGT), 2012, pp. 72--83.","mla":"Cord-Landwehr, Andreas, et al. “Basic Network Creation Games with Communication Interests.” <i>Proceedings of the 5th International Symposium on Algorithmic Game Theory (SAGT)</i>, 2012, pp. 72--83, doi:<a href=\"https://doi.org/10.1007/978-3-642-33996-7_7\">10.1007/978-3-642-33996-7_7</a>.","apa":"Cord-Landwehr, A., Huellmann (married name: Eikel), M., Kling, P., &#38; Setzer, A. (2012). Basic Network Creation Games with Communication Interests. In <i>Proceedings of the 5th International Symposium on Algorithmic Game Theory (SAGT)</i> (pp. 72--83). <a href=\"https://doi.org/10.1007/978-3-642-33996-7_7\">https://doi.org/10.1007/978-3-642-33996-7_7</a>","ieee":"A. Cord-Landwehr, M. Huellmann (married name: Eikel), P. Kling, and A. Setzer, “Basic Network Creation Games with Communication Interests,” in <i>Proceedings of the 5th International Symposium on Algorithmic Game Theory (SAGT)</i>, 2012, pp. 72--83.","chicago":"Cord-Landwehr, Andreas, Martina Huellmann (married name: Eikel), Peter Kling, and Alexander Setzer. “Basic Network Creation Games with Communication Interests.” In <i>Proceedings of the 5th International Symposium on Algorithmic Game Theory (SAGT)</i>, 72--83. LNCS, 2012. <a href=\"https://doi.org/10.1007/978-3-642-33996-7_7\">https://doi.org/10.1007/978-3-642-33996-7_7</a>.","ama":"Cord-Landwehr A, Huellmann (married name: Eikel) M, Kling P, Setzer A. Basic Network Creation Games with Communication Interests. In: <i>Proceedings of the 5th International Symposium on Algorithmic Game Theory (SAGT)</i>. LNCS. ; 2012:72--83. doi:<a href=\"https://doi.org/10.1007/978-3-642-33996-7_7\">10.1007/978-3-642-33996-7_7</a>"},"page":"72--83","project":[{"_id":"1","name":"SFB 901"},{"_id":"5","name":"SFB 901 - Subprojekt A1"},{"_id":"2","name":"SFB 901 - Project Area A"}],"_id":"628","user_id":"477","series_title":"LNCS","department":[{"_id":"79"},{"_id":"63"}],"ddc":["040"],"language":[{"iso":"eng"}],"file_date_updated":"2018-03-15T06:42:01Z","type":"conference","publication":"Proceedings of the 5th International Symposium on Algorithmic Game Theory (SAGT)","abstract":[{"lang":"eng","text":"Network creation games model the creation and usage costs of networks formed by a set of selfish peers.Each peer has the ability to change the network in a limited way, e.g., by creating or deleting incident links.In doing so, a peer can reduce its individual communication cost.Typically, these costs are modeled by the maximum or average distance in the network.We introduce a generalized version of the basic network creation game (BNCG).In the BNCG (by Alon et al., SPAA 2010), each peer may replace one of its incident links by a link to an arbitrary peer.This is done in a selfish way in order to minimize either the maximum or average distance to all other peers.That is, each peer works towards a network structure that allows himself to communicate efficiently with all other peers.However, participants of large networks are seldom interested in all peers.Rather, they want to communicate efficiently with a small subset only.Our model incorporates these (communication) interests explicitly.Given peers with interests and a communication network forming a tree, we prove several results on the structure and quality of equilibria in our model.We focus on the MAX-version, i.e., each node tries to minimize the maximum distance to nodes it is interested in, and give an upper bound of O(\\sqrt(n)) for the private costs in an equilibrium of n peers.Moreover, we give an equilibrium for a circular interest graph where a node has private cost Omega(\\sqrt(n)), showing that our bound is tight.This example can be extended such that we get a tight bound of Theta(\\sqrt(n)) for the price of anarchy.For the case of general networks we show the price of anarchy to be Theta(n).Additionally, we prove an interesting connection between a maximum independent set in the interest graph and the private costs of the peers."}],"file":[{"relation":"main_file","success":1,"content_type":"application/pdf","file_name":"628-FULL_paper_bncs_with_interests.pdf","access_level":"closed","file_id":"1238","file_size":300591,"creator":"florida","date_created":"2018-03-15T06:42:01Z","date_updated":"2018-03-15T06:42:01Z"}],"status":"public"},{"citation":{"chicago":"Setzer, Alexander. <i>Lokale Online-Strategien Zur Linearen Anordnung von Teilnehmern in Einem Peer-to-Peer Netzwerk</i>. Universität Paderborn, 2011.","ieee":"A. Setzer, <i>Lokale Online-Strategien zur linearen Anordnung von Teilnehmern in einem Peer-to-Peer Netzwerk</i>. Universität Paderborn, 2011.","ama":"Setzer A. <i>Lokale Online-Strategien Zur Linearen Anordnung von Teilnehmern in Einem Peer-to-Peer Netzwerk</i>. Universität Paderborn; 2011.","short":"A. Setzer, Lokale Online-Strategien Zur Linearen Anordnung von Teilnehmern in Einem Peer-to-Peer Netzwerk, Universität Paderborn, 2011.","bibtex":"@book{Setzer_2011, title={Lokale Online-Strategien zur linearen Anordnung von Teilnehmern in einem Peer-to-Peer Netzwerk}, publisher={Universität Paderborn}, author={Setzer, Alexander}, year={2011} }","mla":"Setzer, Alexander. <i>Lokale Online-Strategien Zur Linearen Anordnung von Teilnehmern in Einem Peer-to-Peer Netzwerk</i>. Universität Paderborn, 2011.","apa":"Setzer, A. (2011). <i>Lokale Online-Strategien zur linearen Anordnung von Teilnehmern in einem Peer-to-Peer Netzwerk</i>. Universität Paderborn."},"year":"2011","title":"Lokale Online-Strategien zur linearen Anordnung von Teilnehmern in einem Peer-to-Peer Netzwerk","author":[{"last_name":"Setzer","full_name":"Setzer, Alexander","id":"11108","first_name":"Alexander"}],"supervisor":[{"last_name":"Scheideler","id":"20792","full_name":"Scheideler, Christian","first_name":"Christian"}],"date_created":"2020-08-17T08:08:13Z","date_updated":"2022-01-06T06:53:24Z","publisher":"Universität Paderborn","status":"public","type":"bachelorsthesis","language":[{"iso":"eng"}],"department":[{"_id":"79"}],"user_id":"477","_id":"17997","project":[{"_id":"1","name":"SFB 901"},{"name":"SFB 901 - Project Area A","_id":"2"},{"name":"SFB 901 - Subproject A1","_id":"5"}]}]