[{"ddc":["040"],"language":[{"iso":"eng"}],"external_id":{"arxiv":["1708.06542"]},"abstract":[{"lang":"eng","text":"Searching for other participants is one of the most important operations in a distributed system.We are interested in topologies in which it is possible to route a packet in a fixed number of hops until it arrives at its destination.Given a constant $d$, this paper introduces a new self-stabilizing protocol for the $q$-ary $d$-dimensional de Bruijn graph ($q = \\sqrt[d]{n}$) that is able to route any search request in at most $d$ hops w.h.p., while significantly lowering the node degree compared to the clique: We require nodes to have a degree of $\\mathcal O(\\sqrt[d]{n})$, which is asymptotically optimal for a fixed diameter $d$.The protocol keeps the expected amount of edge redirections per node in $\\mathcal O(\\sqrt[d]{n})$, when the number of nodes in the system increases by factor $2^d$.The number of messages that are periodically sent out by nodes is constant."}],"file":[{"creator":"mfeldma2","date_created":"2018-10-31T13:30:13Z","date_updated":"2018-10-31T13:30:13Z","file_id":"5214","access_level":"closed","file_name":"Feldmann-Scheideler2017_Chapter_ASelf-stabilizingGeneralDeBrui.pdf","file_size":311204,"content_type":"application/pdf","relation":"main_file","success":1}],"publication":"Proceedings of the 19th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)","title":"A Self-Stabilizing General De Bruijn Graph","publisher":"Springer, Cham","date_created":"2017-10-17T12:41:16Z","year":"2017","file_date_updated":"2018-10-31T13:30:13Z","_id":"125","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":"23538","series_title":"Lecture Notes in Computer Science","status":"public","type":"conference","doi":"10.1007/978-3-319-69084-1_17","date_updated":"2022-01-06T06:51:19Z","volume":10616,"author":[{"first_name":"Michael","last_name":"Feldmann","id":"23538","full_name":"Feldmann, Michael"},{"first_name":"Christian","last_name":"Scheideler","id":"20792","full_name":"Scheideler, Christian"}],"intvolume":"     10616","page":"250-264 ","citation":{"short":"M. Feldmann, C. Scheideler, in: Proceedings of the 19th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), Springer, Cham, 2017, pp. 250–264.","bibtex":"@inproceedings{Feldmann_Scheideler_2017, series={Lecture Notes in Computer Science}, title={A Self-Stabilizing General De Bruijn Graph}, volume={10616}, DOI={<a href=\"https://doi.org/10.1007/978-3-319-69084-1_17\">10.1007/978-3-319-69084-1_17</a>}, booktitle={Proceedings of the 19th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)}, publisher={Springer, Cham}, author={Feldmann, Michael and Scheideler, Christian}, year={2017}, pages={250–264}, collection={Lecture Notes in Computer Science} }","mla":"Feldmann, Michael, and Christian Scheideler. “A Self-Stabilizing General De Bruijn Graph.” <i>Proceedings of the 19th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)</i>, vol. 10616, Springer, Cham, 2017, pp. 250–64, doi:<a href=\"https://doi.org/10.1007/978-3-319-69084-1_17\">10.1007/978-3-319-69084-1_17</a>.","apa":"Feldmann, M., &#38; Scheideler, C. (2017). A Self-Stabilizing General De Bruijn Graph. In <i>Proceedings of the 19th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)</i> (Vol. 10616, pp. 250–264). Springer, Cham. <a href=\"https://doi.org/10.1007/978-3-319-69084-1_17\">https://doi.org/10.1007/978-3-319-69084-1_17</a>","ama":"Feldmann M, Scheideler C. A Self-Stabilizing General De Bruijn Graph. In: <i>Proceedings of the 19th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)</i>. Vol 10616. Lecture Notes in Computer Science. Springer, Cham; 2017:250-264. doi:<a href=\"https://doi.org/10.1007/978-3-319-69084-1_17\">10.1007/978-3-319-69084-1_17</a>","chicago":"Feldmann, Michael, and Christian Scheideler. “A Self-Stabilizing General De Bruijn Graph.” In <i>Proceedings of the 19th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)</i>, 10616:250–64. Lecture Notes in Computer Science. Springer, Cham, 2017. <a href=\"https://doi.org/10.1007/978-3-319-69084-1_17\">https://doi.org/10.1007/978-3-319-69084-1_17</a>.","ieee":"M. Feldmann and C. Scheideler, “A Self-Stabilizing General De Bruijn Graph,” in <i>Proceedings of the 19th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)</i>, 2017, vol. 10616, pp. 250–264."},"publication_identifier":{"isbn":["978-3-319-69083-4"]},"has_accepted_license":"1","publication_status":"published"},{"year":"2016","page":"477-488","citation":{"short":"F.N. Abu-Khzam, S. Li, C. Markarian, F. Meyer auf der Heide, P. Podlipyan, in: Proceedings of the 10th International Conference on Combinatorial Optimization and Applications (COCOA), 2016, pp. 477–488.","bibtex":"@inproceedings{Abu-Khzam_Li_Markarian_Meyer auf der Heide_Podlipyan_2016, series={LNCS}, title={On the Parameterized Parallel Complexity and the Vertex Cover Problem}, DOI={<a href=\"https://doi.org/10.1007/978-3-319-48749-6_35\">10.1007/978-3-319-48749-6_35</a>}, booktitle={Proceedings of the 10th International Conference on Combinatorial Optimization and Applications (COCOA)}, author={Abu-Khzam, Faisal N. and Li, Shouwei and Markarian, Christine and Meyer auf der Heide, Friedhelm and Podlipyan, Pavel}, year={2016}, pages={477–488}, collection={LNCS} }","mla":"Abu-Khzam, Faisal N., et al. “On the Parameterized Parallel Complexity and the Vertex Cover Problem.” <i>Proceedings of the 10th International Conference on Combinatorial Optimization and Applications (COCOA)</i>, 2016, pp. 477–88, doi:<a href=\"https://doi.org/10.1007/978-3-319-48749-6_35\">10.1007/978-3-319-48749-6_35</a>.","apa":"Abu-Khzam, F. N., Li, S., Markarian, C., Meyer auf der Heide, F., &#38; Podlipyan, P. (2016). On the Parameterized Parallel Complexity and the Vertex Cover Problem. In <i>Proceedings of the 10th International Conference on Combinatorial Optimization and Applications (COCOA)</i> (pp. 477–488). <a href=\"https://doi.org/10.1007/978-3-319-48749-6_35\">https://doi.org/10.1007/978-3-319-48749-6_35</a>","chicago":"Abu-Khzam, Faisal N., Shouwei Li, Christine Markarian, Friedhelm Meyer auf der Heide, and Pavel Podlipyan. “On the Parameterized Parallel Complexity and the Vertex Cover Problem.” In <i>Proceedings of the 10th International Conference on Combinatorial Optimization and Applications (COCOA)</i>, 477–88. LNCS, 2016. <a href=\"https://doi.org/10.1007/978-3-319-48749-6_35\">https://doi.org/10.1007/978-3-319-48749-6_35</a>.","ieee":"F. N. Abu-Khzam, S. Li, C. Markarian, F. Meyer auf der Heide, and P. Podlipyan, “On the Parameterized Parallel Complexity and the Vertex Cover Problem,” in <i>Proceedings of the 10th International Conference on Combinatorial Optimization and Applications (COCOA)</i>, 2016, pp. 477–488.","ama":"Abu-Khzam FN, Li S, Markarian C, Meyer auf der Heide F, Podlipyan P. On the Parameterized Parallel Complexity and the Vertex Cover Problem. In: <i>Proceedings of the 10th International Conference on Combinatorial Optimization and Applications (COCOA)</i>. LNCS. ; 2016:477-488. doi:<a href=\"https://doi.org/10.1007/978-3-319-48749-6_35\">10.1007/978-3-319-48749-6_35</a>"},"has_accepted_license":"1","title":"On the Parameterized Parallel Complexity and the Vertex Cover Problem","doi":"10.1007/978-3-319-48749-6_35","date_updated":"2022-01-06T06:53:17Z","author":[{"last_name":"Abu-Khzam","full_name":"Abu-Khzam, Faisal N.","first_name":"Faisal N."},{"full_name":"Li, Shouwei","last_name":"Li","first_name":"Shouwei"},{"first_name":"Christine","id":"37612","full_name":"Markarian, Christine","last_name":"Markarian"},{"first_name":"Friedhelm","last_name":"Meyer auf der Heide","full_name":"Meyer auf der Heide, Friedhelm","id":"15523"},{"last_name":"Podlipyan","full_name":"Podlipyan, Pavel","first_name":"Pavel"}],"date_created":"2017-10-17T12:41:26Z","abstract":[{"lang":"eng","text":"Efficiently parallelizable parameterized problems have been classified as being either in the class FPP (fixed-parameter parallelizable) or the class PNC (parameterized analog of NC), which contains FPP as a subclass. In this paper, we propose a more restrictive class of parallelizable parameterized problems called fixed-parameter parallel-tractable (FPPT). For a problem to be in FPPT, it should possess an efficient parallel algorithm not only from a theoretical standpoint but in practice as well. The primary distinction between FPPT and FPP is the parallel processor utilization, which is bounded by a polynomial function in the case of FPPT. We initiate the study of FPPT with the well-known k-vertex cover problem. In particular, we present a parallel algorithm that outperforms the best known parallel algorithm for this problem: using O(m) instead of O(n2) parallel processors, the running time improves from 4logn+O(kk) to O(k⋅log3n), where m is the number of edges, n is the number of vertices of the input graph, and k is an upper bound of the size of the sought vertex cover. We also note that a few P-complete problems fall into FPPT including the monotone circuit value problem (MCV) when the underlying graphs are bounded by a constant Euler genus."}],"status":"public","file":[{"success":1,"relation":"main_file","content_type":"application/pdf","file_size":293345,"file_name":"OnTheParameterizedParallelComp.pdf","access_level":"closed","file_id":"5266","date_updated":"2018-11-02T14:15:18Z","creator":"ups","date_created":"2018-11-02T14:15:18Z"}],"publication":"Proceedings of the 10th International Conference on Combinatorial Optimization and Applications (COCOA)","type":"conference","ddc":["000"],"file_date_updated":"2018-11-02T14:15:18Z","language":[{"iso":"eng"}],"_id":"177","project":[{"name":"SFB 901","_id":"1"},{"_id":"5","name":"SFB 901 - Subprojekt A1"},{"_id":"2","name":"SFB 901 - Project Area A"}],"department":[{"_id":"63"}],"series_title":"LNCS","user_id":"477"},{"citation":{"apa":"Meyer auf der Heide, F. (Ed.). (2016). <i>Introduction to the Special Issue on SPAA 2014</i>. <i>Transactions on Parallel Computing (TOPC)</i>. <a href=\"https://doi.org/10.1145/2936716\">https://doi.org/10.1145/2936716</a>","mla":"Meyer auf der Heide, Friedhelm, editor. “Introduction to the Special Issue on SPAA 2014.” <i>Transactions on Parallel Computing (TOPC)</i>, no. 1, 2016, doi:<a href=\"https://doi.org/10.1145/2936716\">10.1145/2936716</a>.","bibtex":"@book{Meyer auf der Heide_2016, title={Introduction to the Special Issue on SPAA 2014}, DOI={<a href=\"https://doi.org/10.1145/2936716\">10.1145/2936716</a>}, number={1}, journal={Transactions on Parallel Computing (TOPC)}, year={2016} }","short":"F. Meyer auf der Heide, ed., Introduction to the Special Issue on SPAA 2014, 2016.","ama":"Meyer auf der Heide F, ed. <i>Introduction to the Special Issue on SPAA 2014</i>.; 2016. doi:<a href=\"https://doi.org/10.1145/2936716\">10.1145/2936716</a>","chicago":"Meyer auf der Heide, Friedhelm, ed. <i>Introduction to the Special Issue on SPAA 2014</i>. <i>Transactions on Parallel Computing (TOPC)</i>, 2016. <a href=\"https://doi.org/10.1145/2936716\">https://doi.org/10.1145/2936716</a>.","ieee":"F. Meyer auf der Heide, Ed., <i>Introduction to the Special Issue on SPAA 2014</i>, no. 1. 2016."},"page":"1","year":"2016","issue":"1","has_accepted_license":"1","doi":"10.1145/2936716","title":"Introduction to the Special Issue on SPAA 2014","date_created":"2017-10-17T12:41:28Z","date_updated":"2022-01-06T06:53:51Z","file":[{"date_updated":"2018-03-21T12:31:42Z","creator":"florida","date_created":"2018-03-21T12:31:42Z","file_size":34053,"file_id":"1531","access_level":"closed","file_name":"187-a1-heide.pdf","content_type":"application/pdf","success":1,"relation":"main_file"}],"status":"public","editor":[{"full_name":"Meyer auf der Heide, Friedhelm","id":"15523","last_name":"Meyer auf der Heide","first_name":"Friedhelm"}],"type":"journal_editor","publication":"Transactions on Parallel Computing (TOPC)","file_date_updated":"2018-03-21T12:31:42Z","ddc":["040"],"user_id":"15504","department":[{"_id":"63"}],"project":[{"name":"SFB 901","_id":"1"},{"name":"SFB 901 - Subprojekt A1","_id":"5"},{"_id":"2","name":"SFB 901 - Project Area A"}],"_id":"187"},{"year":"2016","quality_controlled":"1","issue":"1","title":"The Impact of Communication Patterns on Distributed Self-Adjusting Binary Search Tree","publisher":"Journal of Graph Algorithms and Applications","date_created":"2018-11-19T15:33:50Z","abstract":[{"text":"This paper introduces the problem of communication pattern adaption for a distributed self-adjusting binary search tree. We propose a simple local algorithm that is closely related to the over thirty-year-old idea of splay trees and evaluate its adaption performance in the distributed scenario if different communication patterns are provided. \r\nTo do so, the process of self-adjustment is modeled similarly to a basic network creation game in which the nodes want to communicate with only a certain subset of all nodes. \r\nWe show that, in general, the game (i.e., the process of local adjustments) does not converge, and that convergence is related to certain structures of the communication interests, which we call conflicts. \r\nWe classify conflicts and show that for two communication scenarios in which convergence is guaranteed, the self-adjusting tree performs well. \r\nFurthermore, we investigate the different classes of conflicts separately and show that, for a certain class of conflicts, the performance of the tree network is asymptotically as good as the performance for converging instances.\r\nHowever, for the other conflict classes, a distributed self-adjusting binary search tree adapts poorly.","lang":"eng"}],"file":[{"relation":"main_file","success":1,"content_type":"application/pdf","file_id":"5912","file_name":"Strothmann2016.20.1.pdf","access_level":"closed","file_size":2324066,"date_created":"2018-11-27T11:58:08Z","creator":"thim","date_updated":"2018-11-27T11:58:08Z"}],"publication":"Journal of Graph Algorithms and Applications","ddc":["040"],"language":[{"iso":"eng"}],"citation":{"ama":"Strothmann TF. The Impact of Communication Patterns on Distributed Self-Adjusting Binary Search Tree. <i>Journal of Graph Algorithms and Applications</i>. 2016;20(1):79-100. doi:<a href=\"https://doi.org/10.7155/jgaa.00385\">10.7155/jgaa.00385</a>","chicago":"Strothmann, Thim Frederik. “The Impact of Communication Patterns on Distributed Self-Adjusting Binary Search Tree.” <i>Journal of Graph Algorithms and Applications</i> 20, no. 1 (2016): 79–100. <a href=\"https://doi.org/10.7155/jgaa.00385\">https://doi.org/10.7155/jgaa.00385</a>.","ieee":"T. F. Strothmann, “The Impact of Communication Patterns on Distributed Self-Adjusting Binary Search Tree,” <i>Journal of Graph Algorithms and Applications</i>, vol. 20, no. 1, pp. 79–100, 2016.","bibtex":"@article{Strothmann_2016, title={The Impact of Communication Patterns on Distributed Self-Adjusting Binary Search Tree}, volume={20}, DOI={<a href=\"https://doi.org/10.7155/jgaa.00385\">10.7155/jgaa.00385</a>}, number={1}, journal={Journal of Graph Algorithms and Applications}, publisher={Journal of Graph Algorithms and Applications}, author={Strothmann, Thim Frederik}, year={2016}, pages={79–100} }","short":"T.F. Strothmann, Journal of Graph Algorithms and Applications 20 (2016) 79–100.","mla":"Strothmann, Thim Frederik. “The Impact of Communication Patterns on Distributed Self-Adjusting Binary Search Tree.” <i>Journal of Graph Algorithms and Applications</i>, vol. 20, no. 1, Journal of Graph Algorithms and Applications, 2016, pp. 79–100, doi:<a href=\"https://doi.org/10.7155/jgaa.00385\">10.7155/jgaa.00385</a>.","apa":"Strothmann, T. F. (2016). The Impact of Communication Patterns on Distributed Self-Adjusting Binary Search Tree. <i>Journal of Graph Algorithms and Applications</i>, <i>20</i>(1), 79–100. <a href=\"https://doi.org/10.7155/jgaa.00385\">https://doi.org/10.7155/jgaa.00385</a>"},"page":"79-100","intvolume":"        20","publication_status":"published","has_accepted_license":"1","publication_identifier":{"issn":["1526-1719"]},"doi":"10.7155/jgaa.00385","date_updated":"2022-01-06T07:02:38Z","author":[{"last_name":"Strothmann","full_name":"Strothmann, Thim Frederik","id":"11319","first_name":"Thim Frederik"}],"volume":20,"status":"public","type":"journal_article","file_date_updated":"2018-11-27T11:58:08Z","project":[{"_id":"1","name":"SFB 901"},{"name":"SFB 901 - Project Area A","_id":"2"},{"_id":"5","name":"SFB 901 - Subproject A1"}],"_id":"5762","user_id":"477","department":[{"_id":"79"}]},{"author":[{"full_name":"Kutzias, Damian","last_name":"Kutzias","first_name":"Damian"}],"supervisor":[{"first_name":"Friedhelm","full_name":"Meyer auf der Heide, Friedhelm","id":"15523","last_name":"Meyer auf der Heide"}],"date_created":"2017-11-14T06:50:35Z","publisher":"Universität Paderborn","date_updated":"2022-01-06T07:03:23Z","title":"Friendship Processes in Network Creation Games","citation":{"mla":"Kutzias, Damian. <i>Friendship Processes in Network Creation Games</i>. Universität Paderborn, 2016.","bibtex":"@book{Kutzias_2016, title={Friendship Processes in Network Creation Games}, publisher={Universität Paderborn}, author={Kutzias, Damian}, year={2016} }","short":"D. Kutzias, Friendship Processes in Network Creation Games, Universität Paderborn, 2016.","apa":"Kutzias, D. (2016). <i>Friendship Processes in Network Creation Games</i>. Universität Paderborn.","ama":"Kutzias D. <i>Friendship Processes in Network Creation Games</i>. Universität Paderborn; 2016.","chicago":"Kutzias, Damian. <i>Friendship Processes in Network Creation Games</i>. Universität Paderborn, 2016.","ieee":"D. Kutzias, <i>Friendship Processes in Network Creation Games</i>. Universität Paderborn, 2016."},"year":"2016","user_id":"477","department":[{"_id":"63"}],"project":[{"_id":"1","name":"SFB 901"},{"_id":"5","name":"SFB 901 - Subprojekt A1"},{"_id":"2","name":"SFB 901 - Project Area A"}],"_id":"688","language":[{"iso":"eng"}],"type":"mastersthesis","status":"public"},{"date_updated":"2022-01-06T07:03:23Z","publisher":"Universität Paderborn","author":[{"first_name":"Johannes Sebastian","id":"30291","full_name":"Schaefer, Johannes Sebastian","last_name":"Schaefer"}],"supervisor":[{"first_name":"Friedhelm","id":"15523","full_name":"Meyer auf der Heide, Friedhelm","last_name":"Meyer auf der Heide"}],"date_created":"2017-11-14T06:51:37Z","title":"Routing Algorithms on Delayed Networks for Disaster Management Support","year":"2016","citation":{"bibtex":"@book{Schaefer_2016, title={Routing Algorithms on Delayed Networks for Disaster Management Support}, publisher={Universität Paderborn}, author={Schaefer, Johannes Sebastian}, year={2016} }","short":"J.S. Schaefer, Routing Algorithms on Delayed Networks for Disaster Management Support, Universität Paderborn, 2016.","mla":"Schaefer, Johannes Sebastian. <i>Routing Algorithms on Delayed Networks for Disaster Management Support</i>. Universität Paderborn, 2016.","apa":"Schaefer, J. S. (2016). <i>Routing Algorithms on Delayed Networks for Disaster Management Support</i>. Universität Paderborn.","chicago":"Schaefer, Johannes Sebastian. <i>Routing Algorithms on Delayed Networks for Disaster Management Support</i>. Universität Paderborn, 2016.","ieee":"J. S. Schaefer, <i>Routing Algorithms on Delayed Networks for Disaster Management Support</i>. Universität Paderborn, 2016.","ama":"Schaefer JS. <i>Routing Algorithms on Delayed Networks for Disaster Management Support</i>. Universität Paderborn; 2016."},"project":[{"_id":"1","name":"SFB 901"},{"_id":"5","name":"SFB 901 - Subprojekt A1"},{"_id":"2","name":"SFB 901 - Project Area A"}],"_id":"689","user_id":"477","department":[{"_id":"63"}],"language":[{"iso":"eng"}],"type":"mastersthesis","status":"public"},{"series_title":"Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn","user_id":"5786","department":[{"_id":"63"},{"_id":"26"}],"project":[{"_id":"1","name":"SFB 901"},{"name":"SFB 901 - Subprojekt A1","_id":"5"},{"_id":"2","name":"SFB 901 - Project Area A"}],"_id":"154","file_date_updated":"2018-03-21T12:52:03Z","type":"dissertation","status":"public","author":[{"first_name":"Andreas","last_name":"Cord-Landwehr","full_name":"Cord-Landwehr, Andreas"}],"supervisor":[{"first_name":"Friedhelm","id":"15523","full_name":"Meyer auf der Heide, Friedhelm","last_name":"Meyer auf der Heide"}],"volume":353,"date_updated":"2022-01-06T06:52:23Z","related_material":{"link":[{"relation":"confirmation","url":"http://nbn-resolving.de/urn:nbn:de:hbz:466:2-24089"}]},"has_accepted_license":"1","publication_identifier":{"isbn":["978-3-942647-72-4"]},"citation":{"ama":"Cord-Landwehr A. <i>Selfish Network Creation - On Variants of Network Creation Games</i>. Vol 353. Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn; 2016.","ieee":"A. Cord-Landwehr, <i>Selfish Network Creation - On Variants of Network Creation Games</i>, vol. 353. Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn, 2016.","chicago":"Cord-Landwehr, Andreas. <i>Selfish Network Creation - On Variants of Network Creation Games</i>. Vol. 353. Verlagsschriftenreihe Des Heinz Nixdorf Instituts, Paderborn. Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn, 2016.","short":"A. Cord-Landwehr, Selfish Network Creation - On Variants of Network Creation Games, Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn, 2016.","mla":"Cord-Landwehr, Andreas. <i>Selfish Network Creation - On Variants of Network Creation Games</i>. Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn, 2016.","bibtex":"@book{Cord-Landwehr_2016, series={Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}, title={Selfish Network Creation - On Variants of Network Creation Games}, volume={353}, publisher={Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}, author={Cord-Landwehr, Andreas}, year={2016}, collection={Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn} }","apa":"Cord-Landwehr, A. (2016). <i>Selfish Network Creation - On Variants of Network Creation Games</i> (Vol. 353). Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn."},"intvolume":"       353","language":[{"iso":"eng"}],"ddc":["040"],"file":[{"date_updated":"2018-03-21T12:52:03Z","date_created":"2018-03-21T12:52:03Z","creator":"florida","file_size":800101,"file_name":"154-dissertation.pdf","access_level":"closed","file_id":"1551","content_type":"application/pdf","success":1,"relation":"main_file"}],"date_created":"2017-10-17T12:41:22Z","publisher":"Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn","title":"Selfish Network Creation - On Variants of Network Creation Games","year":"2016"},{"year":"2016","page":"593--607","citation":{"apa":"Drees, M., Feldkord, B., &#38; Skopalik, A. (2016). Strategic Online Facility Location. In <i>Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA)</i> (pp. 593--607). <a href=\"https://doi.org/10.1007/978-3-319-48749-6_43\">https://doi.org/10.1007/978-3-319-48749-6_43</a>","short":"M. Drees, B. Feldkord, A. Skopalik, in: Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA), 2016, pp. 593--607.","bibtex":"@inproceedings{Drees_Feldkord_Skopalik_2016, series={LNCS}, title={Strategic Online Facility Location}, DOI={<a href=\"https://doi.org/10.1007/978-3-319-48749-6_43\">10.1007/978-3-319-48749-6_43</a>}, booktitle={Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA)}, author={Drees, Maximilian and Feldkord, Björn and Skopalik, Alexander}, year={2016}, pages={593--607}, collection={LNCS} }","mla":"Drees, Maximilian, et al. “Strategic Online Facility Location.” <i>Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA)</i>, 2016, pp. 593--607, doi:<a href=\"https://doi.org/10.1007/978-3-319-48749-6_43\">10.1007/978-3-319-48749-6_43</a>.","ama":"Drees M, Feldkord B, Skopalik A. Strategic Online Facility Location. In: <i>Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA)</i>. LNCS. ; 2016:593--607. doi:<a href=\"https://doi.org/10.1007/978-3-319-48749-6_43\">10.1007/978-3-319-48749-6_43</a>","chicago":"Drees, Maximilian, Björn Feldkord, and Alexander Skopalik. “Strategic Online Facility Location.” In <i>Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA)</i>, 593--607. LNCS, 2016. <a href=\"https://doi.org/10.1007/978-3-319-48749-6_43\">https://doi.org/10.1007/978-3-319-48749-6_43</a>.","ieee":"M. Drees, B. Feldkord, and A. Skopalik, “Strategic Online Facility Location,” in <i>Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA)</i>, 2016, pp. 593--607."},"has_accepted_license":"1","title":"Strategic Online Facility Location","doi":"10.1007/978-3-319-48749-6_43","date_updated":"2022-01-06T06:52:10Z","author":[{"first_name":"Maximilian","last_name":"Drees","full_name":"Drees, Maximilian"},{"full_name":"Feldkord, Björn","id":"22704","last_name":"Feldkord","first_name":"Björn"},{"full_name":"Skopalik, Alexander","id":"40384","last_name":"Skopalik","first_name":"Alexander"}],"date_created":"2017-10-17T12:41:21Z","abstract":[{"lang":"eng","text":"In this paper we consider a strategic variant of the online facility location problem. Given is a graph in which each node serves two roles: it is a strategic client stating requests as well as a potential location for a facility. In each time step one client states a request which induces private costs equal to the distance to the closest facility. Before serving, the clients may collectively decide to open new facilities, sharing the corresponding price. Instead of optimizing the global costs, each client acts selfishly. The prices of new facilities vary between nodes and also change over time, but are always bounded by some fixed value α. Both the requests as well as the facility prices are given by an online sequence and are not known in advance.We characterize the optimal strategies of the clients and analyze their overall performance in comparison to a centralized offline solution. If all players optimize their own competitiveness, the global performance of the system is O(√α⋅α) times worse than the offline optimum. A restriction to a natural subclass of strategies improves this result to O(α). We also show that for fixed facility costs, we can find strategies such that this bound further improves to O(√α)."}],"status":"public","file":[{"relation":"main_file","success":1,"content_type":"application/pdf","file_name":"149-chp_3A10.1007_2F978-3-319-48749-6_43.pdf","file_id":"1553","access_level":"closed","file_size":236253,"date_created":"2018-03-21T12:55:43Z","creator":"florida","date_updated":"2018-03-21T12:55:43Z"}],"publication":"Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA)","type":"conference","ddc":["040"],"language":[{"iso":"eng"}],"file_date_updated":"2018-03-21T12:55:43Z","_id":"149","project":[{"_id":"1","name":"SFB 901"},{"name":"SFB 901 - Subprojekt A1","_id":"5"},{"name":"SFB 901 - Subproject A3","_id":"7"},{"name":"SFB 901 - Project Area A","_id":"2"}],"department":[{"_id":"63"},{"_id":"541"}],"series_title":"LNCS","user_id":"477"},{"year":"2016","issue":"4","title":"Towards the price of leasing online","publisher":"Springer","date_created":"2017-10-17T12:41:18Z","abstract":[{"text":"We consider online optimization problems in which certain goods have to be acquired in order to provide a service or infrastructure. Classically, decisions for such problems are considered as final: one buys the goods. However, in many real world applications, there is a shift away from the idea of buying goods. Instead, leasing is often a more flexible and lucrative business model. Research has realized this shift and recently initiated the theoretical study of leasing models (Anthony and Gupta in Proceedings of the integer programming and combinatorial optimization: 12th International IPCO Conference, Ithaca, NY, USA, June 25–27, 2007; Meyerson in Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 23–25 Oct 2005, Pittsburgh, PA, USA, 2005; Nagarajan and Williamson in Discret Optim 10(4):361–370, 2013) We extend this line of work and suggest a more systematic study of leasing aspects for a class of online optimization problems. We provide two major technical results. We introduce the leasing variant of online set multicover and give an O(log(mK)logn)-competitive algorithm (with n, m, and K being the number of elements, sets, and leases, respectively). Our results also imply improvements for the non-leasing variant of online set cover. Moreover, we extend results for the leasing variant of online facility location. Nagarajan and Williamson (Discret Optim 10(4):361–370, 2013) gave an O(Klogn)-competitive algorithm for this problem (with n and K being the number of clients and leases, respectively). We remove the dependency on n (and, thereby, on time). In general, this leads to a bound of O(lmaxloglmax) (with the maximal lease length lmax). For many natural problem instances, the bound improves to O(K2).","lang":"eng"}],"file":[{"creator":"ups","date_created":"2018-11-02T15:57:25Z","date_updated":"2018-11-02T15:57:25Z","file_name":"Abshoff-TowardsThePriceOfLeasingOnline.pdf","access_level":"closed","file_id":"5318","file_size":654903,"content_type":"application/pdf","relation":"main_file","success":1}],"publication":"Journal of Combinatorial Optimization","ddc":["000"],"language":[{"iso":"eng"}],"page":" 1197--1216","citation":{"apa":"Abshoff, S., Kling, P., Markarian, C., Meyer auf der Heide, F., &#38; Pietrzyk, P. (2016). Towards the price of leasing online. <i>Journal of Combinatorial Optimization</i>, (4), 1197--1216. <a href=\"https://doi.org/10.1007/s10878-015-9915-5\">https://doi.org/10.1007/s10878-015-9915-5</a>","bibtex":"@article{Abshoff_Kling_Markarian_Meyer auf der Heide_Pietrzyk_2016, title={Towards the price of leasing online}, DOI={<a href=\"https://doi.org/10.1007/s10878-015-9915-5\">10.1007/s10878-015-9915-5</a>}, number={4}, journal={Journal of Combinatorial Optimization}, publisher={Springer}, author={Abshoff, Sebastian and Kling, Peter and Markarian, Christine and Meyer auf der Heide, Friedhelm and Pietrzyk, Peter }, year={2016}, pages={1197--1216} }","short":"S. Abshoff, P. Kling, C. Markarian, F. Meyer auf der Heide, P. Pietrzyk, Journal of Combinatorial Optimization (2016) 1197--1216.","mla":"Abshoff, Sebastian, et al. “Towards the Price of Leasing Online.” <i>Journal of Combinatorial Optimization</i>, no. 4, Springer, 2016, pp. 1197--1216, doi:<a href=\"https://doi.org/10.1007/s10878-015-9915-5\">10.1007/s10878-015-9915-5</a>.","chicago":"Abshoff, Sebastian, Peter Kling, Christine Markarian, Friedhelm Meyer auf der Heide, and Peter  Pietrzyk. “Towards the Price of Leasing Online.” <i>Journal of Combinatorial Optimization</i>, no. 4 (2016): 1197--1216. <a href=\"https://doi.org/10.1007/s10878-015-9915-5\">https://doi.org/10.1007/s10878-015-9915-5</a>.","ieee":"S. Abshoff, P. Kling, C. Markarian, F. Meyer auf der Heide, and P. Pietrzyk, “Towards the price of leasing online,” <i>Journal of Combinatorial Optimization</i>, no. 4, pp. 1197--1216, 2016.","ama":"Abshoff S, Kling P, Markarian C, Meyer auf der Heide F, Pietrzyk P. Towards the price of leasing online. <i>Journal of Combinatorial Optimization</i>. 2016;(4):1197--1216. doi:<a href=\"https://doi.org/10.1007/s10878-015-9915-5\">10.1007/s10878-015-9915-5</a>"},"has_accepted_license":"1","doi":"10.1007/s10878-015-9915-5","date_updated":"2022-01-06T06:51:46Z","author":[{"full_name":"Abshoff, Sebastian","last_name":"Abshoff","first_name":"Sebastian"},{"full_name":"Kling, Peter","last_name":"Kling","first_name":"Peter"},{"id":"37612","full_name":"Markarian, Christine","last_name":"Markarian","first_name":"Christine"},{"first_name":"Friedhelm","last_name":"Meyer auf der Heide","full_name":"Meyer auf der Heide, Friedhelm","id":"15523"},{"full_name":"Pietrzyk, Peter ","last_name":"Pietrzyk","first_name":"Peter "}],"status":"public","type":"journal_article","file_date_updated":"2018-11-02T15:57:25Z","_id":"139","project":[{"name":"SFB 901","_id":"1"},{"_id":"5","name":"SFB 901 - Subprojekt A1"},{"name":"SFB 901 - Subprojekt C4","_id":"16"},{"_id":"2","name":"SFB 901 - Project Area A"},{"name":"SFB 901 - Project Area C","_id":"4"}],"department":[{"_id":"63"}],"user_id":"477"},{"page":"71--84","citation":{"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>","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.","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>.","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>","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>.","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} }","short":"C. Scheideler, A. Setzer, T.F. Strothmann, in: Proceedings of the 30th International Symposium on Distributed Computing (DISC), 2016, pp. 71--84."},"year":"2016","has_accepted_license":"1","doi":"10.1007/978-3-662-53426-7_6","title":"Towards a Universal Approach for Monotonic Searchability in Self-stabilizing Overlay Networks","author":[{"full_name":"Scheideler, Christian","id":"20792","last_name":"Scheideler","first_name":"Christian"},{"first_name":"Alexander","full_name":"Setzer, Alexander","id":"11108","last_name":"Setzer"},{"first_name":"Thim Frederik","last_name":"Strothmann","id":"11319","full_name":"Strothmann, Thim Frederik"}],"date_created":"2017-10-17T12:41:19Z","date_updated":"2022-01-06T06:51:56Z","status":"public","file":[{"date_updated":"2018-03-21T12:59:29Z","creator":"florida","date_created":"2018-03-21T12:59:29Z","file_size":209638,"access_level":"closed","file_id":"1558","file_name":"142-SchSetStrDISC16.pdf","content_type":"application/pdf","success":1,"relation":"main_file"}],"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."}],"publication":"Proceedings of the 30th International Symposium on Distributed Computing (DISC)","type":"conference","file_date_updated":"2018-03-21T12:59:29Z","language":[{"iso":"eng"}],"ddc":["040"],"department":[{"_id":"79"}],"series_title":"LNCS","user_id":"477","_id":"142","project":[{"_id":"1","name":"SFB 901"},{"name":"SFB 901 - Subprojekt A1","_id":"5"},{"_id":"2","name":"SFB 901 - Project Area A"}]},{"publication":"Proceedings of the 22nd International Conference on Computing and Combinatorics (COCOON)","type":"conference","abstract":[{"text":"We present an efficient parallel algorithm for the general Monotone Circuit Value Problem (MCVP) with n gates and an underlying graph of bounded genus k. Our algorithm generalizes a recent result by Limaye et al. who showed that MCVP with toroidal embedding (genus 1) is in NC when the input contains a toroidal embedding of the circuit. In addition to extending this result from genus 1 to any bounded genus k, and unlike the work reported by Limaye et al., we do not require a precomputed embedding to be given. Most importantly, our results imply that given a P-complete problem, it is possible to find an algorithm that makes the problem fall into NC by fixing one or more parameters. Hence, we deduce the interesting analogy: Fixed Parameter Parallelizable (FPP) is with respect to P-complete what Fixed Parameter Tractable (FPT) is with respect to NP-complete. Similar work that uses treewidth as parameter was also presented by Elberfeld et al. in [6].","lang":"eng"}],"status":"public","file":[{"file_size":234587,"file_name":"TheMonotoneCircuitValueProblem.pdf","access_level":"closed","file_id":"5269","date_updated":"2018-11-02T14:20:45Z","creator":"ups","date_created":"2018-11-02T14:20:45Z","success":1,"relation":"main_file","content_type":"application/pdf"}],"_id":"143","project":[{"_id":"1","name":"SFB 901"},{"_id":"5","name":"SFB 901 - Subprojekt A1"},{"name":"SFB 901 - Project Area A","_id":"2"}],"department":[{"_id":"63"}],"series_title":"LNCS","user_id":"477","ddc":["000"],"language":[{"iso":"eng"}],"file_date_updated":"2018-11-02T14:20:45Z","has_accepted_license":"1","year":"2016","page":"92-102","citation":{"chicago":"Abu-Khzam, Faisal N. , Shouwei Li, Christine Markarian, Friedhelm Meyer auf der Heide, and Pavel Podlipyan. “The Monotone Circuit Value Problem with Bounded Genus Is in NC.” In <i>Proceedings of the 22nd International Conference on Computing and Combinatorics (COCOON)</i>, 92–102. LNCS, 2016. <a href=\"https://doi.org/10.1007/978-3-319-42634-1_8\">https://doi.org/10.1007/978-3-319-42634-1_8</a>.","ieee":"F. N. Abu-Khzam, S. Li, C. Markarian, F. Meyer auf der Heide, and P. Podlipyan, “The Monotone Circuit Value Problem with Bounded Genus Is in NC,” in <i>Proceedings of the 22nd International Conference on Computing and Combinatorics (COCOON)</i>, 2016, pp. 92–102.","ama":"Abu-Khzam FN, Li S, Markarian C, Meyer auf der Heide F, Podlipyan P. The Monotone Circuit Value Problem with Bounded Genus Is in NC. In: <i>Proceedings of the 22nd International Conference on Computing and Combinatorics (COCOON)</i>. LNCS. ; 2016:92-102. doi:<a href=\"https://doi.org/10.1007/978-3-319-42634-1_8\">10.1007/978-3-319-42634-1_8</a>","apa":"Abu-Khzam, F. N., Li, S., Markarian, C., Meyer auf der Heide, F., &#38; Podlipyan, P. (2016). The Monotone Circuit Value Problem with Bounded Genus Is in NC. In <i>Proceedings of the 22nd International Conference on Computing and Combinatorics (COCOON)</i> (pp. 92–102). <a href=\"https://doi.org/10.1007/978-3-319-42634-1_8\">https://doi.org/10.1007/978-3-319-42634-1_8</a>","short":"F.N. Abu-Khzam, S. Li, C. Markarian, F. Meyer auf der Heide, P. Podlipyan, in: Proceedings of the 22nd International Conference on Computing and Combinatorics (COCOON), 2016, pp. 92–102.","mla":"Abu-Khzam, Faisal N., et al. “The Monotone Circuit Value Problem with Bounded Genus Is in NC.” <i>Proceedings of the 22nd International Conference on Computing and Combinatorics (COCOON)</i>, 2016, pp. 92–102, doi:<a href=\"https://doi.org/10.1007/978-3-319-42634-1_8\">10.1007/978-3-319-42634-1_8</a>.","bibtex":"@inproceedings{Abu-Khzam_Li_Markarian_Meyer auf der Heide_Podlipyan_2016, series={LNCS}, title={The Monotone Circuit Value Problem with Bounded Genus Is in NC}, DOI={<a href=\"https://doi.org/10.1007/978-3-319-42634-1_8\">10.1007/978-3-319-42634-1_8</a>}, booktitle={Proceedings of the 22nd International Conference on Computing and Combinatorics (COCOON)}, author={Abu-Khzam, Faisal N.  and Li, Shouwei and Markarian, Christine and Meyer auf der Heide, Friedhelm and Podlipyan, Pavel}, year={2016}, pages={92–102}, collection={LNCS} }"},"date_updated":"2022-01-06T06:51:57Z","date_created":"2017-10-17T12:41:19Z","author":[{"full_name":"Abu-Khzam, Faisal N. ","last_name":"Abu-Khzam","first_name":"Faisal N. "},{"first_name":"Shouwei","full_name":"Li, Shouwei","last_name":"Li"},{"last_name":"Markarian","full_name":"Markarian, Christine","id":"37612","first_name":"Christine"},{"first_name":"Friedhelm","id":"15523","full_name":"Meyer auf der Heide, Friedhelm","last_name":"Meyer auf der Heide"},{"full_name":"Podlipyan, Pavel","last_name":"Podlipyan","first_name":"Pavel"}],"title":"The Monotone Circuit Value Problem with Bounded Genus Is in NC","doi":"10.1007/978-3-319-42634-1_8"},{"year":"2016","issue":"5","title":"Systematic evaluation of peer-to-peer systems using PeerfactSim.KOM","publisher":"Wiley Online Library","date_created":"2017-10-17T12:41:20Z","abstract":[{"lang":"eng","text":"Comparative evaluations of peer-to-peer protocols through simulations are a viable approach to judge the performance and costs of the individual protocols in large-scale networks. In order to support this work, we present the peer-to-peer system simulator PeerfactSim.KOM, which we extended over the last years. PeerfactSim.KOM comes with an extensive layer model to support various facets and protocols of peer-to-peer networking. In this article, we describe PeerfactSim.KOM and show how it can be used for detailed measurements of large-scale peer-to-peer networks. We enhanced PeerfactSim.KOM with a fine-grained analyzer concept, with exhaustive automated measurements and gnuplot generators as well as a coordination control to evaluate sets of experiment setups in parallel. Thus, by configuring all experiments and protocols only once and starting the simulator, all desired measurements are performed, analyzed, evaluated, and combined, resulting in a holistic environment for the comparative evaluation of peer-to-peer systems. An immediate comparison of different configurations and overlays under different aspects is possible directly after the execution without any manual post-processing. "}],"file":[{"relation":"main_file","success":1,"content_type":"application/pdf","file_name":"145-Feldotto_et_al-2016-Concurrency_and_Computation-_Practice_and_Experience.pdf","file_id":"1556","access_level":"closed","file_size":3121363,"date_created":"2018-03-21T12:57:57Z","creator":"florida","date_updated":"2018-03-21T12:57:57Z"}],"publication":"Concurrency and Computation: Practice and Experience","ddc":["040"],"intvolume":"        28","page":"1655-1677","citation":{"ama":"Feldotto M, Graffi K. Systematic evaluation of peer-to-peer systems using PeerfactSim.KOM. <i>Concurrency and Computation: Practice and Experience</i>. 2016;28(5):1655-1677. doi:<a href=\"https://doi.org/10.1002/cpe.3716\">10.1002/cpe.3716</a>","chicago":"Feldotto, Matthias, and Kalman Graffi. “Systematic Evaluation of Peer-to-Peer Systems Using PeerfactSim.KOM.” <i>Concurrency and Computation: Practice and Experience</i> 28, no. 5 (2016): 1655–77. <a href=\"https://doi.org/10.1002/cpe.3716\">https://doi.org/10.1002/cpe.3716</a>.","ieee":"M. Feldotto and K. Graffi, “Systematic evaluation of peer-to-peer systems using PeerfactSim.KOM,” <i>Concurrency and Computation: Practice and Experience</i>, vol. 28, no. 5, pp. 1655–1677, 2016.","mla":"Feldotto, Matthias, and Kalman Graffi. “Systematic Evaluation of Peer-to-Peer Systems Using PeerfactSim.KOM.” <i>Concurrency and Computation: Practice and Experience</i>, vol. 28, no. 5, Wiley Online Library, 2016, pp. 1655–77, doi:<a href=\"https://doi.org/10.1002/cpe.3716\">10.1002/cpe.3716</a>.","bibtex":"@article{Feldotto_Graffi_2016, title={Systematic evaluation of peer-to-peer systems using PeerfactSim.KOM}, volume={28}, DOI={<a href=\"https://doi.org/10.1002/cpe.3716\">10.1002/cpe.3716</a>}, number={5}, journal={Concurrency and Computation: Practice and Experience}, publisher={Wiley Online Library}, author={Feldotto, Matthias and Graffi, Kalman}, year={2016}, pages={1655–1677} }","short":"M. Feldotto, K. Graffi, Concurrency and Computation: Practice and Experience 28 (2016) 1655–1677.","apa":"Feldotto, M., &#38; Graffi, K. (2016). Systematic evaluation of peer-to-peer systems using PeerfactSim.KOM. <i>Concurrency and Computation: Practice and Experience</i>, <i>28</i>(5), 1655–1677. <a href=\"https://doi.org/10.1002/cpe.3716\">https://doi.org/10.1002/cpe.3716</a>"},"has_accepted_license":"1","publication_status":"published","doi":"10.1002/cpe.3716","date_updated":"2022-01-06T06:52:00Z","volume":28,"author":[{"id":"14052","full_name":"Feldotto, Matthias","last_name":"Feldotto","orcid":"0000-0003-1348-6516","first_name":"Matthias"},{"full_name":"Graffi, Kalman","last_name":"Graffi","first_name":"Kalman"}],"status":"public","type":"journal_article","file_date_updated":"2018-03-21T12:57:57Z","_id":"145","project":[{"_id":"1","name":"SFB 901"},{"_id":"5","name":"SFB 901 - Subprojekt A1"},{"name":"SFB 901 - Project Area A","_id":"2"}],"department":[{"_id":"79"},{"_id":"63"},{"_id":"541"}],"user_id":"14052"},{"status":"public","type":"mastersthesis","user_id":"477","project":[{"name":"SFB 901","_id":"1"},{"_id":"5","name":"SFB 901 - Subprojekt A1"},{"_id":"2","name":"SFB 901 - Project Area A"}],"_id":"281","citation":{"bibtex":"@book{Rojahn_2015, title={Load Balancing for Range Queries in a Dimension Invariant Peer-to-Peer Network}, publisher={Universität Paderborn}, author={Rojahn, Tobias}, year={2015} }","mla":"Rojahn, Tobias. <i>Load Balancing for Range Queries in a Dimension Invariant Peer-to-Peer Network</i>. Universität Paderborn, 2015.","short":"T. Rojahn, Load Balancing for Range Queries in a Dimension Invariant Peer-to-Peer Network, Universität Paderborn, 2015.","apa":"Rojahn, T. (2015). <i>Load Balancing for Range Queries in a Dimension Invariant Peer-to-Peer Network</i>. Universität Paderborn.","chicago":"Rojahn, Tobias. <i>Load Balancing for Range Queries in a Dimension Invariant Peer-to-Peer Network</i>. Universität Paderborn, 2015.","ieee":"T. Rojahn, <i>Load Balancing for Range Queries in a Dimension Invariant Peer-to-Peer Network</i>. Universität Paderborn, 2015.","ama":"Rojahn T. <i>Load Balancing for Range Queries in a Dimension Invariant Peer-to-Peer Network</i>. Universität Paderborn; 2015."},"year":"2015","title":"Load Balancing for Range Queries in a Dimension Invariant Peer-to-Peer Network","author":[{"full_name":"Rojahn, Tobias","last_name":"Rojahn","first_name":"Tobias"}],"date_created":"2017-10-17T12:41:46Z","publisher":"Universität Paderborn","date_updated":"2022-01-06T06:57:51Z"},{"title":"Towards Establishing Monotonic Searchability in Self-Stabilizing Data Structures","doi":"10.4230/LIPIcs.OPODIS.2015.24","date_updated":"2022-01-06T06:56:07Z","date_created":"2017-10-17T12:41:39Z","author":[{"first_name":"Christian","full_name":"Scheideler, Christian","id":"20792","last_name":"Scheideler"},{"first_name":"Alexander","last_name":"Setzer","id":"11108","full_name":"Setzer, Alexander"},{"last_name":"Strothmann","id":"11319","full_name":"Strothmann, Thim Frederik","first_name":"Thim Frederik"}],"year":"2015","citation":{"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>","short":"C. Scheideler, A. Setzer, T.F. Strothmann, in: Proceedings of the 19th International Conference on Principles of Distributed Systems (OPODIS), 2015.","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)} }","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>.","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>.","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.","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>"},"has_accepted_license":"1","ddc":["040"],"language":[{"iso":"eng"}],"file_date_updated":"2018-03-21T10:28:21Z","_id":"241","project":[{"name":"SFB 901","_id":"1"},{"name":"SFB 901 - Subprojekt A1","_id":"5"},{"_id":"2","name":"SFB 901 - Project Area A"}],"department":[{"_id":"79"}],"series_title":"Leibniz International Proceedings in Informatics (LIPIcs)","user_id":"477","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."}],"status":"public","file":[{"success":1,"relation":"main_file","content_type":"application/pdf","file_size":692363,"file_id":"1497","file_name":"241-ScheidelerSetzerStrothmann2015.pdf","access_level":"closed","date_updated":"2018-03-21T10:28:21Z","creator":"florida","date_created":"2018-03-21T10:28:21Z"}],"publication":"Proceedings of the 19th International Conference on Principles of Distributed Systems (OPODIS)","type":"conference"},{"year":"2015","title":"Towards a Universal Approach for the Finite Departure Problem in Overlay Networks","date_created":"2017-10-17T12:41:39Z","file":[{"success":1,"relation":"main_file","content_type":"application/pdf","file_size":532792,"access_level":"closed","file_id":"1496","file_name":"242-KSS-SSS2015.pdf","date_updated":"2018-03-21T09:59:32Z","date_created":"2018-03-21T09:59:32Z","creator":"florida"}],"abstract":[{"lang":"eng","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. There are a number of studies for safe node exclusion if the overlay is in a well-defined state, but almost no formal results are known for the case in which the overlay network is in an arbitrary initial state, i.e., when looking for a self-stabilizing solution for excluding leaving nodes. We study this problem in two variants: the Finite Departure Problem (FDP) and the Finite Sleep Problem (FSP). In the FDP the leaving nodes have to irrevocably decide when it is safe to leave the network, whereas in the FSP, this leaving decision does not have to be final: the nodes may resume computation when woken up by an incoming message. We are the first to present a self-stabilizing protocol for the FDP and the FSP that can be combined with a large class of overlay maintenance protocols so that these are then guaranteed to safely exclude leaving nodes from the system from any initial state while operating as specified for the staying nodes. In order to formally define the properties these overlay maintenance protocols have to satisfy, we identify four basic primitives for manipulating edges in an overlay network that might be of independent interest."}],"publication":"Proceedings of the 17th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)","language":[{"iso":"eng"}],"ddc":["040"],"page":"201-216","citation":{"ieee":"A. Koutsopoulos, C. Scheideler, and T. F. Strothmann, “Towards a Universal Approach for the Finite Departure Problem in Overlay Networks,” in <i>Proceedings of the 17th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)</i>, 2015, pp. 201–216.","chicago":"Koutsopoulos, Andreas, Christian Scheideler, and Thim Frederik Strothmann. “Towards a Universal Approach for the Finite Departure Problem in Overlay Networks.” In <i>Proceedings of the 17th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)</i>, 201–16. Lecture Notes in Computer Science, 2015. <a href=\"https://doi.org/10.1007/978-3-319-21741-3_14\">https://doi.org/10.1007/978-3-319-21741-3_14</a>.","ama":"Koutsopoulos A, Scheideler C, Strothmann TF. Towards a Universal Approach for the Finite Departure Problem in Overlay Networks. In: <i>Proceedings of the 17th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)</i>. Lecture Notes in Computer Science. ; 2015:201-216. doi:<a href=\"https://doi.org/10.1007/978-3-319-21741-3_14\">10.1007/978-3-319-21741-3_14</a>","bibtex":"@inproceedings{Koutsopoulos_Scheideler_Strothmann_2015, series={Lecture Notes in Computer Science}, title={Towards a Universal Approach for the Finite Departure Problem in Overlay Networks}, DOI={<a href=\"https://doi.org/10.1007/978-3-319-21741-3_14\">10.1007/978-3-319-21741-3_14</a>}, booktitle={Proceedings of the 17th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)}, author={Koutsopoulos, Andreas and Scheideler, Christian and Strothmann, Thim Frederik}, year={2015}, pages={201–216}, collection={Lecture Notes in Computer Science} }","short":"A. Koutsopoulos, C. Scheideler, T.F. Strothmann, in: Proceedings of the 17th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), 2015, pp. 201–216.","mla":"Koutsopoulos, Andreas, et al. “Towards a Universal Approach for the Finite Departure Problem in Overlay Networks.” <i>Proceedings of the 17th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)</i>, 2015, pp. 201–16, doi:<a href=\"https://doi.org/10.1007/978-3-319-21741-3_14\">10.1007/978-3-319-21741-3_14</a>.","apa":"Koutsopoulos, A., Scheideler, C., &#38; Strothmann, T. F. (2015). Towards a Universal Approach for the Finite Departure Problem in Overlay Networks. In <i>Proceedings of the 17th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)</i> (pp. 201–216). <a href=\"https://doi.org/10.1007/978-3-319-21741-3_14\">https://doi.org/10.1007/978-3-319-21741-3_14</a>"},"has_accepted_license":"1","doi":"10.1007/978-3-319-21741-3_14","author":[{"first_name":"Andreas","last_name":"Koutsopoulos","full_name":"Koutsopoulos, Andreas"},{"first_name":"Christian","full_name":"Scheideler, Christian","id":"20792","last_name":"Scheideler"},{"last_name":"Strothmann","id":"11319","full_name":"Strothmann, Thim Frederik","first_name":"Thim Frederik"}],"date_updated":"2022-01-06T06:56:10Z","status":"public","type":"conference","file_date_updated":"2018-03-21T09:59:32Z","department":[{"_id":"79"}],"series_title":"Lecture Notes in Computer Science","user_id":"477","_id":"242","project":[{"name":"SFB 901","_id":"1"},{"name":"SFB 901 - Subprojekt A1","_id":"5"},{"_id":"2","name":"SFB 901 - Project Area A"}]},{"year":"2015","citation":{"mla":"Strothmann, Thim Frederik. “The Impact of Communication Patterns on Distributed Locally Self-Adjusting Binary Search Trees.” <i>Proceedings of the 9th International Workshop on Algorithms and Computation (WALCOM)</i>, 2015, pp. 175--186, doi:<a href=\"https://doi.org/10.1007/978-3-319-15612-5_16\">10.1007/978-3-319-15612-5_16</a>.","bibtex":"@inproceedings{Strothmann_2015, series={LNCS}, title={The impact of communication patterns on distributed locally self-adjusting binary search trees}, DOI={<a href=\"https://doi.org/10.1007/978-3-319-15612-5_16\">10.1007/978-3-319-15612-5_16</a>}, booktitle={Proceedings of the 9th International Workshop on Algorithms and Computation (WALCOM)}, author={Strothmann, Thim Frederik}, year={2015}, pages={175--186}, collection={LNCS} }","short":"T.F. Strothmann, in: Proceedings of the 9th International Workshop on Algorithms and Computation (WALCOM), 2015, pp. 175--186.","apa":"Strothmann, T. F. (2015). The impact of communication patterns on distributed locally self-adjusting binary search trees. In <i>Proceedings of the 9th International Workshop on Algorithms and Computation (WALCOM)</i> (pp. 175--186). <a href=\"https://doi.org/10.1007/978-3-319-15612-5_16\">https://doi.org/10.1007/978-3-319-15612-5_16</a>","ama":"Strothmann TF. The impact of communication patterns on distributed locally self-adjusting binary search trees. In: <i>Proceedings of the 9th International Workshop on Algorithms and Computation (WALCOM)</i>. LNCS. ; 2015:175--186. doi:<a href=\"https://doi.org/10.1007/978-3-319-15612-5_16\">10.1007/978-3-319-15612-5_16</a>","chicago":"Strothmann, Thim Frederik. “The Impact of Communication Patterns on Distributed Locally Self-Adjusting Binary Search Trees.” In <i>Proceedings of the 9th International Workshop on Algorithms and Computation (WALCOM)</i>, 175--186. LNCS, 2015. <a href=\"https://doi.org/10.1007/978-3-319-15612-5_16\">https://doi.org/10.1007/978-3-319-15612-5_16</a>.","ieee":"T. F. Strothmann, “The impact of communication patterns on distributed locally self-adjusting binary search trees,” in <i>Proceedings of the 9th International Workshop on Algorithms and Computation (WALCOM)</i>, 2015, pp. 175--186."},"page":"175--186","has_accepted_license":"1","title":"The impact of communication patterns on distributed locally self-adjusting binary search trees","doi":"10.1007/978-3-319-15612-5_16","date_updated":"2022-01-06T06:56:17Z","author":[{"first_name":"Thim Frederik","full_name":"Strothmann, Thim Frederik","id":"11319","last_name":"Strothmann"}],"date_created":"2017-10-17T12:41:39Z","abstract":[{"text":"This paper introduces the problem of communication pattern adaption for a distributed self-adjusting binary search tree. We propose a simple local algorithm, which is closely related to the nearly thirty-year-old idea of splay trees and evaluate its adaption performance in the distributed scenario if different communication patterns are provided.To do so, the process of self-adjustment is modeled similarly to a basic network creation game, in which the nodes want to communicate with only a certain subset of all nodes. We show that, in general, the game (i.e., the process of local adjustments) does not converge, and convergence is related to certain structures of the communication interests, which we call conflicts.We classify conflicts and show that for two communication scenarios in which convergence is guaranteed, the self-adjusting tree performs well.Furthermore, we investigate the different classes of conflicts separately and show that, for a certain class of conflicts, the performance of the tree network is asymptotically as good as the performance for converging instances. However, for the other conflict classes, a distributed self-adjusting binary search tree adapts poorly.","lang":"eng"}],"file":[{"date_created":"2018-03-21T09:59:00Z","creator":"florida","date_updated":"2018-03-21T09:59:00Z","file_id":"1495","access_level":"closed","file_name":"243-Strothmann-Walcom2015.pdf","file_size":1003113,"content_type":"application/pdf","relation":"main_file","success":1}],"status":"public","type":"conference","publication":"Proceedings of the 9th International Workshop on Algorithms and Computation (WALCOM)","ddc":["040"],"file_date_updated":"2018-03-21T09:59:00Z","language":[{"iso":"eng"}],"project":[{"name":"SFB 901","_id":"1"},{"name":"SFB 901 - Subprojekt A1","_id":"5"},{"_id":"2","name":"SFB 901 - Project Area A"}],"_id":"243","user_id":"477","series_title":"LNCS","department":[{"_id":"79"}]},{"has_accepted_license":"1","year":"2015","page":"343-344","citation":{"apa":"Markarian, C., &#38; Meyer auf der Heide, F. (2015). Online Resource Leasing. In <i>Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC)</i> (pp. 343–344). <a href=\"https://doi.org/10.1145/2767386.2767454\">https://doi.org/10.1145/2767386.2767454</a>","bibtex":"@inproceedings{Markarian_Meyer auf der Heide_2015, title={Online Resource Leasing}, DOI={<a href=\"https://doi.org/10.1145/2767386.2767454\">10.1145/2767386.2767454</a>}, booktitle={Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC)}, author={Markarian, Christine and Meyer auf der Heide, Friedhelm}, year={2015}, pages={343–344} }","mla":"Markarian, Christine, and Friedhelm Meyer auf der Heide. “Online Resource Leasing.” <i>Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC)</i>, 2015, pp. 343–44, doi:<a href=\"https://doi.org/10.1145/2767386.2767454\">10.1145/2767386.2767454</a>.","short":"C. Markarian, F. Meyer auf der Heide, in: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC), 2015, pp. 343–344.","ama":"Markarian C, Meyer auf der Heide F. Online Resource Leasing. In: <i>Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC)</i>. ; 2015:343-344. doi:<a href=\"https://doi.org/10.1145/2767386.2767454\">10.1145/2767386.2767454</a>","chicago":"Markarian, Christine, and Friedhelm Meyer auf der Heide. “Online Resource Leasing.” In <i>Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC)</i>, 343–44, 2015. <a href=\"https://doi.org/10.1145/2767386.2767454\">https://doi.org/10.1145/2767386.2767454</a>.","ieee":"C. Markarian and F. Meyer auf der Heide, “Online Resource Leasing,” in <i>Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC)</i>, 2015, pp. 343–344."},"date_updated":"2022-01-06T06:57:22Z","author":[{"last_name":"Markarian","id":"37612","full_name":"Markarian, Christine","first_name":"Christine"},{"first_name":"Friedhelm","id":"15523","full_name":"Meyer auf der Heide, Friedhelm","last_name":"Meyer auf der Heide"}],"date_created":"2017-10-17T12:41:44Z","title":"Online Resource Leasing","doi":"10.1145/2767386.2767454","publication":"Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC)","type":"conference","abstract":[{"lang":"eng","text":"Many markets have seen a shift from the idea of buying and moved to leasing instead. Arguably, the latter has been the major catalyst for their success. Ten years ago, research realized this shift and initiated the study of \"online leasing problems\" by introducing leasing to online optimization problems. Resources required to provide a service in an \"online leasing problem\" are no more bought but leased for different durations. In this paper, we provide an overview of results that contribute to the understanding of \"online resource leasing problems\". "}],"status":"public","file":[{"creator":"florida","date_created":"2018-03-21T09:33:11Z","date_updated":"2018-03-21T09:33:11Z","file_name":"266-p343-markarian.pdf","file_id":"1478","access_level":"closed","file_size":679580,"content_type":"application/pdf","relation":"main_file","success":1}],"_id":"266","project":[{"name":"SFB 901","_id":"1"},{"name":"SFB 901 - Subprojekt A1","_id":"5"},{"name":"SFB 901 - Subprojekt C4","_id":"16"},{"_id":"2","name":"SFB 901 - Project Area A"},{"name":"SFB 901 - Project Area C","_id":"4"}],"department":[{"_id":"63"}],"user_id":"15504","ddc":["040"],"file_date_updated":"2018-03-21T09:33:11Z"},{"doi":"10.1016/j.tcs.2014.11.027","title":"A deterministic worst-case message complexity optimal solution for resource discovery","author":[{"full_name":"Kniesburges, Sebastian","last_name":"Kniesburges","first_name":"Sebastian"},{"first_name":"Andreas","full_name":"Koutsopoulos, Andreas","last_name":"Koutsopoulos"},{"first_name":"Christian","id":"20792","full_name":"Scheideler, Christian","last_name":"Scheideler"}],"date_created":"2017-10-17T12:41:55Z","date_updated":"2022-01-06T06:59:08Z","publisher":"Elsevier","page":"67-79","citation":{"short":"S. Kniesburges, A. Koutsopoulos, C. Scheideler, Theoretical Computer Science (2015) 67–79.","bibtex":"@article{Kniesburges_Koutsopoulos_Scheideler_2015, title={A deterministic worst-case message complexity optimal solution for resource discovery}, DOI={<a href=\"https://doi.org/10.1016/j.tcs.2014.11.027\">10.1016/j.tcs.2014.11.027</a>}, journal={Theoretical Computer Science}, publisher={Elsevier}, author={Kniesburges, Sebastian and Koutsopoulos, Andreas and Scheideler, Christian}, year={2015}, pages={67–79} }","mla":"Kniesburges, Sebastian, et al. “A Deterministic Worst-Case Message Complexity Optimal Solution for Resource Discovery.” <i>Theoretical Computer Science</i>, Elsevier, 2015, pp. 67–79, doi:<a href=\"https://doi.org/10.1016/j.tcs.2014.11.027\">10.1016/j.tcs.2014.11.027</a>.","apa":"Kniesburges, S., Koutsopoulos, A., &#38; Scheideler, C. (2015). A deterministic worst-case message complexity optimal solution for resource discovery. <i>Theoretical Computer Science</i>, 67–79. <a href=\"https://doi.org/10.1016/j.tcs.2014.11.027\">https://doi.org/10.1016/j.tcs.2014.11.027</a>","ama":"Kniesburges S, Koutsopoulos A, Scheideler C. A deterministic worst-case message complexity optimal solution for resource discovery. <i>Theoretical Computer Science</i>. 2015:67-79. doi:<a href=\"https://doi.org/10.1016/j.tcs.2014.11.027\">10.1016/j.tcs.2014.11.027</a>","ieee":"S. Kniesburges, A. Koutsopoulos, and C. Scheideler, “A deterministic worst-case message complexity optimal solution for resource discovery,” <i>Theoretical Computer Science</i>, pp. 67–79, 2015.","chicago":"Kniesburges, Sebastian, Andreas Koutsopoulos, and Christian Scheideler. “A Deterministic Worst-Case Message Complexity Optimal Solution for Resource Discovery.” <i>Theoretical Computer Science</i>, 2015, 67–79. <a href=\"https://doi.org/10.1016/j.tcs.2014.11.027\">https://doi.org/10.1016/j.tcs.2014.11.027</a>."},"year":"2015","has_accepted_license":"1","file_date_updated":"2018-03-20T07:38:02Z","ddc":["040"],"department":[{"_id":"79"}],"user_id":"477","_id":"327","project":[{"name":"SFB 901","_id":"1"},{"_id":"5","name":"SFB 901 - Subprojekt A1"},{"name":"SFB 901 - Project Area A","_id":"2"}],"status":"public","file":[{"content_type":"application/pdf","success":1,"relation":"main_file","date_updated":"2018-03-20T07:38:02Z","creator":"florida","date_created":"2018-03-20T07:38:02Z","file_size":398044,"access_level":"closed","file_id":"1427","file_name":"327-KKS15-TOCS_01.pdf"}],"abstract":[{"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 address 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)O(n)) or bits (O(nlog⁡n)O(nlog⁡n)) a node receives or sends coincides with the lower bound, while ensuring only a linear runtime (O(n)O(n)) on the number of rounds.","lang":"eng"}],"publication":"Theoretical Computer Science","type":"journal_article"},{"project":[{"name":"SFB 901","_id":"1"},{"name":"SFB 901 - Subproject A1","_id":"5"},{"name":"SFB 901 - Project Area A","_id":"2"}],"_id":"304","user_id":"15504","department":[{"_id":"79"}],"ddc":["040"],"file_date_updated":"2018-03-20T07:46:19Z","type":"dissertation","file":[{"date_created":"2018-03-20T07:46:19Z","creator":"florida","date_updated":"2018-03-20T07:46:19Z","file_name":"304-Dissertation_-_Koutsopoulos.pdf","access_level":"closed","file_id":"1441","file_size":2275834,"content_type":"application/pdf","relation":"main_file","success":1}],"status":"public","date_updated":"2022-01-06T06:58:53Z","publisher":"Universität Paderborn","author":[{"first_name":"Andreas","last_name":"Koutsopoulos","full_name":"Koutsopoulos, Andreas"}],"date_created":"2017-10-17T12:41:51Z","supervisor":[{"first_name":"Christian","last_name":"Scheideler","full_name":"Scheideler, Christian","id":"20792"}],"title":"Dynamics and Efficiency in Topological Self-Stabilization","has_accepted_license":"1","year":"2015","citation":{"ieee":"A. Koutsopoulos, <i>Dynamics and Efficiency in Topological Self-Stabilization</i>. Universität Paderborn, 2015.","chicago":"Koutsopoulos, Andreas. <i>Dynamics and Efficiency in Topological Self-Stabilization</i>. Universität Paderborn, 2015.","ama":"Koutsopoulos A. <i>Dynamics and Efficiency in Topological Self-Stabilization</i>. Universität Paderborn; 2015.","mla":"Koutsopoulos, Andreas. <i>Dynamics and Efficiency in Topological Self-Stabilization</i>. Universität Paderborn, 2015.","short":"A. Koutsopoulos, Dynamics and Efficiency in Topological Self-Stabilization, Universität Paderborn, 2015.","bibtex":"@book{Koutsopoulos_2015, title={Dynamics and Efficiency in Topological Self-Stabilization}, publisher={Universität Paderborn}, author={Koutsopoulos, Andreas}, year={2015} }","apa":"Koutsopoulos, A. (2015). <i>Dynamics and Efficiency in Topological Self-Stabilization</i>. Universität Paderborn."}},{"type":"dissertation","status":"public","file":[{"success":1,"relation":"main_file","content_type":"application/pdf","file_size":1709094,"file_id":"1206","file_name":"305-Dissertation_-_Kniesburges.pdf","access_level":"closed","date_updated":"2018-03-13T09:14:43Z","date_created":"2018-03-13T09:14:43Z","creator":"florida"}],"_id":"305","project":[{"name":"SFB 901","_id":"1"},{"name":"SFB 901 - Project Area A","_id":"2"},{"_id":"4","name":"SFB 901 - Project Area C"},{"name":"SFB 901 - Subproject A1","_id":"5"},{"name":"SFB 901 - Subproject C1","_id":"13"}],"department":[{"_id":"79"}],"user_id":"15504","ddc":["040"],"file_date_updated":"2018-03-13T09:14:43Z","has_accepted_license":"1","year":"2015","citation":{"ama":"Kniesburges S. <i>Distributed Data Structures and the Power of Topological Self-Stabilization</i>. Universität Paderborn; 2015.","ieee":"S. Kniesburges, <i>Distributed Data Structures and the Power of topological Self-Stabilization</i>. Universität Paderborn, 2015.","chicago":"Kniesburges, Sebastian. <i>Distributed Data Structures and the Power of Topological Self-Stabilization</i>. Universität Paderborn, 2015.","bibtex":"@book{Kniesburges_2015, title={Distributed Data Structures and the Power of topological Self-Stabilization}, publisher={Universität Paderborn}, author={Kniesburges, Sebastian}, year={2015} }","mla":"Kniesburges, Sebastian. <i>Distributed Data Structures and the Power of Topological Self-Stabilization</i>. Universität Paderborn, 2015.","short":"S. Kniesburges, Distributed Data Structures and the Power of Topological Self-Stabilization, Universität Paderborn, 2015.","apa":"Kniesburges, S. (2015). <i>Distributed Data Structures and the Power of topological Self-Stabilization</i>. Universität Paderborn."},"publisher":"Universität Paderborn","date_updated":"2022-01-06T06:58:54Z","supervisor":[{"first_name":"Christian","full_name":"Scheideler, Christian","id":"20792","last_name":"Scheideler"}],"date_created":"2017-10-17T12:41:51Z","author":[{"full_name":"Kniesburges, Sebastian","last_name":"Kniesburges","first_name":"Sebastian"}],"title":"Distributed Data Structures and the Power of topological Self-Stabilization"}]