TY - CHAP
AU - Götte, Thorsten
AU - Kolb, Christina
AU - Scheideler, Christian
AU - Werthmann, Julian
ID - 26888
SN - 0302-9743
T2 - Algorithms for Sensor Systems (ALGOSENSORS '21)
TI - Beep-And-Sleep: Message and Energy Efficient Set Cover
ER -
TY - CONF
AB - 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$.
AU - Götte, Thorsten
AU - Hinnenthal, Kristian
AU - Scheideler, Christian
AU - Werthmann, Julian
ED - Censor-Hillel, Keren
ID - 22283
T2 - Proc. of the 40th ACM Symposium on Principles of Distributed Computing (PODC '21)
TI - Time-Optimal Construction of Overlays
ER -
TY - CONF
AU - Dolev, Shlomi
AU - Prasadh Narayanan, Ram
AU - Scheideler, Christian
AU - Schindelhauer, Christian
ED - Galluccio, Laura
ED - Mitra, Urbashi
ED - Magarini, Maurizio
ED - Abada, Sergi
ED - Taynnan Barros, Michael
ED - Krishnaswamy, Bhuvana
ID - 25105
T2 - NANOCOM '21: The Eighth Annual ACM International Conference on Nanoscale Computing and Communication, Virtual Event, Italy, September 7 - 9, 2021
TI - Logarithmic Time MIMO Based Self-Stabilizing Clock Synchronization
ER -
TY - CONF
AU - Dolev, Shlomi
AU - Prasadh Narayanan, Ram
AU - Scheideler, Christian
AU - Schindelhauer, Christian
ED - Galluccio, Laura
ED - Mitra, Urbashi
ED - Magarini, Maurizio
ED - Abada, Sergi
ED - Taynnan Barros, Michael
ED - Krishnaswamy, Bhuvana
ID - 27048
T2 - NANOCOM '21: The Eighth Annual ACM International Conference on Nanoscale Computing and Communication, Virtual Event, Italy, September 7 - 9, 2021
TI - Logarithmic Time MIMO Based Self-Stabilizing Clock Synchronization
ER -
TY - CONF
AU - J. Daymude, Joshua
AU - W. Richa, Andrea
AU - Scheideler, Christian
ED - Gilbert, Seth
ID - 27050
T2 - 35th International Symposium on Distributed Computing, DISC 2021, October 4-8, 2021, Freiburg, Germany (Virtual Conference)
TI - The Canonical Amoebot Model: Algorithms and Concurrency Control
VL - 209
ER -
TY - JOUR
AB - 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.
AU - Knollmann, Till
AU - Scheideler, Christian
ID - 21096
JF - Information and Computation
SN - 0890-5401
TI - A self-stabilizing Hashed Patricia Trie
ER -
TY - CONF
AU - Daymude, Joshua J.
AU - Gmyr, Robert
AU - Hinnenthal, Kristian
AU - Kostitsyna, Irina
AU - Scheideler, Christian
AU - Richa, Andréa W.
ID - 16346
SN - 9781450377515
T2 - Proceedings of the 21st International Conference on Distributed Computing and Networking
TI - Convex Hull Formation for Programmable Matter
ER -
TY - JOUR
AU - Gmyr, Robert
AU - Hinnenthal, Kristian
AU - Kostitsyna, Irina
AU - Kuhn, Fabian
AU - Rudolph, Dorian
AU - Scheideler, Christian
AU - Strothmann, Thim
ID - 17808
IS - 2
JF - Nat. Comput.
TI - Forming tile shapes with simple robots
VL - 19
ER -
TY - CONF
AB - We consider the problem of computing shortest paths in \emph{hybrid networks}, in which nodes can make use of different communication modes. For example, mobile phones may use ad-hoc connections via Bluetooth or Wi-Fi in addition to the cellular network to solve tasks more efficiently. Like in this case, the different communication modes may differ considerably in range, bandwidth, and flexibility. We build upon the model of Augustine et al. [SODA '20], which captures these differences by a \emph{local} and a \emph{global} mode. Specifically, the local edges model a fixed communication network in which $O(1)$ messages of size $O(\log n)$ can be sent over every edge in each synchronous round. The global edges form a clique, but nodes are only allowed to send and receive a total of at most $O(\log n)$ messages over global edges, which restricts the nodes to use these edges only very sparsely.
We demonstrate the power of hybrid networks by presenting algorithms to compute Single-Source Shortest Paths and the diameter very efficiently in \emph{sparse graphs}. Specifically, we present exact $O(\log n)$ time algorithms for cactus graphs (i.e., graphs in which each edge is contained in at most one cycle), and $3$-approximations for graphs that have at most $n + O(n^{1/3})$ edges and arboricity $O(\log n)$. For these graph classes, our algorithms provide exponentially faster solutions than the best known algorithms for general graphs in this model.
Beyond shortest paths, we also provide a variety of useful tools and techniques for hybrid networks, which may be of independent interest.
AU - Feldmann, Michael
AU - Hinnenthal, Kristian
AU - Scheideler, Christian
ID - 20755
T2 - Proceedings of the 24th International Conference on Principles of Distributed Systems (OPODIS)
TI - Fast Hybrid Network Algorithms for Shortest Paths in Sparse Graphs
ER -
TY - JOUR
AB - The maintenance of efficient and robust overlay networks is one
of the most fundamental and reoccurring themes in networking.
This paper presents a survey of state-of-the-art
algorithms to design and repair overlay networks in a distributed
manner. In particular, we discuss basic algorithmic primitives
to preserve connectivity, review algorithms for the fundamental
problem of graph linearization, and then survey self-stabilizing
algorithms for metric and scalable topologies.
We also identify open problems and avenues for future research.
AU - Feldmann, Michael
AU - Scheideler, Christian
AU - Schmid, Stefan
ID - 16902
JF - ACM Computing Surveys
TI - Survey on Algorithms for Self-Stabilizing Overlay Networks
ER -