Arrow Research search

Author name cluster

Christian Scheideler

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

29 papers
2 author rows

Possible papers

29

TCS Journal 2025 Journal Article

Efficient shape formation by 3D hybrid programmable matter: An algorithm for low diameter intermediate structures

  • Kristian Hinnenthal
  • David Liedtke
  • Christian Scheideler

This paper considers the shape formation problem within the 3D hybrid model, where a single agent with a strictly limited viewing range and the computational capacity of a deterministic finite automaton manipulates passive tiles through pickup, movement, and placement actions. The goal is to reconfigure a set of tiles into a specific shape termed an icicle. The icicle, identified as a dense, hole-free structure, is strategically chosen to function as an intermediate shape for more intricate shape formation tasks. It is designed for easy exploration by a finite-state agent, enabling the identification of tiles that can be lifted without breaking connectivity. Compared to the line shape, the icicle presents distinct advantages, including a reduced diameter and the presence of multiple removable tiles. We propose an algorithm that transforms an arbitrary initially connected tile structure into an icicle in O ( n 3 ) steps, matching the runtime of the line formation algorithm from prior work. Our theoretical contribution is accompanied by an extensive experimental analysis, indicating that our algorithm decreases the diameter of tile structures on average.

Details DOI

TCS Journal 2024 Journal Article

Routing schemes for hybrid communication networks

  • Sam Coy
  • Artur Czumaj
  • Christian Scheideler
  • Philipp Schneider
  • Julian Werthmann

We consider the problem of computing routing schemes in the HYBRID model of distributed computing where nodes have access to two fundamentally different communication modes. In this problem nodes have to compute small labels and routing tables that allow for efficient routing of messages in the local network, which typically offers the majority of the throughput. Recent work has shown that using the HYBRID model admits a significant speed-up compared to what would be possible if either communication mode were used in isolation. Nonetheless, if general graphs are used as the input graph the computation of routing schemes still takes polynomial rounds in the HYBRID model. We bypass this lower bound by restricting the local graph to unit-disc-graphs and solve the problem deterministically with running time O ( | H | 2 + log ⁡ n ), label size O ( log ⁡ n ), and size of routing tables O ( | H | 2 ⋅ log ⁡ n ) where | H | is the number of “radio holes” in the network. Our work builds on recent work by Coy et al. , who obtain this result in the much simpler setting where the input graph has no radio holes. We develop new techniques to achieve this, including a decomposition of the local graph into path-convex regions, where each region contains a shortest path for any pair of nodes in it.

Details DOI

TCS Journal 2023 Journal Article

Beep-and-Sleep: Message and Energy Efficient Set Cover

  • Thorsten Götte
  • Christina Kolb
  • Christian Scheideler
  • Julian Werthmann

This article considers message and energy-efficient distributed algorithms for the SetCover Problem. Given a ground set U of n elements and a set S of m subsets of U, we aim to find the minimal number of these subsets that contain all elements. In the default distributed setup of this problem, each set has a bidirected communication link with each element it contains. This results in a communication graph with n + m nodes and degree Δ. The value Δ denotes the maximal degree of the communication graph, i. e. , the maximum of all subsets' sizes and the maximum number of sets an element is contained in. We present SetCover algorithm in the Beeping model that only relies on carrier-sensing. In each synchronous time step, a node can either listen to the channel or beep. A listening node learns if one or more of its neighbors beeped or if none of its neighbors beeped. In particular, it neither learns which neighbors beeped nor how many neighbors beeped exactly. Given this model, we present an algorithm that runs in O ( k 3 ) time and has an expected approximation ratio of O ( Δ 3 / k log 2 ⁡ Δ ). The value k ∈ [ 3, log ⁡ Δ ] is a parameter that lets us trade runtime for approximation ratio similar to the celebrated algorithm by Kuhn and Wattenhofer [14]. Our next result is a O ( k 2 ) -time and O ˜ ( Δ 1 2 + 1 k ( n + m ) ) -message algorithm (where O ˜ ( ⋅ ) hides polylogarithmic factors) with expected approximation ratio of O ( Δ 1 k log ⁡ Δ ) in the K T 0 -Congest model. In this variant of the well-known Congest model, time proceeds in synchronous rounds, and each node can send a distinct message of size O ( log ⁡ ( n + m ) ) to each of its neighbors. Further, each node has a unique identifier of size O ( log ⁡ ( n + m ) ). However, the crucial aspect of K T 0 -Congest is that the nodes do not know their neighbors' identifiers. Our algorithm is almost optimal concerning time and message complexity as we can show that there are hard instances that require Ω ( Δ 1 2 − ϵ m ) messages for a constant approximation ratio.

Details DOI

I&C Journal 2022 Journal Article

A self-stabilizing Hashed Patricia Trie

  • Till Knollmann
  • Christian Scheideler

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 Θ ( d ) bits, where d is the number of bits needed for storing all keys.

Details DOI

SODA Conference 2020 Conference Paper

Shortest Paths in a Hybrid Network Model

  • John Augustine 0001
  • Kristian Hinnenthal
  • Fabian Kuhn
  • Christian Scheideler
  • Philipp Schneider

We introduce a communication model for hybrid networks, where nodes have access to two different communication modes: a local mode where (like in traditional networks) communication is only possible between specific pairs of nodes, and a global mode where (like in overlay networks) communication between any pair of nodes is possible. Typically, communication over short-range connections is cheaper and can be done at a much higher rate than communication via the overlay network. Therefore, we are focusing on the LOCAL model for the local connections where nodes can exchange an unbounded amount of information per round. For the global communication we assume the so-called nodecapacitated clique model, where in each round every node can exchange O (log n )-bit messages with O (log n ) arbitrary nodes. We explore the impact of hybrid communication on the complexity of distributed algorithms by studying the problem of computing shortest paths in the graph given by the local connections. We present the following results. For the all-pairs shortest paths problem, we show that an exact solution can be computed in time Õ ( n 2/3 ), and that approximate solutions can be computed in time but not faster. For the single-source shortest paths problem an exact solution can be computed in time, where SPD denotes the shortest path diameter. Furthermore, a (l + o (1))-approximate solution can be computed in time. Finally, we show that for every constant ε > 0, it is possible to compute an O (1)-approximate solution in time.

Details

MFCS Conference 2018 Conference Paper

Shape Recognition by a Finite Automaton Robot

  • Robert Gmyr
  • Kristian Hinnenthal
  • Irina Kostitsyna
  • Fabian Kuhn
  • Dorian Rudolph
  • Christian Scheideler

Motivated by the problem of shape recognition by nanoscale computing agents, we investigate the problem of detecting the geometric shape of a structure composed of hexagonal tiles by a finite-state automaton robot. In particular, in this paper we consider the question of recognizing whether the tiles are assembled into a parallelogram whose longer side has length l = f(h), for a given function f(*), where h is the length of the shorter side. To determine the computational power of the finite-state automaton robot, we identify functions that can or cannot be decided when the robot is given a certain number of pebbles. We show that the robot can decide whether l = ah+b for constant integers a and b without any pebbles, but cannot detect whether l = f(h) for any function f(x) = omega(x). For a robot with a single pebble, we present an algorithm to decide whether l = p(h) for a given polynomial p(*) of constant degree. We contrast this result by showing that, for any constant k, any function f(x) = omega(x^(6k + 2)) cannot be decided by a robot with k states and a single pebble. We further present exponential functions that can be decided using two pebbles. Finally, we present a family of functions f_n(*) such that the robot needs more than n pebbles to decide whether l = f_n(h).

Details

I&C Journal 2017 Journal Article

Towards a universal approach for the finite departure problem in overlay networks

  • Andreas Koutsopoulos
  • Christian Scheideler
  • Thim Strothmann

A fundamental problem for overlay networks is to safely exclude leaving nodes, i. e. , nodes requesting to leave the network are excluded without affecting connectivity. There are numerous studies for safe node exclusion if the overlay is in a well-defined state, but almost no formal results for the self-stabilizing case. We study this problem in two variants: the Finite Departure Problem ( FDP ) and the Finite Sleep Problem ( FSP ). In the FDP 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 present self-stabilizing protocols for both problems that can be combined with a large class of overlay networks in order to guarantee safe exclusion for leaving nodes from any initial state while operating normal for staying nodes. 1

Details DOI

TCS Journal 2017 Journal Article

Universal coating for programmable matter

  • Zahra Derakhshandeh
  • Robert Gmyr
  • Andréa W. Richa
  • Christian Scheideler
  • Thim Strothmann

The idea behind universal coating is to have a thin layer of a specific substance covering an object of any shape so that one can measure a certain condition (like temperature or cracks) at any spot on the surface of the object without requiring direct access to that spot. We study the universal coating problem in the context of self-organizing programmable matter consisting of simple computational elements, called particles, that can establish and release bonds and can actively move in a self-organized way. Based on that matter, we present a worst-case work-optimal universal coating algorithm that uniformly coats any object of arbitrary shape and size that allows a uniform coating. Our particles are anonymous, do not have any global information, have constant-size memory, and utilize only local interactions.

Details DOI

TCS Journal 2015 Journal Article

A deterministic worst-case message complexity optimal solution for resource discovery

  • Sebastian Kniesburges
  • Andreas Koutsopoulos
  • Christian Scheideler

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 ) ) or bits ( O ( n log ⁡ n ) ) a node receives or sends coincides with the lower bound, while ensuring only a linear runtime ( O ( n ) ) on the number of rounds.

Details DOI

TCS Journal 2013 Journal Article

Corona: A stabilizing deterministic message-passing skip list

  • Rizal Mohd Nor
  • Mikhail Nesterenko
  • Christian Scheideler

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 a 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 identifiers 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.

Details DOI

TCS Journal 2012 Journal Article

Tiara: A self-stabilizing deterministic skip list and skip graph

  • Thomas Clouser
  • Mikhail Nesterenko
  • Christian Scheideler

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.

Details DOI

TCS Journal 2012 Journal Article

Towards higher-dimensional topological self-stabilization: A distributed algorithm for Delaunay graphs

  • Riko Jacob
  • Stephan Ritscher
  • Christian Scheideler
  • Stefan Schmid

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 identifiers, 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 ( n 3 ) 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 affect 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 higher-dimensional linearization problems.

Details DOI

TCS Journal 2009 Journal Article

Robust random number generation for peer-to-peer systems

  • Baruch Awerbuch
  • Christian Scheideler

We consider the problem of designing an efficient and robust distributed random number generator for peer-to-peer systems that is easy to implement and works even if all communication channels are public. A robust random number generator is crucial for avoiding adversarial join–leave attacks on peer-to-peer overlay networks. We show that our new generator together with a light-weight rule recently proposed in [B. Awerbuch, C. Scheideler, Towards a scalable and robust DHT, in: Proc. of the 18th ACM Symp. on Parallel Algorithms and Architectures, SPAA, 2006. See also http: //www14. in. tum. de/personen/scheideler] for keeping peers well distributed can keep various structured overlay networks in a robust state even under a constant fraction of adversarial peers.

Details DOI

STOC Conference 2005 Conference Paper

How to spread adversarial nodes? : rotate!

  • Christian Scheideler

In this paper we study the problem of how to keep a dynamic system of nodes well-mixed even under adversarial behavior. This problem is very important in the context of distributed systems.More specifically, we consider the following game: There are n white pebbles and ε n black pebbles for some fixed constant ε < 1. Initially, all of the white pebbles are laid down in a ring, and the adversary has all of the black pebbles in its bag. In each round, the adversary can look at the entire ring and can select to add a black pebble to the ring (if its bag is not empty) or to take any black pebble from the ring and put it back into its bag (i.e. we consider adaptive adversaries). However, the adversary cannot place a black pebble into any position it likes. This is handled by a join strategy to be specified by the system. The goal is to find an oblivious join strategy, i.e. a strategy that cannot distinguish between the white and black pebbles in the ring, that integrates the black pebbles into this ring and may do some further rearrangements so that for a polynomial number of rounds the adversary will not manage to include its black pebbles into the ring so that there is a sequence of s=Θ(log n) consecutive pebbles in which at least half of the pebbles are black. If this is achieved by the join strategy, it wins. Otherwise, the adversary wins.Of course, the brute-force strategy of rearranging all of the pebbles in the ring at random after each insertion of a black pebble will achieve the stated goal, with high probability, but this would be a very expensive strategy. The challenge is to find a join strategy that needs as little randomness and as few rearrangements as possible in order to win with high probability. In this paper, we present and analyze a very simple strategy called k-rotation that chooses k-1 existing positions uniformly at random in the ring, creates a new position uniformly at random in the ring, and then rotates the new pebble and the k-1 old pebbles along these positions. Interestingly, even if the adversary has just $s$ pebbles, it can still win for k=2. But the k-rotation rule wins with high probability for k=3 as long as ε<2/3, demonstrating that there is a sharp threshold for keeping pebbles in a sufficiently perturbed state.

Details

FOCS Conference 2001 Conference Paper

Simple Routing Strategies for Adversarial Systems

  • Baruch Awerbuch
  • Petra Berenbrink
  • André Brinkmann
  • Christian Scheideler

In this paper we consider the problem of delivering dynamically changing input streams in dynamically changing networks where both the topology and the input streams can change in an unpredictable way. In particular, we present two simple distributed balancing algorithms (one for packet injections and one for flow injections) and show that for the case of a single receiver these algorithms will always ensure that the number of packets or flow in the system is bounded at any time step, even for an injection process that completely saturates the capacities of the available edges and even if the network topology changes in a completely unpredictable way. We also show that the maximum number of packets or flow that can be in the system at any time is essentially best possible by providing a lower bound that holds for any online algorithm, whether distributed or not. Interestingly, our balancing algorithms do not behave well in a completely adversarial setting. We show that also in the other extreme of a static network and a static injection pattern the algorithms will converge to a point in which they achieve an average routing time that is close to the best possible average routing time that can be achieved by any strategy. This demonstrates that there are simple algorithms that can be efficient for very different scenarios.

Details

FOCS Conference 1996 Conference Paper

Deterministic Routing with Bounded Buffers: Turning Offline into Online Protocols

  • Friedhelm Meyer auf der Heide
  • Christian Scheideler

In this paper we present a deterministic protocol for routing arbitrary permutations in arbitrary networks. The protocol is analyzed in terms of the size of the network and the routing number of the network. Given a network H of size n, the routing number of H is defined as the maximum over all permutations /spl pi/ on [n] of the minimal number of steps to route /spl pi/ offline in H. We can show that for any network H of size n with routing number R our protocol needs O(log/sub R/ n/spl middot/R) time to route any permutation in H using only constant size edge buffers. This significantly improves all previously known results on deterministic routing. In particular our result yields optimal deterministic routing protocols for arbitrary networks with diameter /spl Omega/(n/sup /spl epsiv//) or bisection width O(n/sup 1-/spl epsiv//), /spl epsiv/>0 constant. Furthermore we can extend our result to deterministic compact routing. This yields, e. g. , a deterministic routing protocol with runtime O((log n)/(log log n) R) for arbitrary bounded degree networks if only O(log n) bits are available at each node for storing routing information. Our proofs use a new protocol for routing arbitrary r/spl middot/s-relations in r-replicated s-ary Multibutterflies in optimal time O(log, n).

Details

TCS Journal 1996 Journal Article

Exploiting storage redundancy to speed up randomized shared memory simulations

  • Friedhelm Meyer auf der Heide
  • Christian Scheideler
  • Volker Stemann

Assume that a set U of memory locations is distributed among n memory modules, using some number a of hash functions h 1, …, h a, randomly and independently drawn from a high-performance universal class of hash functions. Thus, each memory location has a copies. Consider the task of accessing b out of the a copies for each of given keys x 1, …, x n ∈ U, b < a. The paper presents and analyses a simple process executing the above task on distributed memory machines (DMMs) with n processors. Efficient implementations are presented, implying - a simulation of an n-processor PRAM on an n-processor optical crossbar DMM with delay O(log log n), - a simulation as above on an arbitrary-DMM with delay O( log log n log log log n ), - an implementation of a static dictionary on an arbitrary-DMM with parallel access time O( log∗ n + log log n log a ), if a hash functions are used. In particular, an access time of O(log∗ n) can be reached if (log n) 1 log∗ n hash functions are used. We further prove a lower bound for executing the above process by any so-called simple access protocol, showing that our implementations are optimal.

Details DOI
v2026.09.13