@proceedings{33968, editor = {{Scheideler, Christian}}, isbn = {{978-3-95977-255-6}}, publisher = {{Schloss Dagstuhl - Leibniz-Zentrum für Informatik}}, title = {{{36th International Symposium on Distributed Computing, DISC 2022, October 25-27, 2022, Augusta, Georgia, USA}}}, volume = {{246}}, year = {{2022}}, } @phdthesis{30239, author = {{Kolb, Christina}}, title = {{{Competitive Routing in Hybrid Communications Networks and Message efficient SetCover in AdHoc Networks}}}, doi = {{10.17619/UNIPB/1-1673 }}, year = {{2022}}, } @article{21096, abstract = {{While many research in distributed computing has covered solutions for self-stabilizing computing and topologies, there is far less work on self-stabilization for distributed data structures. However, when peers in peer-to-peer networks crash, a distributed data structure may not remain intact. We present a self-stabilizing protocol for a distributed data structure called the Hashed Patricia Trie (Kniesburges and Scheideler WALCOM'11) that enables efficient prefix search on a set of keys. The data structure has many applications while offering low overhead and efficient operations when embedded on top of a Distributed Hash Table. Especially, longest prefix matching for x can be done in O(log |x|) hash table read accesses. We show how to maintain the structure in a self-stabilizing way, while assuring a low overhead in a legal state and an asymptotically optimal memory demand of O(d) bits, where d is the number of bits needed for storing all keys.}}, author = {{Knollmann, Till and Scheideler, Christian}}, issn = {{0890-5401}}, journal = {{Information and Computation}}, title = {{{A self-stabilizing Hashed Patricia Trie}}}, doi = {{10.1016/j.ic.2021.104697}}, year = {{2022}}, } @phdthesis{24887, author = {{Hinnenthal, Kristian}}, title = {{{Models and Algorithms for Hybrid Networks and Hybrid Programmable Matter}}}, doi = {{10.17619/UNIPB/1-1169 }}, year = {{2021}}, } @misc{27053, author = {{Everling, Leon}}, title = {{{Selbststabilisierender Bakery Algorithmus für verteilte Systeme}}}, year = {{2021}}, } @misc{27072, author = {{Adsul, Vaibhav}}, title = {{{Peer-to-Peer Matching for Distributed Systems}}}, year = {{2021}}, } @misc{21084, author = {{Werthmann, Julian}}, title = {{{Derandomization and Local Graph Problems in the Node-Capacitated Clique}}}, year = {{2021}}, } @misc{21197, author = {{Mengshi, Ma}}, title = {{{Self-stabilizing Arrow Protocol on Spanning Trees with a Low Diameter}}}, year = {{2021}}, } @phdthesis{21628, abstract = {{This thesis considers the realization of distributed data structures and the construction of distributed protocols for self-stabilizing overlay networks. In the first part of this thesis, we provide distributed protocols for queues, stacks and priority queues that serve the insertion and deletion of elements within a logarithmic amount of rounds. Our protocols respect semantic constraints such as sequential consistency or serializability and the individual semantic constraints given by the type (queue, stack, priority queue) of the data structure. We furthermore provide a protocol that handles joining and leaving nodes. As an important side product, we present a novel protocol solving the distributed $k$-selection problem in a logarithmic amount of rounds, that is, to find the $k$-smallest elements among a polynomial number of elements spread among $n$ nodes. The second part of this thesis is devoted to the construction of protocols for self-stabilizing overlay networks, i.e., distributed protocols that transform an overlay network from any initial (potentially illegitimate) state into a legitimate state in finite time. We present protocols for self-stabilizing generalized De Bruijn graphs, self-stabilizing quadtrees and self-stabilizing supervised skip rings. Each of those protocols comes with unique properties that makes it interesting for certain distributed applications. Generalized De Bruijn networks provide routing within a constant amount of hops, thus serving the interest in networks that require a low latency for requests. The protocol for the quadtree guarantees monotonic searchability as well as a geometric variant of monotonic searchability, making it interesting for wireless networks or applications needed in the area of computational geometry. The supervised skip ring can be used to construct a self-stabilizing publish-subscribe system. }}, author = {{Feldmann, Michael}}, title = {{{Algorithms for Distributed Data Structures and Self-Stabilizing Overlay Networks}}}, doi = {{10.17619/UNIPB/1-1113}}, year = {{2021}}, } @article{20683, author = {{Feldkord, Björn and Knollmann, Till and Malatyali, Manuel and Meyer auf der Heide, Friedhelm}}, journal = {{Theory of Computing Systems}}, pages = {{943–984}}, title = {{{Managing Multiple Mobile Resources}}}, doi = {{10.1007/s00224-020-10023-8}}, volume = {{65}}, year = {{2021}}, } @inproceedings{20817, author = {{Bienkowski, Marcin and Feldkord, Björn and Schmidt, Pawel}}, booktitle = {{Proceedings of the 38th Symposium on Theoretical Aspects of Computer Science (STACS)}}, pages = {{14:1 -- 14:17}}, title = {{{A Nearly Optimal Deterministic Online Algorithm for Non-Metric Facility Location}}}, doi = {{10.4230/LIPIcs.STACS.2021.14}}, year = {{2021}}, } @inproceedings{22283, abstract = {{ We show how to construct an overlay network of constant degree and diameter $O(\log n)$ in time $O(\log n)$ starting from an arbitrary weakly connected graph. We assume a synchronous communication network in which nodes can send messages to nodes they know the identifier of and establish new connections by sending node identifiers. If the initial network's graph is weakly connected and has constant degree, then our algorithm constructs the desired topology with each node sending and receiving only $O(\log n)$ messages in each round in time $O(\log n)$, w.h.p., which beats the currently best $O(\log^{3/2} n)$ time algorithm of [Götte et al., SIROCCO'19]. Since the problem cannot be solved faster than by using pointer jumping for $O(\log n)$ rounds (which would even require each node to communicate $\Omega(n)$ bits), our algorithm is asymptotically optimal. We achieve this speedup by using short random walks to repeatedly establish random connections between the nodes that quickly reduce the conductance of the graph using an observation of [Kwok and Lau, APPROX'14]. Additionally, we show how our algorithm can be used to efficiently solve graph problems in \emph{hybrid networks} [Augustine et al., SODA'20]. Motivated by the idea that nodes possess two different modes of communication, we assume that communication of the \emph{initial} edges is unrestricted. In contrast, only polylogarithmically many messages can be communicated over edges that have been established throughout an algorithm's execution. For an (undirected) graph $G$ with arbitrary degree, we show how to compute connected components, a spanning tree, and biconnected components in time $O(\log n)$, w.h.p. Furthermore, we show how to compute an MIS in time $O(\log d + \log \log n)$, w.h.p., where $d$ is the initial degree of $G$.}}, author = {{Götte, Thorsten and Hinnenthal, Kristian and Scheideler, Christian and Werthmann, Julian}}, booktitle = {{Proc. of the 40th ACM Symposium on Principles of Distributed Computing (PODC '21)}}, editor = {{Censor-Hillel, Keren}}, location = {{Virtual}}, publisher = {{ACM}}, title = {{{Time-Optimal Construction of Overlays}}}, doi = {{10.1145/3465084.3467932}}, year = {{2021}}, } @inbook{26888, author = {{Götte, Thorsten and Kolb, Christina and Scheideler, Christian and Werthmann, Julian}}, booktitle = {{Algorithms for Sensor Systems (ALGOSENSORS '21)}}, issn = {{0302-9743}}, location = {{Lisbon, Portgual}}, title = {{{Beep-And-Sleep: Message and Energy Efficient Set Cover}}}, doi = {{10.1007/978-3-030-89240-1_7}}, year = {{2021}}, } @misc{44234, author = {{Berger, Thilo Frederik}}, title = {{{Combining Mobility, Heterogeneity, and Leasing Approaches for Online Resource Allocation}}}, year = {{2021}}, } @misc{44233, author = {{Pranger, Sebastian}}, title = {{{Online k-Facility Reallocation using k-Server Algorithms}}}, year = {{2021}}, } @misc{20221, author = {{Yeole, Paresh Kishor}}, title = {{{Plurality Consensus in Hybrid Networks}}}, year = {{2020}}, } @inproceedings{17370, abstract = {{ We consider a natural extension to the metric uncapacitated Facility Location Problem (FLP) in which requests ask for different commodities out of a finite set \( S \) of commodities. Ravi and Sinha (SODA 2004) introduced the model as the \emph{Multi-Commodity Facility Location Problem} (MFLP) and considered it an offline optimization problem. The model itself is similar to the FLP: i.e., requests are located at points of a finite metric space and the task of an algorithm is to construct facilities and assign requests to facilities while minimizing the construction cost and the sum over all assignment distances. In addition, requests and facilities are heterogeneous; they request or offer multiple commodities out of $S$. A request has to be connected to a set of facilities jointly offering the commodities demanded by it. In comparison to the FLP, an algorithm has to decide not only if and where to place facilities, but also which commodities to offer at each. To the best of our knowledge we are the first to study the problem in its online variant in which requests, their positions and their commodities are not known beforehand but revealed over time. We present results regarding the competitive ratio. On the one hand, we show that heterogeneity influences the competitive ratio by developing a lower bound on the competitive ratio for any randomized online algorithm of \( \Omega ( \sqrt{|S|} + \frac{\log n}{\log \log n} ) \) that already holds for simple line metrics. Here, \( n \) is the number of requests. On the other side, we establish a deterministic \( \mathcal{O}(\sqrt{|S|} \cdot \log n) \)-competitive algorithm and a randomized \( \mathcal{O}(\sqrt{|S|} \cdot \frac{\log n}{\log \log n} ) \)-competitive algorithm. Further, we show that when considering a more special class of cost functions for the construction cost of a facility, the competitive ratio decreases given by our deterministic algorithm depending on the function.}}, author = {{Castenow, Jannik and Feldkord, Björn and Knollmann, Till and Malatyali, Manuel and Meyer auf der Heide, Friedhelm}}, booktitle = {{Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures}}, isbn = {{9781450369350}}, keywords = {{Online Multi-Commodity Facility Location, Competitive Ratio, Online Optimization, Facility Location Problem}}, title = {{{The Online Multi-Commodity Facility Location Problem}}}, doi = {{10.1145/3350755.3400281}}, year = {{2020}}, } @proceedings{17836, editor = {{Werneck Richa, Andrea and Scheideler, Christian}}, isbn = {{978-3-030-54920-6}}, publisher = {{Springer}}, title = {{{Structural Information and Communication Complexity - 27th International Colloquium, SIROCCO 2020, Paderborn, Germany, June 29 - July 1, 2020, Proceedings}}}, doi = {{10.1007/978-3-030-54921-3}}, volume = {{12156}}, year = {{2020}}, } @proceedings{17839, editor = {{Scheideler, Christian and Spear, Michael}}, isbn = {{978-1-4503-6935-0}}, publisher = {{ACM}}, title = {{{SPAA '20: 32nd ACM Symposium on Parallelism in Algorithms and Architectures, Virtual Event, USA, July 15-17, 2020}}}, doi = {{10.1145/3350755}}, year = {{2020}}, } @misc{20495, author = {{Jochmaring, Moritz}}, title = {{{A self stabilizing protocol for well-formed trees in hybrid networks}}}, year = {{2020}}, }