--- _id: '125' 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.' author: - first_name: Michael full_name: Feldmann, Michael id: '23538' last_name: Feldmann - first_name: Christian full_name: Scheideler, Christian id: '20792' last_name: Scheideler citation: ama: 'Feldmann M, Scheideler C. A Self-Stabilizing General De Bruijn Graph. In: Proceedings of the 19th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS). Vol 10616. Lecture Notes in Computer Science. Springer, Cham; 2017:250-264. doi:10.1007/978-3-319-69084-1_17' apa: Feldmann, M., & Scheideler, C. (2017). A Self-Stabilizing General De Bruijn Graph. In Proceedings of the 19th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS) (Vol. 10616, pp. 250–264). Springer, Cham. https://doi.org/10.1007/978-3-319-69084-1_17 bibtex: '@inproceedings{Feldmann_Scheideler_2017, series={Lecture Notes in Computer Science}, title={A Self-Stabilizing General De Bruijn Graph}, volume={10616}, DOI={10.1007/978-3-319-69084-1_17}, 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} }' chicago: Feldmann, Michael, and Christian Scheideler. “A Self-Stabilizing General De Bruijn Graph.” In Proceedings of the 19th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), 10616:250–64. Lecture Notes in Computer Science. Springer, Cham, 2017. https://doi.org/10.1007/978-3-319-69084-1_17. ieee: M. Feldmann and C. Scheideler, “A Self-Stabilizing General De Bruijn Graph,” in Proceedings of the 19th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), 2017, vol. 10616, pp. 250–264. mla: Feldmann, Michael, and Christian Scheideler. “A Self-Stabilizing General De Bruijn Graph.” Proceedings of the 19th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), vol. 10616, Springer, Cham, 2017, pp. 250–64, doi:10.1007/978-3-319-69084-1_17. 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.' date_created: 2017-10-17T12:41:16Z date_updated: 2022-01-06T06:51:19Z ddc: - '040' department: - _id: '79' doi: 10.1007/978-3-319-69084-1_17 external_id: arxiv: - '1708.06542' file: - access_level: closed content_type: application/pdf creator: mfeldma2 date_created: 2018-10-31T13:30:13Z date_updated: 2018-10-31T13:30:13Z file_id: '5214' file_name: Feldmann-Scheideler2017_Chapter_ASelf-stabilizingGeneralDeBrui.pdf file_size: 311204 relation: main_file success: 1 file_date_updated: 2018-10-31T13:30:13Z has_accepted_license: '1' intvolume: ' 10616' language: - iso: eng page: '250-264 ' project: - _id: '1' name: SFB 901 - _id: '5' name: SFB 901 - Subprojekt A1 - _id: '2' name: SFB 901 - Project Area A publication: Proceedings of the 19th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS) publication_identifier: isbn: - 978-3-319-69083-4 publication_status: published publisher: Springer, Cham series_title: Lecture Notes in Computer Science status: public title: A Self-Stabilizing General De Bruijn Graph type: conference user_id: '23538' volume: 10616 year: '2017' ... --- _id: '177' 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.' author: - first_name: Faisal N. full_name: Abu-Khzam, Faisal N. last_name: Abu-Khzam - first_name: Shouwei full_name: Li, Shouwei last_name: Li - first_name: Christine full_name: Markarian, Christine id: '37612' last_name: Markarian - first_name: Friedhelm full_name: Meyer auf der Heide, Friedhelm id: '15523' last_name: Meyer auf der Heide - first_name: Pavel full_name: Podlipyan, Pavel last_name: Podlipyan citation: 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: Proceedings of the 10th International Conference on Combinatorial Optimization and Applications (COCOA). LNCS. ; 2016:477-488. doi:10.1007/978-3-319-48749-6_35' apa: Abu-Khzam, F. N., Li, S., Markarian, C., Meyer auf der Heide, F., & Podlipyan, P. (2016). On the Parameterized Parallel Complexity and the Vertex Cover Problem. In Proceedings of the 10th International Conference on Combinatorial Optimization and Applications (COCOA) (pp. 477–488). https://doi.org/10.1007/978-3-319-48749-6_35 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={10.1007/978-3-319-48749-6_35}, 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} }' 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 Proceedings of the 10th International Conference on Combinatorial Optimization and Applications (COCOA), 477–88. LNCS, 2016. https://doi.org/10.1007/978-3-319-48749-6_35. 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 Proceedings of the 10th International Conference on Combinatorial Optimization and Applications (COCOA), 2016, pp. 477–488. mla: Abu-Khzam, Faisal N., et al. “On the Parameterized Parallel Complexity and the Vertex Cover Problem.” Proceedings of the 10th International Conference on Combinatorial Optimization and Applications (COCOA), 2016, pp. 477–88, doi:10.1007/978-3-319-48749-6_35. 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.' date_created: 2017-10-17T12:41:26Z date_updated: 2022-01-06T06:53:17Z ddc: - '000' department: - _id: '63' doi: 10.1007/978-3-319-48749-6_35 file: - access_level: closed content_type: application/pdf creator: ups date_created: 2018-11-02T14:15:18Z date_updated: 2018-11-02T14:15:18Z file_id: '5266' file_name: OnTheParameterizedParallelComp.pdf file_size: 293345 relation: main_file success: 1 file_date_updated: 2018-11-02T14:15:18Z has_accepted_license: '1' language: - iso: eng page: 477-488 project: - _id: '1' name: SFB 901 - _id: '5' name: SFB 901 - Subprojekt A1 - _id: '2' name: SFB 901 - Project Area A publication: Proceedings of the 10th International Conference on Combinatorial Optimization and Applications (COCOA) series_title: LNCS status: public title: On the Parameterized Parallel Complexity and the Vertex Cover Problem type: conference user_id: '477' year: '2016' ... --- _id: '187' citation: ama: Meyer auf der Heide F, ed. Introduction to the Special Issue on SPAA 2014.; 2016. doi:10.1145/2936716 apa: Meyer auf der Heide, F. (Ed.). (2016). Introduction to the Special Issue on SPAA 2014. Transactions on Parallel Computing (TOPC). https://doi.org/10.1145/2936716 bibtex: '@book{Meyer auf der Heide_2016, title={Introduction to the Special Issue on SPAA 2014}, DOI={10.1145/2936716}, number={1}, journal={Transactions on Parallel Computing (TOPC)}, year={2016} }' chicago: Meyer auf der Heide, Friedhelm, ed. Introduction to the Special Issue on SPAA 2014. Transactions on Parallel Computing (TOPC), 2016. https://doi.org/10.1145/2936716. ieee: F. Meyer auf der Heide, Ed., Introduction to the Special Issue on SPAA 2014, no. 1. 2016. mla: Meyer auf der Heide, Friedhelm, editor. “Introduction to the Special Issue on SPAA 2014.” Transactions on Parallel Computing (TOPC), no. 1, 2016, doi:10.1145/2936716. short: F. Meyer auf der Heide, ed., Introduction to the Special Issue on SPAA 2014, 2016. date_created: 2017-10-17T12:41:28Z date_updated: 2022-01-06T06:53:51Z ddc: - '040' department: - _id: '63' doi: 10.1145/2936716 editor: - first_name: Friedhelm full_name: Meyer auf der Heide, Friedhelm id: '15523' last_name: Meyer auf der Heide file: - access_level: closed content_type: application/pdf creator: florida date_created: 2018-03-21T12:31:42Z date_updated: 2018-03-21T12:31:42Z file_id: '1531' file_name: 187-a1-heide.pdf file_size: 34053 relation: main_file success: 1 file_date_updated: 2018-03-21T12:31:42Z has_accepted_license: '1' issue: '1' page: '1' project: - _id: '1' name: SFB 901 - _id: '5' name: SFB 901 - Subprojekt A1 - _id: '2' name: SFB 901 - Project Area A publication: Transactions on Parallel Computing (TOPC) status: public title: Introduction to the Special Issue on SPAA 2014 type: journal_editor user_id: '15504' year: '2016' ... --- _id: '5762' abstract: - lang: eng 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." author: - first_name: Thim Frederik full_name: Strothmann, Thim Frederik id: '11319' last_name: Strothmann citation: ama: Strothmann TF. The Impact of Communication Patterns on Distributed Self-Adjusting Binary Search Tree. Journal of Graph Algorithms and Applications. 2016;20(1):79-100. doi:10.7155/jgaa.00385 apa: Strothmann, T. F. (2016). The Impact of Communication Patterns on Distributed Self-Adjusting Binary Search Tree. Journal of Graph Algorithms and Applications, 20(1), 79–100. https://doi.org/10.7155/jgaa.00385 bibtex: '@article{Strothmann_2016, title={The Impact of Communication Patterns on Distributed Self-Adjusting Binary Search Tree}, volume={20}, DOI={10.7155/jgaa.00385}, 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} }' chicago: 'Strothmann, Thim Frederik. “The Impact of Communication Patterns on Distributed Self-Adjusting Binary Search Tree.” Journal of Graph Algorithms and Applications 20, no. 1 (2016): 79–100. https://doi.org/10.7155/jgaa.00385.' ieee: T. F. Strothmann, “The Impact of Communication Patterns on Distributed Self-Adjusting Binary Search Tree,” Journal of Graph Algorithms and Applications, vol. 20, no. 1, pp. 79–100, 2016. mla: Strothmann, Thim Frederik. “The Impact of Communication Patterns on Distributed Self-Adjusting Binary Search Tree.” Journal of Graph Algorithms and Applications, vol. 20, no. 1, Journal of Graph Algorithms and Applications, 2016, pp. 79–100, doi:10.7155/jgaa.00385. short: T.F. Strothmann, Journal of Graph Algorithms and Applications 20 (2016) 79–100. date_created: 2018-11-19T15:33:50Z date_updated: 2022-01-06T07:02:38Z ddc: - '040' department: - _id: '79' doi: 10.7155/jgaa.00385 file: - access_level: closed content_type: application/pdf creator: thim date_created: 2018-11-27T11:58:08Z date_updated: 2018-11-27T11:58:08Z file_id: '5912' file_name: Strothmann2016.20.1.pdf file_size: 2324066 relation: main_file success: 1 file_date_updated: 2018-11-27T11:58:08Z has_accepted_license: '1' intvolume: ' 20' issue: '1' language: - iso: eng page: 79-100 project: - _id: '1' name: SFB 901 - _id: '2' name: SFB 901 - Project Area A - _id: '5' name: SFB 901 - Subproject A1 publication: Journal of Graph Algorithms and Applications publication_identifier: issn: - 1526-1719 publication_status: published publisher: Journal of Graph Algorithms and Applications quality_controlled: '1' status: public title: The Impact of Communication Patterns on Distributed Self-Adjusting Binary Search Tree type: journal_article user_id: '477' volume: 20 year: '2016' ... --- _id: '688' author: - first_name: Damian full_name: Kutzias, Damian last_name: Kutzias citation: ama: Kutzias D. Friendship Processes in Network Creation Games. Universität Paderborn; 2016. apa: Kutzias, D. (2016). Friendship Processes in Network Creation Games. Universität Paderborn. bibtex: '@book{Kutzias_2016, title={Friendship Processes in Network Creation Games}, publisher={Universität Paderborn}, author={Kutzias, Damian}, year={2016} }' chicago: Kutzias, Damian. Friendship Processes in Network Creation Games. Universität Paderborn, 2016. ieee: D. Kutzias, Friendship Processes in Network Creation Games. Universität Paderborn, 2016. mla: Kutzias, Damian. Friendship Processes in Network Creation Games. Universität Paderborn, 2016. short: D. Kutzias, Friendship Processes in Network Creation Games, Universität Paderborn, 2016. date_created: 2017-11-14T06:50:35Z date_updated: 2022-01-06T07:03:23Z department: - _id: '63' language: - iso: eng project: - _id: '1' name: SFB 901 - _id: '5' name: SFB 901 - Subprojekt A1 - _id: '2' name: SFB 901 - Project Area A publisher: Universität Paderborn status: public supervisor: - first_name: Friedhelm full_name: Meyer auf der Heide, Friedhelm id: '15523' last_name: Meyer auf der Heide title: Friendship Processes in Network Creation Games type: mastersthesis user_id: '477' year: '2016' ... --- _id: '689' author: - first_name: Johannes Sebastian full_name: Schaefer, Johannes Sebastian id: '30291' last_name: Schaefer citation: ama: Schaefer JS. Routing Algorithms on Delayed Networks for Disaster Management Support. Universität Paderborn; 2016. apa: Schaefer, J. S. (2016). Routing Algorithms on Delayed Networks for Disaster Management Support. Universität Paderborn. bibtex: '@book{Schaefer_2016, title={Routing Algorithms on Delayed Networks for Disaster Management Support}, publisher={Universität Paderborn}, author={Schaefer, Johannes Sebastian}, year={2016} }' chicago: Schaefer, Johannes Sebastian. Routing Algorithms on Delayed Networks for Disaster Management Support. Universität Paderborn, 2016. ieee: J. S. Schaefer, Routing Algorithms on Delayed Networks for Disaster Management Support. Universität Paderborn, 2016. mla: Schaefer, Johannes Sebastian. Routing Algorithms on Delayed Networks for Disaster Management Support. Universität Paderborn, 2016. short: J.S. Schaefer, Routing Algorithms on Delayed Networks for Disaster Management Support, Universität Paderborn, 2016. date_created: 2017-11-14T06:51:37Z date_updated: 2022-01-06T07:03:23Z department: - _id: '63' language: - iso: eng project: - _id: '1' name: SFB 901 - _id: '5' name: SFB 901 - Subprojekt A1 - _id: '2' name: SFB 901 - Project Area A publisher: Universität Paderborn status: public supervisor: - first_name: Friedhelm full_name: Meyer auf der Heide, Friedhelm id: '15523' last_name: Meyer auf der Heide title: Routing Algorithms on Delayed Networks for Disaster Management Support type: mastersthesis user_id: '477' year: '2016' ... --- _id: '154' author: - first_name: Andreas full_name: Cord-Landwehr, Andreas last_name: Cord-Landwehr citation: ama: Cord-Landwehr A. Selfish Network Creation - On Variants of Network Creation Games. Vol 353. Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn; 2016. apa: Cord-Landwehr, A. (2016). Selfish Network Creation - On Variants of Network Creation Games (Vol. 353). Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn. 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} }' chicago: Cord-Landwehr, Andreas. Selfish Network Creation - On Variants of Network Creation Games. Vol. 353. Verlagsschriftenreihe Des Heinz Nixdorf Instituts, Paderborn. Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn, 2016. ieee: A. Cord-Landwehr, Selfish Network Creation - On Variants of Network Creation Games, vol. 353. Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn, 2016. mla: Cord-Landwehr, Andreas. Selfish Network Creation - On Variants of Network Creation Games. 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. date_created: 2017-10-17T12:41:22Z date_updated: 2022-01-06T06:52:23Z ddc: - '040' department: - _id: '63' - _id: '26' file: - access_level: closed content_type: application/pdf creator: florida date_created: 2018-03-21T12:52:03Z date_updated: 2018-03-21T12:52:03Z file_id: '1551' file_name: 154-dissertation.pdf file_size: 800101 relation: main_file success: 1 file_date_updated: 2018-03-21T12:52:03Z has_accepted_license: '1' intvolume: ' 353' language: - iso: eng project: - _id: '1' name: SFB 901 - _id: '5' name: SFB 901 - Subprojekt A1 - _id: '2' name: SFB 901 - Project Area A publication_identifier: isbn: - 978-3-942647-72-4 publisher: Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn related_material: link: - relation: confirmation url: http://nbn-resolving.de/urn:nbn:de:hbz:466:2-24089 series_title: Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn status: public supervisor: - first_name: Friedhelm full_name: Meyer auf der Heide, Friedhelm id: '15523' last_name: Meyer auf der Heide title: Selfish Network Creation - On Variants of Network Creation Games type: dissertation user_id: '5786' volume: 353 year: '2016' ... --- _id: '149' 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(√α).' author: - first_name: Maximilian full_name: Drees, Maximilian last_name: Drees - first_name: Björn full_name: Feldkord, Björn id: '22704' last_name: Feldkord - first_name: Alexander full_name: Skopalik, Alexander id: '40384' last_name: Skopalik citation: ama: 'Drees M, Feldkord B, Skopalik A. Strategic Online Facility Location. In: Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA). LNCS. ; 2016:593--607. doi:10.1007/978-3-319-48749-6_43' apa: Drees, M., Feldkord, B., & Skopalik, A. (2016). Strategic Online Facility Location. In Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA) (pp. 593--607). https://doi.org/10.1007/978-3-319-48749-6_43 bibtex: '@inproceedings{Drees_Feldkord_Skopalik_2016, series={LNCS}, title={Strategic Online Facility Location}, DOI={10.1007/978-3-319-48749-6_43}, 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} }' chicago: Drees, Maximilian, Björn Feldkord, and Alexander Skopalik. “Strategic Online Facility Location.” In Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA), 593--607. LNCS, 2016. https://doi.org/10.1007/978-3-319-48749-6_43. ieee: M. Drees, B. Feldkord, and A. Skopalik, “Strategic Online Facility Location,” in Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA), 2016, pp. 593--607. mla: Drees, Maximilian, et al. “Strategic Online Facility Location.” Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA), 2016, pp. 593--607, doi:10.1007/978-3-319-48749-6_43. 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.' date_created: 2017-10-17T12:41:21Z date_updated: 2022-01-06T06:52:10Z ddc: - '040' department: - _id: '63' - _id: '541' doi: 10.1007/978-3-319-48749-6_43 file: - access_level: closed content_type: application/pdf creator: florida date_created: 2018-03-21T12:55:43Z date_updated: 2018-03-21T12:55:43Z file_id: '1553' file_name: 149-chp_3A10.1007_2F978-3-319-48749-6_43.pdf file_size: 236253 relation: main_file success: 1 file_date_updated: 2018-03-21T12:55:43Z has_accepted_license: '1' language: - iso: eng page: 593--607 project: - _id: '1' name: SFB 901 - _id: '5' name: SFB 901 - Subprojekt A1 - _id: '7' name: SFB 901 - Subproject A3 - _id: '2' name: SFB 901 - Project Area A publication: Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA) series_title: LNCS status: public title: Strategic Online Facility Location type: conference user_id: '477' year: '2016' ... --- _id: '139' abstract: - lang: eng 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).' author: - first_name: Sebastian full_name: Abshoff, Sebastian last_name: Abshoff - first_name: Peter full_name: Kling, Peter last_name: Kling - first_name: Christine full_name: Markarian, Christine id: '37612' last_name: Markarian - first_name: Friedhelm full_name: Meyer auf der Heide, Friedhelm id: '15523' last_name: Meyer auf der Heide - first_name: 'Peter ' full_name: 'Pietrzyk, Peter ' last_name: Pietrzyk citation: ama: Abshoff S, Kling P, Markarian C, Meyer auf der Heide F, Pietrzyk P. Towards the price of leasing online. Journal of Combinatorial Optimization. 2016;(4):1197--1216. doi:10.1007/s10878-015-9915-5 apa: Abshoff, S., Kling, P., Markarian, C., Meyer auf der Heide, F., & Pietrzyk, P. (2016). Towards the price of leasing online. Journal of Combinatorial Optimization, (4), 1197--1216. https://doi.org/10.1007/s10878-015-9915-5 bibtex: '@article{Abshoff_Kling_Markarian_Meyer auf der Heide_Pietrzyk_2016, title={Towards the price of leasing online}, DOI={10.1007/s10878-015-9915-5}, 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} }' chicago: 'Abshoff, Sebastian, Peter Kling, Christine Markarian, Friedhelm Meyer auf der Heide, and Peter Pietrzyk. “Towards the Price of Leasing Online.” Journal of Combinatorial Optimization, no. 4 (2016): 1197--1216. https://doi.org/10.1007/s10878-015-9915-5.' ieee: S. Abshoff, P. Kling, C. Markarian, F. Meyer auf der Heide, and P. Pietrzyk, “Towards the price of leasing online,” Journal of Combinatorial Optimization, no. 4, pp. 1197--1216, 2016. mla: Abshoff, Sebastian, et al. “Towards the Price of Leasing Online.” Journal of Combinatorial Optimization, no. 4, Springer, 2016, pp. 1197--1216, doi:10.1007/s10878-015-9915-5. short: S. Abshoff, P. Kling, C. Markarian, F. Meyer auf der Heide, P. Pietrzyk, Journal of Combinatorial Optimization (2016) 1197--1216. date_created: 2017-10-17T12:41:18Z date_updated: 2022-01-06T06:51:46Z ddc: - '000' department: - _id: '63' doi: 10.1007/s10878-015-9915-5 file: - access_level: closed content_type: application/pdf creator: ups date_created: 2018-11-02T15:57:25Z date_updated: 2018-11-02T15:57:25Z file_id: '5318' file_name: Abshoff-TowardsThePriceOfLeasingOnline.pdf file_size: 654903 relation: main_file success: 1 file_date_updated: 2018-11-02T15:57:25Z has_accepted_license: '1' issue: '4' language: - iso: eng page: ' 1197--1216' project: - _id: '1' name: SFB 901 - _id: '5' name: SFB 901 - Subprojekt A1 - _id: '16' name: SFB 901 - Subprojekt C4 - _id: '2' name: SFB 901 - Project Area A - _id: '4' name: SFB 901 - Project Area C publication: Journal of Combinatorial Optimization publisher: Springer status: public title: Towards the price of leasing online type: journal_article user_id: '477' year: '2016' ... --- _id: '142' 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. author: - first_name: Christian full_name: Scheideler, Christian id: '20792' last_name: Scheideler - first_name: Alexander full_name: Setzer, Alexander id: '11108' last_name: Setzer - first_name: Thim Frederik full_name: Strothmann, Thim Frederik id: '11319' last_name: Strothmann citation: ama: 'Scheideler C, Setzer A, Strothmann TF. Towards a Universal Approach for Monotonic Searchability in Self-stabilizing Overlay Networks. In: Proceedings of the 30th International Symposium on Distributed Computing (DISC). LNCS. ; 2016:71--84. doi:10.1007/978-3-662-53426-7_6' apa: Scheideler, C., Setzer, A., & Strothmann, T. F. (2016). Towards a Universal Approach for Monotonic Searchability in Self-stabilizing Overlay Networks. In Proceedings of the 30th International Symposium on Distributed Computing (DISC) (pp. 71--84). https://doi.org/10.1007/978-3-662-53426-7_6 bibtex: '@inproceedings{Scheideler_Setzer_Strothmann_2016, series={LNCS}, title={Towards a Universal Approach for Monotonic Searchability in Self-stabilizing Overlay Networks}, DOI={10.1007/978-3-662-53426-7_6}, 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} }' chicago: Scheideler, Christian, Alexander Setzer, and Thim Frederik Strothmann. “Towards a Universal Approach for Monotonic Searchability in Self-Stabilizing Overlay Networks.” In Proceedings of the 30th International Symposium on Distributed Computing (DISC), 71--84. LNCS, 2016. https://doi.org/10.1007/978-3-662-53426-7_6. ieee: C. Scheideler, A. Setzer, and T. F. Strothmann, “Towards a Universal Approach for Monotonic Searchability in Self-stabilizing Overlay Networks,” in Proceedings of the 30th International Symposium on Distributed Computing (DISC), 2016, pp. 71--84. mla: Scheideler, Christian, et al. “Towards a Universal Approach for Monotonic Searchability in Self-Stabilizing Overlay Networks.” Proceedings of the 30th International Symposium on Distributed Computing (DISC), 2016, pp. 71--84, doi:10.1007/978-3-662-53426-7_6. short: 'C. Scheideler, A. Setzer, T.F. Strothmann, in: Proceedings of the 30th International Symposium on Distributed Computing (DISC), 2016, pp. 71--84.' date_created: 2017-10-17T12:41:19Z date_updated: 2022-01-06T06:51:56Z ddc: - '040' department: - _id: '79' doi: 10.1007/978-3-662-53426-7_6 file: - access_level: closed content_type: application/pdf creator: florida date_created: 2018-03-21T12:59:29Z date_updated: 2018-03-21T12:59:29Z file_id: '1558' file_name: 142-SchSetStrDISC16.pdf file_size: 209638 relation: main_file success: 1 file_date_updated: 2018-03-21T12:59:29Z has_accepted_license: '1' language: - iso: eng page: 71--84 project: - _id: '1' name: SFB 901 - _id: '5' name: SFB 901 - Subprojekt A1 - _id: '2' name: SFB 901 - Project Area A publication: Proceedings of the 30th International Symposium on Distributed Computing (DISC) series_title: LNCS status: public title: Towards a Universal Approach for Monotonic Searchability in Self-stabilizing Overlay Networks type: conference user_id: '477' year: '2016' ... --- _id: '143' abstract: - lang: eng 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].' author: - first_name: 'Faisal N. ' full_name: 'Abu-Khzam, Faisal N. ' last_name: Abu-Khzam - first_name: Shouwei full_name: Li, Shouwei last_name: Li - first_name: Christine full_name: Markarian, Christine id: '37612' last_name: Markarian - first_name: Friedhelm full_name: Meyer auf der Heide, Friedhelm id: '15523' last_name: Meyer auf der Heide - first_name: Pavel full_name: Podlipyan, Pavel last_name: Podlipyan citation: 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: Proceedings of the 22nd International Conference on Computing and Combinatorics (COCOON). LNCS. ; 2016:92-102. doi:10.1007/978-3-319-42634-1_8' apa: Abu-Khzam, F. N., Li, S., Markarian, C., Meyer auf der Heide, F., & Podlipyan, P. (2016). The Monotone Circuit Value Problem with Bounded Genus Is in NC. In Proceedings of the 22nd International Conference on Computing and Combinatorics (COCOON) (pp. 92–102). https://doi.org/10.1007/978-3-319-42634-1_8 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={10.1007/978-3-319-42634-1_8}, 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} }' 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 Proceedings of the 22nd International Conference on Computing and Combinatorics (COCOON), 92–102. LNCS, 2016. https://doi.org/10.1007/978-3-319-42634-1_8. 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 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.” Proceedings of the 22nd International Conference on Computing and Combinatorics (COCOON), 2016, pp. 92–102, doi:10.1007/978-3-319-42634-1_8. 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.' date_created: 2017-10-17T12:41:19Z date_updated: 2022-01-06T06:51:57Z ddc: - '000' department: - _id: '63' doi: 10.1007/978-3-319-42634-1_8 file: - access_level: closed content_type: application/pdf creator: ups date_created: 2018-11-02T14:20:45Z date_updated: 2018-11-02T14:20:45Z file_id: '5269' file_name: TheMonotoneCircuitValueProblem.pdf file_size: 234587 relation: main_file success: 1 file_date_updated: 2018-11-02T14:20:45Z has_accepted_license: '1' language: - iso: eng page: 92-102 project: - _id: '1' name: SFB 901 - _id: '5' name: SFB 901 - Subprojekt A1 - _id: '2' name: SFB 901 - Project Area A publication: Proceedings of the 22nd International Conference on Computing and Combinatorics (COCOON) series_title: LNCS status: public title: The Monotone Circuit Value Problem with Bounded Genus Is in NC type: conference user_id: '477' year: '2016' ... --- _id: '145' 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. ' author: - first_name: Matthias full_name: Feldotto, Matthias id: '14052' last_name: Feldotto orcid: 0000-0003-1348-6516 - first_name: Kalman full_name: Graffi, Kalman last_name: Graffi citation: ama: 'Feldotto M, Graffi K. Systematic evaluation of peer-to-peer systems using PeerfactSim.KOM. Concurrency and Computation: Practice and Experience. 2016;28(5):1655-1677. doi:10.1002/cpe.3716' apa: 'Feldotto, M., & Graffi, K. (2016). Systematic evaluation of peer-to-peer systems using PeerfactSim.KOM. Concurrency and Computation: Practice and Experience, 28(5), 1655–1677. https://doi.org/10.1002/cpe.3716' bibtex: '@article{Feldotto_Graffi_2016, title={Systematic evaluation of peer-to-peer systems using PeerfactSim.KOM}, volume={28}, DOI={10.1002/cpe.3716}, number={5}, journal={Concurrency and Computation: Practice and Experience}, publisher={Wiley Online Library}, author={Feldotto, Matthias and Graffi, Kalman}, year={2016}, pages={1655–1677} }' chicago: 'Feldotto, Matthias, and Kalman Graffi. “Systematic Evaluation of Peer-to-Peer Systems Using PeerfactSim.KOM.” Concurrency and Computation: Practice and Experience 28, no. 5 (2016): 1655–77. https://doi.org/10.1002/cpe.3716.' ieee: 'M. Feldotto and K. Graffi, “Systematic evaluation of peer-to-peer systems using PeerfactSim.KOM,” Concurrency and Computation: Practice and Experience, vol. 28, no. 5, pp. 1655–1677, 2016.' mla: 'Feldotto, Matthias, and Kalman Graffi. “Systematic Evaluation of Peer-to-Peer Systems Using PeerfactSim.KOM.” Concurrency and Computation: Practice and Experience, vol. 28, no. 5, Wiley Online Library, 2016, pp. 1655–77, doi:10.1002/cpe.3716.' short: 'M. Feldotto, K. Graffi, Concurrency and Computation: Practice and Experience 28 (2016) 1655–1677.' date_created: 2017-10-17T12:41:20Z date_updated: 2022-01-06T06:52:00Z ddc: - '040' department: - _id: '79' - _id: '63' - _id: '541' doi: 10.1002/cpe.3716 file: - access_level: closed content_type: application/pdf creator: florida date_created: 2018-03-21T12:57:57Z date_updated: 2018-03-21T12:57:57Z file_id: '1556' file_name: 145-Feldotto_et_al-2016-Concurrency_and_Computation-_Practice_and_Experience.pdf file_size: 3121363 relation: main_file success: 1 file_date_updated: 2018-03-21T12:57:57Z has_accepted_license: '1' intvolume: ' 28' issue: '5' page: 1655-1677 project: - _id: '1' name: SFB 901 - _id: '5' name: SFB 901 - Subprojekt A1 - _id: '2' name: SFB 901 - Project Area A publication: 'Concurrency and Computation: Practice and Experience' publication_status: published publisher: Wiley Online Library status: public title: Systematic evaluation of peer-to-peer systems using PeerfactSim.KOM type: journal_article user_id: '14052' volume: 28 year: '2016' ... --- _id: '281' author: - first_name: Tobias full_name: Rojahn, Tobias last_name: Rojahn citation: ama: Rojahn T. Load Balancing for Range Queries in a Dimension Invariant Peer-to-Peer Network. Universität Paderborn; 2015. apa: Rojahn, T. (2015). Load Balancing for Range Queries in a Dimension Invariant Peer-to-Peer Network. Universität Paderborn. 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} }' chicago: Rojahn, Tobias. Load Balancing for Range Queries in a Dimension Invariant Peer-to-Peer Network. Universität Paderborn, 2015. ieee: T. Rojahn, Load Balancing for Range Queries in a Dimension Invariant Peer-to-Peer Network. Universität Paderborn, 2015. mla: Rojahn, Tobias. Load Balancing for Range Queries in a Dimension Invariant Peer-to-Peer Network. Universität Paderborn, 2015. short: T. Rojahn, Load Balancing for Range Queries in a Dimension Invariant Peer-to-Peer Network, Universität Paderborn, 2015. date_created: 2017-10-17T12:41:46Z date_updated: 2022-01-06T06:57:51Z project: - _id: '1' name: SFB 901 - _id: '5' name: SFB 901 - Subprojekt A1 - _id: '2' name: SFB 901 - Project Area A publisher: Universität Paderborn status: public title: Load Balancing for Range Queries in a Dimension Invariant Peer-to-Peer Network type: mastersthesis user_id: '477' year: '2015' ... --- _id: '241' 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. author: - first_name: Christian full_name: Scheideler, Christian id: '20792' last_name: Scheideler - first_name: Alexander full_name: Setzer, Alexander id: '11108' last_name: Setzer - first_name: Thim Frederik full_name: Strothmann, Thim Frederik id: '11319' last_name: Strothmann citation: ama: 'Scheideler C, Setzer A, Strothmann TF. Towards Establishing Monotonic Searchability in Self-Stabilizing Data Structures. In: Proceedings of the 19th International Conference on Principles of Distributed Systems (OPODIS). Leibniz International Proceedings in Informatics (LIPIcs). ; 2015. doi:10.4230/LIPIcs.OPODIS.2015.24' apa: Scheideler, C., Setzer, A., & Strothmann, T. F. (2015). Towards Establishing Monotonic Searchability in Self-Stabilizing Data Structures. In Proceedings of the 19th International Conference on Principles of Distributed Systems (OPODIS). https://doi.org/10.4230/LIPIcs.OPODIS.2015.24 bibtex: '@inproceedings{Scheideler_Setzer_Strothmann_2015, series={Leibniz International Proceedings in Informatics (LIPIcs)}, title={Towards Establishing Monotonic Searchability in Self-Stabilizing Data Structures}, DOI={10.4230/LIPIcs.OPODIS.2015.24}, 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)} }' chicago: Scheideler, Christian, Alexander Setzer, and Thim Frederik Strothmann. “Towards Establishing Monotonic Searchability in Self-Stabilizing Data Structures.” In Proceedings of the 19th International Conference on Principles of Distributed Systems (OPODIS). Leibniz International Proceedings in Informatics (LIPIcs), 2015. https://doi.org/10.4230/LIPIcs.OPODIS.2015.24. ieee: C. Scheideler, A. Setzer, and T. F. Strothmann, “Towards Establishing Monotonic Searchability in Self-Stabilizing Data Structures,” in Proceedings of the 19th International Conference on Principles of Distributed Systems (OPODIS), 2015. mla: Scheideler, Christian, et al. “Towards Establishing Monotonic Searchability in Self-Stabilizing Data Structures.” Proceedings of the 19th International Conference on Principles of Distributed Systems (OPODIS), 2015, doi:10.4230/LIPIcs.OPODIS.2015.24. short: 'C. Scheideler, A. Setzer, T.F. Strothmann, in: Proceedings of the 19th International Conference on Principles of Distributed Systems (OPODIS), 2015.' date_created: 2017-10-17T12:41:39Z date_updated: 2022-01-06T06:56:07Z ddc: - '040' department: - _id: '79' doi: 10.4230/LIPIcs.OPODIS.2015.24 file: - access_level: closed content_type: application/pdf creator: florida date_created: 2018-03-21T10:28:21Z date_updated: 2018-03-21T10:28:21Z file_id: '1497' file_name: 241-ScheidelerSetzerStrothmann2015.pdf file_size: 692363 relation: main_file success: 1 file_date_updated: 2018-03-21T10:28:21Z has_accepted_license: '1' language: - iso: eng project: - _id: '1' name: SFB 901 - _id: '5' name: SFB 901 - Subprojekt A1 - _id: '2' name: SFB 901 - Project Area A publication: Proceedings of the 19th International Conference on Principles of Distributed Systems (OPODIS) series_title: Leibniz International Proceedings in Informatics (LIPIcs) status: public title: Towards Establishing Monotonic Searchability in Self-Stabilizing Data Structures type: conference user_id: '477' year: '2015' ... --- _id: '242' 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.' author: - first_name: Andreas full_name: Koutsopoulos, Andreas last_name: Koutsopoulos - first_name: Christian full_name: Scheideler, Christian id: '20792' last_name: Scheideler - first_name: Thim Frederik full_name: Strothmann, Thim Frederik id: '11319' last_name: Strothmann citation: ama: 'Koutsopoulos A, Scheideler C, Strothmann TF. Towards a Universal Approach for the Finite Departure Problem in Overlay Networks. In: Proceedings of the 17th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS). Lecture Notes in Computer Science. ; 2015:201-216. doi:10.1007/978-3-319-21741-3_14' apa: Koutsopoulos, A., Scheideler, C., & Strothmann, T. F. (2015). Towards a Universal Approach for the Finite Departure Problem in Overlay Networks. In Proceedings of the 17th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS) (pp. 201–216). https://doi.org/10.1007/978-3-319-21741-3_14 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={10.1007/978-3-319-21741-3_14}, 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} }' chicago: Koutsopoulos, Andreas, Christian Scheideler, and Thim Frederik Strothmann. “Towards a Universal Approach for the Finite Departure Problem in Overlay Networks.” In Proceedings of the 17th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), 201–16. Lecture Notes in Computer Science, 2015. https://doi.org/10.1007/978-3-319-21741-3_14. ieee: A. Koutsopoulos, C. Scheideler, and T. F. Strothmann, “Towards a Universal Approach for the Finite Departure Problem in Overlay Networks,” 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.” Proceedings of the 17th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), 2015, pp. 201–16, doi:10.1007/978-3-319-21741-3_14. 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.' date_created: 2017-10-17T12:41:39Z date_updated: 2022-01-06T06:56:10Z ddc: - '040' department: - _id: '79' doi: 10.1007/978-3-319-21741-3_14 file: - access_level: closed content_type: application/pdf creator: florida date_created: 2018-03-21T09:59:32Z date_updated: 2018-03-21T09:59:32Z file_id: '1496' file_name: 242-KSS-SSS2015.pdf file_size: 532792 relation: main_file success: 1 file_date_updated: 2018-03-21T09:59:32Z has_accepted_license: '1' language: - iso: eng page: 201-216 project: - _id: '1' name: SFB 901 - _id: '5' name: SFB 901 - Subprojekt A1 - _id: '2' name: SFB 901 - Project Area A publication: Proceedings of the 17th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS) series_title: Lecture Notes in Computer Science status: public title: Towards a Universal Approach for the Finite Departure Problem in Overlay Networks type: conference user_id: '477' year: '2015' ... --- _id: '243' abstract: - lang: eng 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. author: - first_name: Thim Frederik full_name: Strothmann, Thim Frederik id: '11319' last_name: Strothmann citation: ama: 'Strothmann TF. The impact of communication patterns on distributed locally self-adjusting binary search trees. In: Proceedings of the 9th International Workshop on Algorithms and Computation (WALCOM). LNCS. ; 2015:175--186. doi:10.1007/978-3-319-15612-5_16' apa: Strothmann, T. F. (2015). The impact of communication patterns on distributed locally self-adjusting binary search trees. In Proceedings of the 9th International Workshop on Algorithms and Computation (WALCOM) (pp. 175--186). https://doi.org/10.1007/978-3-319-15612-5_16 bibtex: '@inproceedings{Strothmann_2015, series={LNCS}, title={The impact of communication patterns on distributed locally self-adjusting binary search trees}, DOI={10.1007/978-3-319-15612-5_16}, booktitle={Proceedings of the 9th International Workshop on Algorithms and Computation (WALCOM)}, author={Strothmann, Thim Frederik}, year={2015}, pages={175--186}, collection={LNCS} }' chicago: Strothmann, Thim Frederik. “The Impact of Communication Patterns on Distributed Locally Self-Adjusting Binary Search Trees.” In Proceedings of the 9th International Workshop on Algorithms and Computation (WALCOM), 175--186. LNCS, 2015. https://doi.org/10.1007/978-3-319-15612-5_16. ieee: T. F. Strothmann, “The impact of communication patterns on distributed locally self-adjusting binary search trees,” in Proceedings of the 9th International Workshop on Algorithms and Computation (WALCOM), 2015, pp. 175--186. mla: Strothmann, Thim Frederik. “The Impact of Communication Patterns on Distributed Locally Self-Adjusting Binary Search Trees.” Proceedings of the 9th International Workshop on Algorithms and Computation (WALCOM), 2015, pp. 175--186, doi:10.1007/978-3-319-15612-5_16. short: 'T.F. Strothmann, in: Proceedings of the 9th International Workshop on Algorithms and Computation (WALCOM), 2015, pp. 175--186.' date_created: 2017-10-17T12:41:39Z date_updated: 2022-01-06T06:56:17Z ddc: - '040' department: - _id: '79' doi: 10.1007/978-3-319-15612-5_16 file: - access_level: closed content_type: application/pdf creator: florida date_created: 2018-03-21T09:59:00Z date_updated: 2018-03-21T09:59:00Z file_id: '1495' file_name: 243-Strothmann-Walcom2015.pdf file_size: 1003113 relation: main_file success: 1 file_date_updated: 2018-03-21T09:59:00Z has_accepted_license: '1' language: - iso: eng page: 175--186 project: - _id: '1' name: SFB 901 - _id: '5' name: SFB 901 - Subprojekt A1 - _id: '2' name: SFB 901 - Project Area A publication: Proceedings of the 9th International Workshop on Algorithms and Computation (WALCOM) series_title: LNCS status: public title: The impact of communication patterns on distributed locally self-adjusting binary search trees type: conference user_id: '477' year: '2015' ... --- _id: '266' 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". ' author: - first_name: Christine full_name: Markarian, Christine id: '37612' last_name: Markarian - first_name: Friedhelm full_name: Meyer auf der Heide, Friedhelm id: '15523' last_name: Meyer auf der Heide citation: ama: 'Markarian C, Meyer auf der Heide F. Online Resource Leasing. In: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC). ; 2015:343-344. doi:10.1145/2767386.2767454' apa: Markarian, C., & Meyer auf der Heide, F. (2015). Online Resource Leasing. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC) (pp. 343–344). https://doi.org/10.1145/2767386.2767454 bibtex: '@inproceedings{Markarian_Meyer auf der Heide_2015, title={Online Resource Leasing}, DOI={10.1145/2767386.2767454}, 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} }' chicago: Markarian, Christine, and Friedhelm Meyer auf der Heide. “Online Resource Leasing.” In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC), 343–44, 2015. https://doi.org/10.1145/2767386.2767454. ieee: C. Markarian and F. Meyer auf der Heide, “Online Resource Leasing,” in Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC), 2015, pp. 343–344. mla: Markarian, Christine, and Friedhelm Meyer auf der Heide. “Online Resource Leasing.” Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC), 2015, pp. 343–44, doi:10.1145/2767386.2767454. 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.' date_created: 2017-10-17T12:41:44Z date_updated: 2022-01-06T06:57:22Z ddc: - '040' department: - _id: '63' doi: 10.1145/2767386.2767454 file: - access_level: closed content_type: application/pdf creator: florida date_created: 2018-03-21T09:33:11Z date_updated: 2018-03-21T09:33:11Z file_id: '1478' file_name: 266-p343-markarian.pdf file_size: 679580 relation: main_file success: 1 file_date_updated: 2018-03-21T09:33:11Z has_accepted_license: '1' page: 343-344 project: - _id: '1' name: SFB 901 - _id: '5' name: SFB 901 - Subprojekt A1 - _id: '16' name: SFB 901 - Subprojekt C4 - _id: '2' name: SFB 901 - Project Area A - _id: '4' name: SFB 901 - Project Area C publication: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC) status: public title: Online Resource Leasing type: conference user_id: '15504' year: '2015' ... --- _id: '327' abstract: - lang: eng text: We consider the problem of resource discovery in distributed systems. In particular we give an algorithm, such that each node in a network discovers the 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. author: - first_name: Sebastian full_name: Kniesburges, Sebastian last_name: Kniesburges - first_name: Andreas full_name: Koutsopoulos, Andreas last_name: Koutsopoulos - first_name: Christian full_name: Scheideler, Christian id: '20792' last_name: Scheideler citation: ama: Kniesburges S, Koutsopoulos A, Scheideler C. A deterministic worst-case message complexity optimal solution for resource discovery. Theoretical Computer Science. 2015:67-79. doi:10.1016/j.tcs.2014.11.027 apa: Kniesburges, S., Koutsopoulos, A., & Scheideler, C. (2015). A deterministic worst-case message complexity optimal solution for resource discovery. Theoretical Computer Science, 67–79. https://doi.org/10.1016/j.tcs.2014.11.027 bibtex: '@article{Kniesburges_Koutsopoulos_Scheideler_2015, title={A deterministic worst-case message complexity optimal solution for resource discovery}, DOI={10.1016/j.tcs.2014.11.027}, journal={Theoretical Computer Science}, publisher={Elsevier}, author={Kniesburges, Sebastian and Koutsopoulos, Andreas and Scheideler, Christian}, year={2015}, pages={67–79} }' chicago: Kniesburges, Sebastian, Andreas Koutsopoulos, and Christian Scheideler. “A Deterministic Worst-Case Message Complexity Optimal Solution for Resource Discovery.” Theoretical Computer Science, 2015, 67–79. https://doi.org/10.1016/j.tcs.2014.11.027. ieee: S. Kniesburges, A. Koutsopoulos, and C. Scheideler, “A deterministic worst-case message complexity optimal solution for resource discovery,” Theoretical Computer Science, pp. 67–79, 2015. mla: Kniesburges, Sebastian, et al. “A Deterministic Worst-Case Message Complexity Optimal Solution for Resource Discovery.” Theoretical Computer Science, Elsevier, 2015, pp. 67–79, doi:10.1016/j.tcs.2014.11.027. short: S. Kniesburges, A. Koutsopoulos, C. Scheideler, Theoretical Computer Science (2015) 67–79. date_created: 2017-10-17T12:41:55Z date_updated: 2022-01-06T06:59:08Z ddc: - '040' department: - _id: '79' doi: 10.1016/j.tcs.2014.11.027 file: - access_level: closed content_type: application/pdf creator: florida date_created: 2018-03-20T07:38:02Z date_updated: 2018-03-20T07:38:02Z file_id: '1427' file_name: 327-KKS15-TOCS_01.pdf file_size: 398044 relation: main_file success: 1 file_date_updated: 2018-03-20T07:38:02Z has_accepted_license: '1' page: 67-79 project: - _id: '1' name: SFB 901 - _id: '5' name: SFB 901 - Subprojekt A1 - _id: '2' name: SFB 901 - Project Area A publication: Theoretical Computer Science publisher: Elsevier status: public title: A deterministic worst-case message complexity optimal solution for resource discovery type: journal_article user_id: '477' year: '2015' ... --- _id: '304' author: - first_name: Andreas full_name: Koutsopoulos, Andreas last_name: Koutsopoulos citation: ama: Koutsopoulos A. Dynamics and Efficiency in Topological Self-Stabilization. Universität Paderborn; 2015. apa: Koutsopoulos, A. (2015). Dynamics and Efficiency in Topological Self-Stabilization. Universität Paderborn. bibtex: '@book{Koutsopoulos_2015, title={Dynamics and Efficiency in Topological Self-Stabilization}, publisher={Universität Paderborn}, author={Koutsopoulos, Andreas}, year={2015} }' chicago: Koutsopoulos, Andreas. Dynamics and Efficiency in Topological Self-Stabilization. Universität Paderborn, 2015. ieee: A. Koutsopoulos, Dynamics and Efficiency in Topological Self-Stabilization. Universität Paderborn, 2015. mla: Koutsopoulos, Andreas. Dynamics and Efficiency in Topological Self-Stabilization. Universität Paderborn, 2015. short: A. Koutsopoulos, Dynamics and Efficiency in Topological Self-Stabilization, Universität Paderborn, 2015. date_created: 2017-10-17T12:41:51Z date_updated: 2022-01-06T06:58:53Z ddc: - '040' department: - _id: '79' file: - access_level: closed content_type: application/pdf creator: florida date_created: 2018-03-20T07:46:19Z date_updated: 2018-03-20T07:46:19Z file_id: '1441' file_name: 304-Dissertation_-_Koutsopoulos.pdf file_size: 2275834 relation: main_file success: 1 file_date_updated: 2018-03-20T07:46:19Z has_accepted_license: '1' project: - _id: '1' name: SFB 901 - _id: '5' name: SFB 901 - Subproject A1 - _id: '2' name: SFB 901 - Project Area A publisher: Universität Paderborn status: public supervisor: - first_name: Christian full_name: Scheideler, Christian id: '20792' last_name: Scheideler title: Dynamics and Efficiency in Topological Self-Stabilization type: dissertation user_id: '15504' year: '2015' ... --- _id: '305' author: - first_name: Sebastian full_name: Kniesburges, Sebastian last_name: Kniesburges citation: ama: Kniesburges S. Distributed Data Structures and the Power of Topological Self-Stabilization. Universität Paderborn; 2015. apa: Kniesburges, S. (2015). Distributed Data Structures and the Power of topological Self-Stabilization. Universität Paderborn. bibtex: '@book{Kniesburges_2015, title={Distributed Data Structures and the Power of topological Self-Stabilization}, publisher={Universität Paderborn}, author={Kniesburges, Sebastian}, year={2015} }' chicago: Kniesburges, Sebastian. Distributed Data Structures and the Power of Topological Self-Stabilization. Universität Paderborn, 2015. ieee: S. Kniesburges, Distributed Data Structures and the Power of topological Self-Stabilization. Universität Paderborn, 2015. mla: Kniesburges, Sebastian. Distributed Data Structures and the Power of Topological Self-Stabilization. Universität Paderborn, 2015. short: S. Kniesburges, Distributed Data Structures and the Power of Topological Self-Stabilization, Universität Paderborn, 2015. date_created: 2017-10-17T12:41:51Z date_updated: 2022-01-06T06:58:54Z ddc: - '040' department: - _id: '79' file: - access_level: closed content_type: application/pdf creator: florida date_created: 2018-03-13T09:14:43Z date_updated: 2018-03-13T09:14:43Z file_id: '1206' file_name: 305-Dissertation_-_Kniesburges.pdf file_size: 1709094 relation: main_file success: 1 file_date_updated: 2018-03-13T09:14:43Z has_accepted_license: '1' project: - _id: '1' name: SFB 901 - _id: '2' name: SFB 901 - Project Area A - _id: '4' name: SFB 901 - Project Area C - _id: '5' name: SFB 901 - Subproject A1 - _id: '13' name: SFB 901 - Subproject C1 publisher: Universität Paderborn status: public supervisor: - first_name: Christian full_name: Scheideler, Christian id: '20792' last_name: Scheideler title: Distributed Data Structures and the Power of topological Self-Stabilization type: dissertation user_id: '15504' year: '2015' ...