@inproceedings{7636, abstract = {{Self-stabilizing overlay networks have the advantage of being able to recover from illegal states and faults. However, the majority of these networks cannot give any guarantees on their functionality while the recovery process is going on. We are especially interested in searchability, i.e., the functionality that search messages for a specific node are answered successfully if a node exists in the network. In this paper we investigate overlay networks that ensure the maintenance of monotonic searchability while the self-stabilization is going on. 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 extend the existing research by focusing on skip graphs and present a solution for two scenarios: (i) the goal topology is a super graph of the perfect skip graph and (ii) the goal topology is exactly the perfect skip graph. }}, author = {{Luo, Linghui and Scheideler, Christian and Strothmann, Thim Frederik}}, booktitle = {{Proceedings of the 2019 IEEE 33rd International Parallel and Distributed Processing Symposium (IPDPS '19)}}, location = {{Rio de Janeiro, Brazil}}, title = {{{MultiSkipGraph: A Self-stabilizing Overlay Network that Maintains Monotonic Searchability}}}, year = {{2019}}, } @article{8543, abstract = {{Dieser Artikel erörtert, ob in studentischen Kleingruppenprojekten in der Informatik Kreativität und die Erarbeitung kreativer Ideen explizit gefördert werden kann. Dazu wird ein Seminarkonzept detailliert vorgestellt, welches auf zwei Grundkonzepten der Informatikpraxis beruht: agiles Projektvorgehen und Prototyping. Die Teilnehmenden des Seminars wurden gezielt in einen Kreativitätsprozess geleitet, indem sie für gegebene moderne Technologien (Virtual Reality, Augmented Reality, Drohnen, etc.) neuartige Nutzungsszenarien entwickeln sollten. Um zu evaluieren, ob das Lehrkonzept erfolgreich ist, wird sowohl die produktbezogene als auch die prozessbezogene Kreativität betrachtet. Für die produktbezogene Kreativität werden die von den Teilnehmenden erstellten Projektideen inklusive der benutzten Prototypingtechnik vorgestellt und bewertet. Die Teilnehmenden haben nicht nur eine enorme Breite an Ideen entwickelt (in der Summe ca. 40 bei 16 Teilnehmenden), sondern insbesondere auch acht Ideen im Verlaufe des Seminars sehr konkret weiterentwickelt. Hinsichtlich der prozessbezogenen Kreativität wird das Lehrkonzept durch mehrere Fragebögen eruiert. Die Studierenden sind mit dem Seminar, der Herangehensweise und den Ergebnissen sehr zufrieden, was unter anderem durch die äußerst positive studentische Veranstaltungskritik (u.a. 1,0 für den Gesamteindruck sowie Atmosphäre in der Veranstaltung) und die Auswertung der Evaluationsfragebögen unterstrichen wird. Auch von externen Beobachtern werden die erarbeiteten Ergebnisse und der Einsatz von Prototyping als sehr positiv bewertet.}}, author = {{Strothmann, Thim Frederik}}, journal = {{die hochschullehre}}, title = {{{Förderung von Kreativität in studentischen Kleingruppenprojekten in der Informatik – Ein Prototyping-basierter Ansatz}}}, year = {{2019}}, } @inbook{16361, abstract = {{Sinnvolle und gebrauchstaugliche digitale Assistenzsysteme, die Beschäftigte bei ihren alltäglichen Aufgaben unterstützen, stellen eine Herausforderung für viele Organisationen hinsichtlich der individuellen und organisationalen Akzeptanz einschließlich der Gebrauchstauglichkeit (Usability), dem Benutzererlebnis (User Experience, UX) und „Arbeit 4.0“-Aspekten dar. Vorhandene Methoden des Software Engineering sind nicht geeignet, Beschäftigte angemessen in die Gestaltung und Entwicklung zu integrieren und Lösungskonzepte solcher Systeme auf Augenhöhe zu betrachten. In diesem Beitrag wird eine leichtgewichtige Canvas-Methode vorgestellt, die sich mit diesen Herausforderungen befasst. Sie umfasst die menschliche, die geschäftliche sowie die technologische Perspektive in einem gemeinsamen Kommunikationsinstrument, dem „Digital Assistance System Canvas“. Erste Evaluationen zeigen, dass die Teilnehmenden das Canvas-Konzept schätzen und die Methode vielseitig in verschiedenen Szenarien einsetzbar ist. Vielfältige Fragen in den Canvas-Bausteinen bereichern die gemeinsame Diskussion über neue Systeme und die Verbesserung bzw. Sicherstellung der Akzeptanz sowie die Denkweise in frühen Phasen des Design- und Entwicklungsprozesses.}}, author = {{Fischer, Holger Gerhard and Rittmeier, Florian and Strothmann, Thim Frederik and Schwenniger, Nina}}, booktitle = {{Arbeit 4.0 im Mittelstand}}, editor = {{Bosse, Christian K. and Zink, Klaus J.}}, isbn = {{9783662594735}}, publisher = {{Springer Gabler}}, title = {{{Partizipation von Beschäftigten in der Gestaltung einer digitalisierten Arbeitswelt 4.0 mittels einer Canvas-Methode}}}, doi = {{10.1007/978-3-662-59474-2_11}}, year = {{2019}}, } @inproceedings{1163, abstract = {{In this paper we present two major results: First, we introduce the first self-stabilizing version of a supervised overlay network (as introduced in~\cite{DBLP:conf/ispan/KothapalliS05}) by presenting a self-stabilizing supervised skip ring. Secondly, we show how to use the self-stabilizing supervised skip ring to construct an efficient self-stabilizing publish-subscribe system. That is, in addition to stabilizing the overlay network, every subscriber of a topic will eventually know all of the publications that have been issued so far for that topic. The communication work needed to processes a subscribe or unsubscribe operation is just a constant in a legitimate state, and the communication work of checking whether the system is still in a legitimate state is just a constant on expectation for the supervisor as well as any process in the system. }}, author = {{Feldmann, Michael and Kolb, Christina and Scheideler, Christian and Strothmann, Thim Frederik}}, booktitle = {{Proceedings of the 32nd IEEE International Parallel & Distributed Processing Symposium (IPDPS)}}, keywords = {{Topological Self-stabilization, Supervised Overlay, Publish-Subscribe System}}, location = {{Vancouver}}, publisher = {{IEEE}}, title = {{{Self-Stabilizing Supervised Publish-Subscribe Systems}}}, doi = {{10.1109/IPDPS.2018.00114}}, year = {{2018}}, } @article{1796, author = {{J. Daymude, Joshua and Derakhshandeh, Zahra and Gmyr, Robert and Porter, Alexandra and W. Richa, Andrea and Scheideler, Christian and Strothmann, Thim Frederik}}, journal = {{Natural Computing}}, number = {{1}}, pages = {{81----96}}, title = {{{On the runtime of universal coating for programmable matter}}}, doi = {{10.1007/s11047-017-9658-6}}, year = {{2018}}, } @inproceedings{5764, author = {{Gmyr, Robert and Hinnenthal, Kristian and Kostitsyna, Irina and Kuhn, Fabian and Rudolph, Dorian and Scheideler, Christian and Strothmann, Thim Frederik}}, booktitle = {{Proceedings of the 24th International Conference on DNA Computing and Molecular Programming}}, pages = {{122--138}}, publisher = {{Springer International Publishing}}, title = {{{Forming Tile Shapes with Simple Robots}}}, doi = {{10.1007/978-3-030-00030-1_8}}, year = {{2018}}, } @inproceedings{5796, author = {{Engels, Gregor and Strothmann, Thim Frederik and Teetz, Alexander}}, booktitle = {{2018 IEEE 22nd International Enterprise Distributed Object Computing Workshop (EDOCW)}}, isbn = {{9781538641415}}, publisher = {{IEEE}}, title = {{{Adapt Cases 4 BPM - A Modeling Framework for Process Flexibility in IIoT}}}, doi = {{10.1109/edocw.2018.00020}}, year = {{2018}}, } @article{1812, author = {{Koutsopoulos, Andreas and Scheideler, Christian and Strothmann, Thim Frederik}}, journal = {{Inf. Comput.}}, pages = {{408----424}}, title = {{{Towards a universal approach for the finite departure problem in overlay networks}}}, doi = {{10.1016/j.ic.2016.12.006}}, year = {{2017}}, } @article{1814, author = {{Derakhshandeh, Zahra and Gmyr, Robert and W. Richa, Andrea and Scheideler, Christian and Strothmann, Thim Frederik}}, journal = {{Theor. Comput. Sci.}}, pages = {{56----68}}, title = {{{Universal coating for programmable matter}}}, doi = {{10.1016/j.tcs.2016.02.039}}, year = {{2017}}, } @inproceedings{1815, author = {{J. Daymude, Joshua and Gmyr, Robert and W. Richa, Andrea and Scheideler, Christian and Strothmann, Thim Frederik}}, booktitle = {{Algorithms for Sensor Systems - 13th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2017, Vienna, Austria, September 7-8, 2017, Revised Selected Papers}}, pages = {{127----140}}, title = {{{Improved Leader Election for Self-organizing Programmable Matter}}}, doi = {{10.1007/978-3-319-72751-6_10}}, year = {{2017}}, } @phdthesis{61, author = {{Strothmann, Thim Frederik}}, publisher = {{Universität Paderborn}}, title = {{{Self-* Algorithms for Distributed Systems}}}, doi = {{10.17619/UNIPB/1-150}}, year = {{2017}}, } @inproceedings{1836, author = {{Derakhshandeh, Zahra and Gmyr, Robert and Porter, Alexandra and W. Richa, Andrea and Scheideler, Christian and Strothmann, Thim Frederik}}, booktitle = {{DNA Computing and Molecular Programming - 22nd International Conference, DNA 22, Munich, Germany, September 4-8, 2016, Proceedings}}, pages = {{148----164}}, title = {{{On the Runtime of Universal Coating for Programmable Matter}}}, doi = {{10.1007/978-3-319-43994-5_10}}, volume = {{9818}}, year = {{2016}}, } @inproceedings{1837, author = {{Derakhshandeh, Zahra and Gmyr, Robert and W. Richa, Andrea and Scheideler, Christian and Strothmann, Thim Frederik}}, booktitle = {{Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2016, Asilomar State Beach/Pacific Grove, CA, USA, July 11-13, 2016}}, pages = {{289----299}}, publisher = {{ACM}}, title = {{{Universal Shape Formation for Programmable Matter}}}, doi = {{10.1145/2935764.2935784}}, year = {{2016}}, } @article{5762, abstract = {{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. 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 that 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 = {{Strothmann, Thim Frederik}}, issn = {{1526-1719}}, journal = {{Journal of Graph Algorithms and Applications}}, number = {{1}}, pages = {{79--100}}, publisher = {{Journal of Graph Algorithms and Applications}}, title = {{{The Impact of Communication Patterns on Distributed Self-Adjusting Binary Search Tree}}}, doi = {{10.7155/jgaa.00385}}, volume = {{20}}, year = {{2016}}, } @inproceedings{142, abstract = {{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 = {{Scheideler, Christian and Setzer, Alexander and Strothmann, Thim Frederik}}, booktitle = {{Proceedings of the 30th International Symposium on Distributed Computing (DISC)}}, pages = {{71----84}}, title = {{{Towards a Universal Approach for Monotonic Searchability in Self-stabilizing Overlay Networks}}}, doi = {{10.1007/978-3-662-53426-7_6}}, year = {{2016}}, } @inproceedings{241, abstract = {{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 = {{Scheideler, Christian and Setzer, Alexander and Strothmann, Thim Frederik}}, booktitle = {{Proceedings of the 19th International Conference on Principles of Distributed Systems (OPODIS)}}, title = {{{Towards Establishing Monotonic Searchability in Self-Stabilizing Data Structures}}}, doi = {{10.4230/LIPIcs.OPODIS.2015.24}}, year = {{2015}}, } @inproceedings{242, abstract = {{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 = {{Koutsopoulos, Andreas and Scheideler, Christian and Strothmann, Thim Frederik}}, booktitle = {{Proceedings of the 17th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)}}, pages = {{201--216}}, title = {{{Towards a Universal Approach for the Finite Departure Problem in Overlay Networks}}}, doi = {{10.1007/978-3-319-21741-3_14}}, year = {{2015}}, } @inproceedings{243, abstract = {{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 = {{Strothmann, Thim Frederik}}, booktitle = {{Proceedings of the 9th International Workshop on Algorithms and Computation (WALCOM)}}, pages = {{175----186}}, title = {{{The impact of communication patterns on distributed locally self-adjusting binary search trees}}}, doi = {{10.1007/978-3-319-15612-5_16}}, year = {{2015}}, } @inproceedings{1850, author = {{Derakhshandeh, Zahra and Gmyr, Robert and Strothmann, Thim Frederik and A. Bazzi, Rida and W. Richa, Andrea and Scheideler, Christian}}, booktitle = {{DNA Computing and Molecular Programming - 21st International Conference, DNA 21, Boston and Cambridge, MA, USA, August 17-21, 2015. Proceedings}}, isbn = {{978-3-319-21998-1}}, pages = {{117----132}}, title = {{{Leader Election and Shape Formation with Self-organizing Programmable Matter}}}, doi = {{10.1007/978-3-319-21999-8_8}}, volume = {{9211}}, year = {{2015}}, } @inproceedings{1851, author = {{Derakhshandeh, Zahra and Gmyr, Robert and W. Richa, Andrea and Scheideler, Christian and Strothmann, Thim Frederik}}, booktitle = {{Proceedings of the Second Annual International Conference on Nanoscale Computing and Communication, NANOCOM' 15, Boston, MA, USA, September 21-22, 2015}}, isbn = {{978-1-4503-3674-1}}, pages = {{21:1----21:2}}, publisher = {{ACM}}, title = {{{An Algorithmic Framework for Shape Formation Problems in Self-Organizing Particle Systems}}}, doi = {{10.1145/2800795.2800829}}, year = {{2015}}, }