--- _id: '646' abstract: - lang: eng text: This paper presents a dynamic overlay network based on the De Bruijn graph which we call Linearized De Bruijn (LDB) network. The LDB network has the advantage that it has a guaranteed constant node degree and that the routing between any two nodes takes at most O(log n) hops with high probability. Also, we show that there is a simple local-control algorithm that can recover the LDB network from any network topology that is weakly connected. author: - first_name: Andrea W. full_name: Richa, Andrea W. last_name: Richa - first_name: Christian full_name: Scheideler, Christian id: '20792' last_name: Scheideler citation: ama: 'Richa AW, Scheideler C. Self-Stabilizing DeBruijn Networks. In: Proceedings of the 13th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS). LNCS. ; 2011:416-430. doi:10.1007/978-3-642-24550-3_31' apa: Richa, A. W., & Scheideler, C. (2011). Self-Stabilizing DeBruijn Networks. In Proceedings of the 13th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS) (pp. 416–430). https://doi.org/10.1007/978-3-642-24550-3_31 bibtex: '@inproceedings{Richa_Scheideler_2011, series={LNCS}, title={Self-Stabilizing DeBruijn Networks}, DOI={10.1007/978-3-642-24550-3_31}, booktitle={Proceedings of the 13th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)}, author={Richa, Andrea W. and Scheideler, Christian}, year={2011}, pages={416–430}, collection={LNCS} }' chicago: Richa, Andrea W., and Christian Scheideler. “Self-Stabilizing DeBruijn Networks.” In Proceedings of the 13th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), 416–30. LNCS, 2011. https://doi.org/10.1007/978-3-642-24550-3_31. ieee: A. W. Richa and C. Scheideler, “Self-Stabilizing DeBruijn Networks,” in Proceedings of the 13th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), 2011, pp. 416–430. mla: Richa, Andrea W., and Christian Scheideler. “Self-Stabilizing DeBruijn Networks.” Proceedings of the 13th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), 2011, pp. 416–30, doi:10.1007/978-3-642-24550-3_31. short: 'A.W. Richa, C. Scheideler, in: Proceedings of the 13th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), 2011, pp. 416–430.' date_created: 2017-10-17T12:42:58Z date_updated: 2022-01-06T07:03:06Z ddc: - '040' department: - _id: '79' doi: 10.1007/978-3-642-24550-3_31 file: - access_level: closed content_type: application/pdf creator: florida date_created: 2018-03-14T13:57:26Z date_updated: 2018-03-14T13:57:26Z file_id: '1227' file_name: 646-SSS2011-Scheideler_02.pdf file_size: 339664 relation: main_file success: 1 file_date_updated: 2018-03-14T13:57:26Z has_accepted_license: '1' page: 416-430 project: - _id: '1' name: SFB 901 - _id: '13' name: SFB 901 - Subprojekt C1 - _id: '4' name: SFB 901 - Project Area C publication: Proceedings of the 13th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS) series_title: LNCS status: public title: Self-Stabilizing DeBruijn Networks type: conference user_id: '15504' year: '2011' ... --- _id: '662' abstract: - lang: eng text: We present Corona, a deterministic self-stabilizing algorithm for skip list construction in structured overlay networks. Corona operates in the low-atomicity message-passing asynchronous system model. Corona requires constant process memory space for its operation and, therefore, scales well. We prove the general necessary conditions limiting the initial states from which a self-stabilizing structured overlay network in message-passing system can be constructed. The conditions require that initial state information has to form a weakly connected graph and it should only contain identiers that are present in the system. We formally describe Corona and rigorously prove that it stabilizes from an arbitrary initial state subject to the necessary conditions. We extend Corona to construct a skip graph. author: - first_name: Mikhail full_name: Nesterenko, Mikhail last_name: Nesterenko - first_name: Rizal full_name: Mohd, Rizal last_name: Mohd - first_name: Christian full_name: Scheideler, Christian id: '20792' last_name: Scheideler citation: ama: 'Nesterenko M, Mohd R, Scheideler C. Corona: A Stabilizing Deterministic Message-Passing Skip List. In: Proceedings of the 13th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS). LNCS. ; 2011:356--370. doi:10.1007/978-3-642-24550-3_27' apa: 'Nesterenko, M., Mohd, R., & Scheideler, C. (2011). Corona: A Stabilizing Deterministic Message-Passing Skip List. In Proceedings of the 13th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS) (pp. 356--370). https://doi.org/10.1007/978-3-642-24550-3_27' bibtex: '@inproceedings{Nesterenko_Mohd_Scheideler_2011, series={LNCS}, title={Corona: A Stabilizing Deterministic Message-Passing Skip List}, DOI={10.1007/978-3-642-24550-3_27}, booktitle={Proceedings of the 13th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)}, author={Nesterenko, Mikhail and Mohd, Rizal and Scheideler, Christian}, year={2011}, pages={356--370}, collection={LNCS} }' chicago: 'Nesterenko, Mikhail, Rizal Mohd, and Christian Scheideler. “Corona: A Stabilizing Deterministic Message-Passing Skip List.” In Proceedings of the 13th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), 356--370. LNCS, 2011. https://doi.org/10.1007/978-3-642-24550-3_27.' ieee: 'M. Nesterenko, R. Mohd, and C. Scheideler, “Corona: A Stabilizing Deterministic Message-Passing Skip List,” in Proceedings of the 13th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), 2011, pp. 356--370.' mla: 'Nesterenko, Mikhail, et al. “Corona: A Stabilizing Deterministic Message-Passing Skip List.” Proceedings of the 13th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), 2011, pp. 356--370, doi:10.1007/978-3-642-24550-3_27.' short: 'M. Nesterenko, R. Mohd, C. Scheideler, in: Proceedings of the 13th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), 2011, pp. 356--370.' date_created: 2017-10-17T12:43:01Z date_updated: 2022-01-06T07:03:13Z ddc: - '040' department: - _id: '79' doi: 10.1007/978-3-642-24550-3_27 file: - access_level: closed content_type: application/pdf creator: florida date_created: 2018-03-14T13:46:48Z date_updated: 2018-03-14T13:46:48Z file_id: '1217' file_name: 662-SSS2011-Corona-Scheideler.pdf file_size: 305543 relation: main_file success: 1 file_date_updated: 2018-03-14T13:46:48Z has_accepted_license: '1' page: 356--370 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 13th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS) series_title: LNCS status: public title: 'Corona: A Stabilizing Deterministic Message-Passing Skip List' type: conference user_id: '15504' year: '2011' ... --- _id: '1882' author: - first_name: Shlomi full_name: Dolev, Shlomi last_name: Dolev - first_name: Christian full_name: Scheideler, Christian id: '20792' last_name: Scheideler citation: ama: Dolev S, Scheideler C. Editorial for Algorithmic Aspects of Wireless Sensor Networks. Theor Comput Sci. 2012:1. doi:10.1016/j.tcs.2012.07.012 apa: Dolev, S., & Scheideler, C. (2012). Editorial for Algorithmic Aspects of Wireless Sensor Networks. Theor. Comput. Sci., 1. https://doi.org/10.1016/j.tcs.2012.07.012 bibtex: '@article{Dolev_Scheideler_2012, title={Editorial for Algorithmic Aspects of Wireless Sensor Networks}, DOI={10.1016/j.tcs.2012.07.012}, journal={Theor. Comput. Sci.}, author={Dolev, Shlomi and Scheideler, Christian}, year={2012}, pages={1} }' chicago: Dolev, Shlomi, and Christian Scheideler. “Editorial for Algorithmic Aspects of Wireless Sensor Networks.” Theor. Comput. Sci., 2012, 1. https://doi.org/10.1016/j.tcs.2012.07.012. ieee: S. Dolev and C. Scheideler, “Editorial for Algorithmic Aspects of Wireless Sensor Networks,” Theor. Comput. Sci., p. 1, 2012. mla: Dolev, Shlomi, and Christian Scheideler. “Editorial for Algorithmic Aspects of Wireless Sensor Networks.” Theor. Comput. Sci., 2012, p. 1, doi:10.1016/j.tcs.2012.07.012. short: S. Dolev, C. Scheideler, Theor. Comput. Sci. (2012) 1. date_created: 2018-03-28T06:44:05Z date_updated: 2022-01-06T06:53:52Z department: - _id: '79' doi: 10.1016/j.tcs.2012.07.012 page: '1' publication: Theor. Comput. Sci. status: public title: Editorial for Algorithmic Aspects of Wireless Sensor Networks type: journal_article user_id: '15504' year: '2012' ... --- _id: '1884' author: - first_name: Burkhard full_name: Monien, Burkhard last_name: Monien - first_name: Christian full_name: Scheideler, Christian id: '20792' last_name: Scheideler citation: ama: 'Monien B, Scheideler C. Selfish Distributed Optimization. In: Euro-Par 2012 Parallel Processing - 18th International Conference, Euro-Par 2012, Rhodes Island, Greece, August 27-31, 2012. Proceedings. Vol 7484. Lecture Notes in Computer Science. Springer; 2012:1--2. doi:10.1007/978-3-642-32820-6_1' apa: Monien, B., & Scheideler, C. (2012). Selfish Distributed Optimization. In Euro-Par 2012 Parallel Processing - 18th International Conference, Euro-Par 2012, Rhodes Island, Greece, August 27-31, 2012. Proceedings (Vol. 7484, pp. 1--2). Springer. https://doi.org/10.1007/978-3-642-32820-6_1 bibtex: '@inproceedings{Monien_Scheideler_2012, series={Lecture Notes in Computer Science}, title={Selfish Distributed Optimization}, volume={7484}, DOI={10.1007/978-3-642-32820-6_1}, booktitle={Euro-Par 2012 Parallel Processing - 18th International Conference, Euro-Par 2012, Rhodes Island, Greece, August 27-31, 2012. Proceedings}, publisher={Springer}, author={Monien, Burkhard and Scheideler, Christian}, year={2012}, pages={1--2}, collection={Lecture Notes in Computer Science} }' chicago: Monien, Burkhard, and Christian Scheideler. “Selfish Distributed Optimization.” In Euro-Par 2012 Parallel Processing - 18th International Conference, Euro-Par 2012, Rhodes Island, Greece, August 27-31, 2012. Proceedings, 7484:1--2. Lecture Notes in Computer Science. Springer, 2012. https://doi.org/10.1007/978-3-642-32820-6_1. ieee: B. Monien and C. Scheideler, “Selfish Distributed Optimization,” in Euro-Par 2012 Parallel Processing - 18th International Conference, Euro-Par 2012, Rhodes Island, Greece, August 27-31, 2012. Proceedings, 2012, vol. 7484, pp. 1--2. mla: Monien, Burkhard, and Christian Scheideler. “Selfish Distributed Optimization.” Euro-Par 2012 Parallel Processing - 18th International Conference, Euro-Par 2012, Rhodes Island, Greece, August 27-31, 2012. Proceedings, vol. 7484, Springer, 2012, pp. 1--2, doi:10.1007/978-3-642-32820-6_1. short: 'B. Monien, C. Scheideler, in: Euro-Par 2012 Parallel Processing - 18th International Conference, Euro-Par 2012, Rhodes Island, Greece, August 27-31, 2012. Proceedings, Springer, 2012, pp. 1--2.' date_created: 2018-03-28T06:44:57Z date_updated: 2022-01-06T06:53:52Z department: - _id: '79' doi: 10.1007/978-3-642-32820-6_1 intvolume: ' 7484' page: 1--2 publication: Euro-Par 2012 Parallel Processing - 18th International Conference, Euro-Par 2012, Rhodes Island, Greece, August 27-31, 2012. Proceedings publication_identifier: isbn: - 978-3-642-32819-0 publisher: Springer series_title: Lecture Notes in Computer Science status: public title: Selfish Distributed Optimization type: conference user_id: '15504' volume: 7484 year: '2012' ... --- _id: '570' abstract: - lang: eng text: 'This article studies the construction of self-stabilizing topologies for distributed systems. While recent research has focused on chain topologies where nodes need to be linearized with respect to their identiers, we explore a natural and relevant 2-dimensional generalization. In particular, we present a local self-stabilizing algorithm DStab which is based on the concept of \local Delaunay graphs" and which forwards temporary edges in greedy fashion reminiscent of compass routing. DStab constructs a Delaunay graph from any initial connected topology and in a distributed manner in time O(n3) in the worst-case; if the initial network contains the Delaunay graph, the convergence time is only O(n) rounds. DStab also ensures that individual node joins and leaves aect a small part of the network only. Such self-stabilizing Delaunay networks have interesting applications and our construction gives insights into the necessary geometric reasoning that is required for higherdimensional linearization problems.Keywords: Distributed Algorithms, Topology Control, Social Networks' author: - first_name: Riko full_name: Jacob, Riko last_name: Jacob - first_name: Stephan full_name: Ritscher, Stephan last_name: Ritscher - first_name: Christian full_name: Scheideler, Christian id: '20792' last_name: Scheideler - first_name: Stefan full_name: Schmid, Stefan last_name: Schmid citation: ama: 'Jacob R, Ritscher S, Scheideler C, Schmid S. Towards higher-dimensional topological self-stabilization: A distributed algorithm for Delaunay graphs. Theoretical Computer Science. 2012:137-148. doi:10.1016/j.tcs.2012.07.029' apa: 'Jacob, R., Ritscher, S., Scheideler, C., & Schmid, S. (2012). Towards higher-dimensional topological self-stabilization: A distributed algorithm for Delaunay graphs. Theoretical Computer Science, 137–148. https://doi.org/10.1016/j.tcs.2012.07.029' bibtex: '@article{Jacob_Ritscher_Scheideler_Schmid_2012, title={Towards higher-dimensional topological self-stabilization: A distributed algorithm for Delaunay graphs}, DOI={10.1016/j.tcs.2012.07.029}, journal={Theoretical Computer Science}, publisher={Elsevier}, author={Jacob, Riko and Ritscher, Stephan and Scheideler, Christian and Schmid, Stefan}, year={2012}, pages={137–148} }' chicago: 'Jacob, Riko, Stephan Ritscher, Christian Scheideler, and Stefan Schmid. “Towards Higher-Dimensional Topological Self-Stabilization: A Distributed Algorithm for Delaunay Graphs.” Theoretical Computer Science, 2012, 137–48. https://doi.org/10.1016/j.tcs.2012.07.029.' ieee: 'R. Jacob, S. Ritscher, C. Scheideler, and S. Schmid, “Towards higher-dimensional topological self-stabilization: A distributed algorithm for Delaunay graphs,” Theoretical Computer Science, pp. 137–148, 2012.' mla: 'Jacob, Riko, et al. “Towards Higher-Dimensional Topological Self-Stabilization: A Distributed Algorithm for Delaunay Graphs.” Theoretical Computer Science, Elsevier, 2012, pp. 137–48, doi:10.1016/j.tcs.2012.07.029.' short: R. Jacob, S. Ritscher, C. Scheideler, S. Schmid, Theoretical Computer Science (2012) 137–148. date_created: 2017-10-17T12:42:43Z date_updated: 2022-01-06T07:02:36Z ddc: - '040' department: - _id: '79' doi: 10.1016/j.tcs.2012.07.029 file: - access_level: closed content_type: application/pdf creator: florida date_created: 2018-03-15T10:16:20Z date_updated: 2018-03-15T10:16:20Z file_id: '1272' file_name: 570-Delaunay-Journal.pdf file_size: 250051 relation: main_file success: 1 file_date_updated: 2018-03-15T10:16:20Z has_accepted_license: '1' page: 137-148 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: 'Towards higher-dimensional topological self-stabilization: A distributed algorithm for Delaunay graphs' type: journal_article user_id: '477' year: '2012' ... --- _id: '574' abstract: - lang: eng text: 'We present Tiara — a self-stabilizing peer-to-peer network maintenance algorithm. Tiara is truly deterministic which allows it to achieve exact performance bounds. Tiara allows logarithmic searches and topology updates. It is based on a novel sparse 0-1 skip list. We then describe its extension to a ringed structure and to a skip-graph.Key words: Peer-to-peer networks, overlay networks, self-stabilization.' author: - first_name: Thomas full_name: Clouser, Thomas last_name: Clouser - first_name: Mikhail full_name: Nesterenko, Mikhail last_name: Nesterenko - first_name: Christian full_name: Scheideler, Christian id: '20792' last_name: Scheideler citation: ama: 'Clouser T, Nesterenko M, Scheideler C. Tiara: A self-stabilizing deterministic skip list and skip graph. Theoretical Computer Science. 2012:18-35. doi:10.1016/j.tcs.2011.12.079' apa: 'Clouser, T., Nesterenko, M., & Scheideler, C. (2012). Tiara: A self-stabilizing deterministic skip list and skip graph. Theoretical Computer Science, 18–35. https://doi.org/10.1016/j.tcs.2011.12.079' bibtex: '@article{Clouser_Nesterenko_Scheideler_2012, title={Tiara: A self-stabilizing deterministic skip list and skip graph}, DOI={10.1016/j.tcs.2011.12.079}, journal={Theoretical Computer Science}, publisher={Elsevier}, author={Clouser, Thomas and Nesterenko, Mikhail and Scheideler, Christian}, year={2012}, pages={18–35} }' chicago: 'Clouser, Thomas, Mikhail Nesterenko, and Christian Scheideler. “Tiara: A Self-Stabilizing Deterministic Skip List and Skip Graph.” Theoretical Computer Science, 2012, 18–35. https://doi.org/10.1016/j.tcs.2011.12.079.' ieee: 'T. Clouser, M. Nesterenko, and C. Scheideler, “Tiara: A self-stabilizing deterministic skip list and skip graph,” Theoretical Computer Science, pp. 18–35, 2012.' mla: 'Clouser, Thomas, et al. “Tiara: A Self-Stabilizing Deterministic Skip List and Skip Graph.” Theoretical Computer Science, Elsevier, 2012, pp. 18–35, doi:10.1016/j.tcs.2011.12.079.' short: T. Clouser, M. Nesterenko, C. Scheideler, Theoretical Computer Science (2012) 18–35. date_created: 2017-10-17T12:42:44Z date_updated: 2022-01-06T07:02:38Z ddc: - '040' department: - _id: '79' doi: 10.1016/j.tcs.2011.12.079 file: - access_level: closed content_type: application/pdf creator: florida date_created: 2018-03-15T09:09:29Z date_updated: 2018-03-15T09:09:29Z file_id: '1268' file_name: 574-tiara.pdf file_size: 315843 relation: main_file success: 1 file_date_updated: 2018-03-15T09:09:29Z has_accepted_license: '1' page: 18-35 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: 'Tiara: A self-stabilizing deterministic skip list and skip graph' type: journal_article user_id: '477' year: '2012' ... --- _id: '579' abstract: - lang: eng text: A left-to-right maximum in a sequence of n numbers s_1, …, s_n is a number that is strictly larger than all preceding numbers. In this article we present a smoothed analysis of the number of left-to-right maxima in the presence of additive random noise. We show that for every sequence of n numbers s_i ∈ [0,1] that are perturbed by uniform noise from the interval [-ε,ε], the expected number of left-to-right maxima is Θ(&sqrt;n/ε + log n) for ε>1/n. For Gaussian noise with standard deviation σ we obtain a bound of O((log3/2 n)/σ + log n).We apply our results to the analysis of the smoothed height of binary search trees and the smoothed number of comparisons in the quicksort algorithm and prove bounds of Θ(&sqrt;n/ε + log n) and Θ(n/ε+1&sqrt;n/ε + n log n), respectively, for uniform random noise from the interval [-ε,ε]. Our results can also be applied to bound the smoothed number of points on a convex hull of points in the two-dimensional plane and to smoothed motion complexity, a concept we describe in this article. We bound how often one needs to update a data structure storing the smallest axis-aligned box enclosing a set of points moving in d-dimensional space. author: - first_name: Valentina full_name: Damerow, Valentina last_name: Damerow - first_name: Bodo full_name: Manthey, Bodo last_name: Manthey - first_name: Friedhelm full_name: Meyer auf der Heide, Friedhelm id: '15523' last_name: Meyer auf der Heide - first_name: Harald full_name: Räcke, Harald last_name: Räcke - first_name: Christian full_name: Scheideler, Christian id: '20792' last_name: Scheideler - first_name: Christian full_name: Sohler, Christian last_name: Sohler - first_name: Till full_name: Tantau, Till last_name: Tantau citation: ama: Damerow V, Manthey B, Meyer auf der Heide F, et al. Smoothed analysis of left-to-right maxima with applications. Transactions on Algorithms. 2012;(3):30. doi:10.1145/2229163.2229174 apa: Damerow, V., Manthey, B., Meyer auf der Heide, F., Räcke, H., Scheideler, C., Sohler, C., & Tantau, T. (2012). Smoothed analysis of left-to-right maxima with applications. Transactions on Algorithms, (3), 30. https://doi.org/10.1145/2229163.2229174 bibtex: '@article{Damerow_Manthey_Meyer auf der Heide_Räcke_Scheideler_Sohler_Tantau_2012, title={Smoothed analysis of left-to-right maxima with applications}, DOI={10.1145/2229163.2229174}, number={3}, journal={Transactions on Algorithms}, publisher={ACM}, author={Damerow, Valentina and Manthey, Bodo and Meyer auf der Heide, Friedhelm and Räcke, Harald and Scheideler, Christian and Sohler, Christian and Tantau, Till}, year={2012}, pages={30} }' chicago: 'Damerow, Valentina, Bodo Manthey, Friedhelm Meyer auf der Heide, Harald Räcke, Christian Scheideler, Christian Sohler, and Till Tantau. “Smoothed Analysis of Left-to-Right Maxima with Applications.” Transactions on Algorithms, no. 3 (2012): 30. https://doi.org/10.1145/2229163.2229174.' ieee: V. Damerow et al., “Smoothed analysis of left-to-right maxima with applications,” Transactions on Algorithms, no. 3, p. 30, 2012. mla: Damerow, Valentina, et al. “Smoothed Analysis of Left-to-Right Maxima with Applications.” Transactions on Algorithms, no. 3, ACM, 2012, p. 30, doi:10.1145/2229163.2229174. short: V. Damerow, B. Manthey, F. Meyer auf der Heide, H. Räcke, C. Scheideler, C. Sohler, T. Tantau, Transactions on Algorithms (2012) 30. date_created: 2017-10-17T12:42:45Z date_updated: 2022-01-06T07:02:41Z ddc: - '040' department: - _id: '79' - _id: '63' doi: 10.1145/2229163.2229174 file: - access_level: closed content_type: application/pdf creator: florida date_created: 2018-03-15T09:04:58Z date_updated: 2018-03-15T09:04:58Z file_id: '1266' file_name: 579-a30-damerow.pdf file_size: 329282 relation: main_file success: 1 file_date_updated: 2018-03-15T09:04:58Z has_accepted_license: '1' issue: '3' page: '30' project: - _id: '1' name: SFB 901 - _id: '5' name: SFB 901 - Subprojekt A1 - _id: '2' name: SFB 901 - Project Area A publication: Transactions on Algorithms publisher: ACM status: public title: Smoothed analysis of left-to-right maxima with applications type: journal_article user_id: '477' year: '2012' ... --- _id: '581' abstract: - lang: eng text: 'Nanoparticles are getting more and more in the focus of the scientic community since the potential for the development of very small particles interacting with each other and completing medical and other tasks is getting bigger year by year. In this work we introduce a distributed local algorithm for arranging a set of nanoparticles on the discrete plane into specic geometric shapes, for instance a rectangle. The concept of a particle we use can be seen as a simple mobile robot with the following restrictions: it can only view the state of robots it is physically connected to, is anonymous, has only a constant size memory, can only move by using other particles as an anchor point on which it pulls itself alongside, and it operates in Look-Compute-Move cycles. The main result of this work is the presentation of a random distributed local algorithm which transforms any given connected set of particles into a particular geometric shape. As an example we provide a version of this algorithm for forming a rectangle with an arbitrary predened aspect ratio. To the best of our knowledge this is the rst work that considers arrangement problems for these types of robots.' author: - first_name: Maximilian full_name: Drees, Maximilian last_name: Drees - first_name: Martina full_name: 'Hüllmann (married name: Eikel), Martina' last_name: 'Hüllmann (married name: Eikel)' - first_name: Andreas full_name: Koutsopoulos, Andreas last_name: Koutsopoulos - first_name: Christian full_name: Scheideler, Christian id: '20792' last_name: Scheideler citation: ama: 'Drees M, Hüllmann (married name: Eikel) M, Koutsopoulos A, Scheideler C. Self-Organizing Particle Systems. In: Proceedings of the 26th IEEE International Parallel and Distributed Processing Symposium (IPDPS). ; 2012:1272-1283. doi:10.1109/IPDPS.2012.116' apa: 'Drees, M., Hüllmann (married name: Eikel), M., Koutsopoulos, A., & Scheideler, C. (2012). Self-Organizing Particle Systems. In Proceedings of the 26th IEEE International Parallel and Distributed Processing Symposium (IPDPS) (pp. 1272–1283). https://doi.org/10.1109/IPDPS.2012.116' bibtex: '@inproceedings{Drees_Hüllmann (married name: Eikel)_Koutsopoulos_Scheideler_2012, title={Self-Organizing Particle Systems}, DOI={10.1109/IPDPS.2012.116}, booktitle={Proceedings of the 26th IEEE International Parallel and Distributed Processing Symposium (IPDPS)}, author={Drees, Maximilian and Hüllmann (married name: Eikel), Martina and Koutsopoulos, Andreas and Scheideler, Christian}, year={2012}, pages={1272–1283} }' chicago: 'Drees, Maximilian, Martina Hüllmann (married name: Eikel), Andreas Koutsopoulos, and Christian Scheideler. “Self-Organizing Particle Systems.” In Proceedings of the 26th IEEE International Parallel and Distributed Processing Symposium (IPDPS), 1272–83, 2012. https://doi.org/10.1109/IPDPS.2012.116.' ieee: 'M. Drees, M. Hüllmann (married name: Eikel), A. Koutsopoulos, and C. Scheideler, “Self-Organizing Particle Systems,” in Proceedings of the 26th IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2012, pp. 1272–1283.' mla: Drees, Maximilian, et al. “Self-Organizing Particle Systems.” Proceedings of the 26th IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2012, pp. 1272–83, doi:10.1109/IPDPS.2012.116. short: 'M. Drees, M. Hüllmann (married name: Eikel), A. Koutsopoulos, C. Scheideler, in: Proceedings of the 26th IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2012, pp. 1272–1283.' date_created: 2017-10-17T12:42:45Z date_updated: 2022-01-06T07:02:42Z ddc: - '040' department: - _id: '79' - _id: '63' doi: 10.1109/IPDPS.2012.116 file: - access_level: closed content_type: application/pdf creator: florida date_created: 2018-03-15T08:39:33Z date_updated: 2018-03-15T08:39:33Z file_id: '1263' file_name: 581-IPDPS2012-Scheideler_Huellmann.pdf file_size: 373131 relation: main_file success: 1 file_date_updated: 2018-03-15T08:39:33Z has_accepted_license: '1' language: - iso: eng page: 1272-1283 project: - _id: '1' name: SFB 901 - _id: '13' name: SFB 901 - Subprojekt C1 - _id: '4' name: SFB 901 - Project Area C publication: Proceedings of the 26th IEEE International Parallel and Distributed Processing Symposium (IPDPS) status: public title: Self-Organizing Particle Systems type: conference user_id: '14955' year: '2012' ... --- _id: '623' abstract: - lang: eng text: 'This paper initiates the formal study of a fundamental problem: How to efficiently allocate a shared communication medium among a set of K co-existing networks in the presence of arbitrary external interference? While most literature on medium access focuses on how to share a medium among nodes, these approaches are often either not directly applicable to co-existing networks as they would violate the independence requirement, or they yield a low throughput if applied to multiple networks. We present the randomized medium access (MAC) protocol COMAC which guarantees that a given communication channel is shared fairly among competing and independent networks, and that the available bandwidth is used efficiently. These performance guarantees hold in the presence of arbitrary external interference or even under adversarial jamming. Concretely, we show that the co-existing networks can use a Ω(ε2 min{ε, 1/poly(K)})-fraction of the non-jammed time steps for successful message transmissions, where ε is the (arbitrarily distributed) fraction of time which is not jammed.' author: - first_name: Andrea W. full_name: Richa, Andrea W. last_name: Richa - first_name: Christian full_name: Scheideler, Christian id: '20792' last_name: Scheideler - first_name: Stefan full_name: Schmid, Stefan last_name: Schmid - first_name: 'Jin ' full_name: 'Zhang, Jin ' last_name: Zhang citation: ama: 'Richa AW, Scheideler C, Schmid S, Zhang J. Competitive and fair throughput for co-existing networks under adversarial interference. In: Proceedings of the 31st Annual ACM SIGACT-SIGOPS Symposium on Principles and Distributed Computing (PODC). ; 2012:291-300. doi:10.1145/2332432.2332488' apa: Richa, A. W., Scheideler, C., Schmid, S., & Zhang, J. (2012). Competitive and fair throughput for co-existing networks under adversarial interference. In Proceedings of the 31st Annual ACM SIGACT-SIGOPS Symposium on Principles and Distributed Computing (PODC) (pp. 291–300). https://doi.org/10.1145/2332432.2332488 bibtex: '@inproceedings{Richa_Scheideler_Schmid_Zhang_2012, title={Competitive and fair throughput for co-existing networks under adversarial interference}, DOI={10.1145/2332432.2332488}, booktitle={Proceedings of the 31st Annual ACM SIGACT-SIGOPS Symposium on Principles and Distributed Computing (PODC)}, author={Richa, Andrea W. and Scheideler, Christian and Schmid, Stefan and Zhang, Jin }, year={2012}, pages={291–300} }' chicago: Richa, Andrea W., Christian Scheideler, Stefan Schmid, and Jin Zhang. “Competitive and Fair Throughput for Co-Existing Networks under Adversarial Interference.” In Proceedings of the 31st Annual ACM SIGACT-SIGOPS Symposium on Principles and Distributed Computing (PODC), 291–300, 2012. https://doi.org/10.1145/2332432.2332488. ieee: A. W. Richa, C. Scheideler, S. Schmid, and J. Zhang, “Competitive and fair throughput for co-existing networks under adversarial interference,” in Proceedings of the 31st Annual ACM SIGACT-SIGOPS Symposium on Principles and Distributed Computing (PODC), 2012, pp. 291–300. mla: Richa, Andrea W., et al. “Competitive and Fair Throughput for Co-Existing Networks under Adversarial Interference.” Proceedings of the 31st Annual ACM SIGACT-SIGOPS Symposium on Principles and Distributed Computing (PODC), 2012, pp. 291–300, doi:10.1145/2332432.2332488. short: 'A.W. Richa, C. Scheideler, S. Schmid, J. Zhang, in: Proceedings of the 31st Annual ACM SIGACT-SIGOPS Symposium on Principles and Distributed Computing (PODC), 2012, pp. 291–300.' date_created: 2017-10-17T12:42:53Z date_updated: 2022-01-06T07:02:58Z ddc: - '040' department: - _id: '79' doi: 10.1145/2332432.2332488 file: - access_level: closed content_type: application/pdf creator: florida date_created: 2018-03-15T06:45:25Z date_updated: 2018-03-15T06:45:25Z file_id: '1241' file_name: 623-PODC-2012_01.pdf file_size: 210382 relation: main_file success: 1 file_date_updated: 2018-03-15T06:45:25Z has_accepted_license: '1' page: 291-300 project: - _id: '1' name: SFB 901 - _id: '13' name: SFB 901 - Subprojekt C1 - _id: '4' name: SFB 901 - Project Area C publication: Proceedings of the 31st Annual ACM SIGACT-SIGOPS Symposium on Principles and Distributed Computing (PODC) status: public title: Competitive and fair throughput for co-existing networks under adversarial interference type: conference user_id: '15504' year: '2012' ... --- _id: '625' abstract: - lang: eng text: 'This paper initiates the study of self-adjusting distributed data structures for networks. In particular, we present SplayNets: a binary search tree based network that is self-adjusting to routing request.We derive entropy bounds on the amortized routing cost and show that our splaying algorithm has some interesting properties.' author: - first_name: Stefan full_name: Schmid, Stefan last_name: Schmid - first_name: Chen full_name: Avin, Chen last_name: Avin - first_name: Christian full_name: Scheideler, Christian id: '20792' last_name: Scheideler - first_name: Bernhard full_name: Häupler, Bernhard last_name: Häupler - first_name: Zvi full_name: Lotker, Zvi last_name: Lotker citation: ama: 'Schmid S, Avin C, Scheideler C, Häupler B, Lotker Z. Brief Announcement: SplayNets - Towards Self-Adjusting Distributed Data Structures. In: Proceedings of the 26th International Symposium on Distributed Computing (DISC). LNCS. ; 2012:439-440. doi:10.1007/978-3-642-33651-5_47' apa: 'Schmid, S., Avin, C., Scheideler, C., Häupler, B., & Lotker, Z. (2012). Brief Announcement: SplayNets - Towards Self-Adjusting Distributed Data Structures. In Proceedings of the 26th International Symposium on Distributed Computing (DISC) (pp. 439–440). https://doi.org/10.1007/978-3-642-33651-5_47' bibtex: '@inproceedings{Schmid_Avin_Scheideler_Häupler_Lotker_2012, series={LNCS}, title={Brief Announcement: SplayNets - Towards Self-Adjusting Distributed Data Structures}, DOI={10.1007/978-3-642-33651-5_47}, booktitle={Proceedings of the 26th International Symposium on Distributed Computing (DISC)}, author={Schmid, Stefan and Avin, Chen and Scheideler, Christian and Häupler, Bernhard and Lotker, Zvi}, year={2012}, pages={439–440}, collection={LNCS} }' chicago: 'Schmid, Stefan, Chen Avin, Christian Scheideler, Bernhard Häupler, and Zvi Lotker. “Brief Announcement: SplayNets - Towards Self-Adjusting Distributed Data Structures.” In Proceedings of the 26th International Symposium on Distributed Computing (DISC), 439–40. LNCS, 2012. https://doi.org/10.1007/978-3-642-33651-5_47.' ieee: 'S. Schmid, C. Avin, C. Scheideler, B. Häupler, and Z. Lotker, “Brief Announcement: SplayNets - Towards Self-Adjusting Distributed Data Structures,” in Proceedings of the 26th International Symposium on Distributed Computing (DISC), 2012, pp. 439–440.' mla: 'Schmid, Stefan, et al. “Brief Announcement: SplayNets - Towards Self-Adjusting Distributed Data Structures.” Proceedings of the 26th International Symposium on Distributed Computing (DISC), 2012, pp. 439–40, doi:10.1007/978-3-642-33651-5_47.' short: 'S. Schmid, C. Avin, C. Scheideler, B. Häupler, Z. Lotker, in: Proceedings of the 26th International Symposium on Distributed Computing (DISC), 2012, pp. 439–440.' date_created: 2017-10-17T12:42:53Z date_updated: 2022-01-06T07:02:58Z ddc: - '040' department: - _id: '79' doi: 10.1007/978-3-642-33651-5_47 file: - access_level: closed content_type: application/pdf creator: florida date_created: 2018-03-15T06:44:09Z date_updated: 2018-03-15T06:44:09Z file_id: '1240' file_name: 625-disc12adjBAshort.pdf file_size: 717284 relation: main_file success: 1 file_date_updated: 2018-03-15T06:44:09Z has_accepted_license: '1' page: 439-440 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 26th International Symposium on Distributed Computing (DISC) series_title: LNCS status: public title: 'Brief Announcement: SplayNets - Towards Self-Adjusting Distributed Data Structures' type: conference user_id: '15504' year: '2012' ...