Christian Schindelhauer

TCS Journal 2015 Journal Article

Strategies for parallel unaware cleaners

• Christian Ortolf
• Christian Schindelhauer

We investigate the parallel traversal of a graph with multiple robots unaware of each other. All robots traverse the graph in parallel forever and the goal is to minimize the time needed until the last node is visited (first visit time) and the time between revisits of a node (revisit time). We also want to minimize the visit time, i. e. the maximum of the first visit time and the time between revisits of a node. We present randomized algorithms for uncoordinated robots, which can compete with the optimal coordinated traversal by a small factor, the so-called competitive ratio. For any number of robots ring and path graph simple traversal strategies allow constant competitive factors even in the worst case. For grid and torus graphs with n nodes and any number of robots there is an O ( log ⁡ n ) -competitive algorithm for both visit problems succeeding with high probability, i. e. with probability 1 − n − O ( 1 ). For general graphs we present an O ( log 2 ⁡ n ) -competitive algorithm for the first visit problem, while for the visit problem we show an O ( log 3 ⁡ n ) -competitive algorithm both succeeding with high probability.

TCS Journal 2015 Journal Article

The wake up dominating set problem

• Amir Bannoura
• Christian Ortolf
• Leonhard Reindl
• Christian Schindelhauer

Recently developed wake-up receivers pose a viable alternative for duty-cycling in wireless sensor networks. Here, a special radio signal can wake up close-by nodes. We model the wake-up range by the unit-disk graph. Such wake-up radio signals are very energy expensive and limited in range. Therefore, their number must be minimized. We revisit the Connected Dominating Set (CDS) problem for unit-disk graphs and consider an online variant, where starting from an initial node all nodes need to be woken up, while the online algorithm knows only the nodes woken up so far and has no information about the number and location of the sleeping nodes. We show that in general this problem cannot be solved effectively, since a worst-case setting exists where the competitive ratio, i. e. the number of wake-up signals divided by the size of the minimum CDS, is Θ ( n ) for n nodes. For dense random uniform placements, this problem can be solved within a constant factor competitive ratio with high probability, i. e. 1 − n − c, when the nodes positions are known or at least some rough distance estimator. For a restricted adversary with a reduced wake-up range of 1 − ϵ we present a deterministic wake-up algorithm with a competitive ratio of O ( ϵ − 1 2 ) for the general problem in two dimensions. In the case of random placement without any explicit position information we present an O ( log ⁡ n ) -competitive epidemic algorithm to wake up all nodes with high probability. Simulations show that a simplified version of this oblivious online algorithm already produces reasonable results, that allow its application in the real world.

TCS Journal 2014 Journal Article

Polynomial-time approximation algorithms for anchor-free TDoA localization

• Johannes Wendeberg
• Christian Schindelhauer

We consider the problem of anchor-free self-calibration of receiver locations using only the reception time of signals produced at unknown locations and time points. In our settings the receivers are synchronized, so the time differences of arrival (TDoA) of the signals arriving at the receivers can be calculated. Given the set of distinguishable time points for all receivers the task is to determine the positions of the receivers as well as the signal sources. We present the first polynomial-time approximation algorithms for the minimum problem in the plane, in which the number of receivers is four, respectively the number of signals is three. For this, we first consider the problem that the time points of m signals are jittered by at most some ϵ > 0. We provide an algorithm which tests whether n given receiver positions are valid for measurements from m unknown senders with a run-time of O ( n 2 m ), and we provide an algorithm with run-time O ( n m log ⁡ m ) which tests the validity of m given sender positions for n unknown receiver positions. Using these tests, we can compute all possible receiver and signal source positions in time O ( ( 2 / ϵ ) 2 n − 3 n 2 m ), respectively O ( ( 2 / ϵ ) 2 m − 3 n m log ⁡ m ).

TAAS Journal 2012 Journal Article

An erasure-resilient encoding system for flexible reading and writing in storage networks

• Mario Mense
• Christian Schindelhauer

We introduce the Read-Write-Coding-System (RWC), a very flexible class of linear block codes that generate efficient and flexible erasure codes for storage networks. In particular, given a message x of k symbols and a codeword y of n symbols, an RW code defines additional parameters k≤ r,w≤ n that offer enhanced possibilities to adjust the fault-tolerance capability of the code. More precisely, an RWC provides linear (n,r,d) -codes that have: (a) minimum (Hamming) distance d = n-r+1 for any two codewords, and (b) for any codeword y 1 there exists a codeword y 2 with distance of at most w. Furthermore, depending on the values r,w and the code alphabet, different block codes such as parity codes (e.g., RAID 4/5) or Reed-Solomon (RS) codes (if r = k and thus, w = n ) can be generated. In storage networks in which I/O accesses are very costly and redundancy is crucial, this flexibility has considerable advantages as r and w can optimally be adapted to read or write intensive applications; only w symbols must be updated if the message x changes completely, which is different from other codes that always need to rewrite y completely as x changes. In this article, we first state a tight lower bound and basic conditions for all RW codes. Furthermore, we introduce special RW codes in which all mentioned parameters are adjustable even online, that is, RW codes which are adaptive to changing demands. At last, we investigate the question for which choices of (k,r,w,n) a coding system exists over the binary alphabet F 2 = {0,1} and discuss how RW codes can be combined.

TCS Journal 2012 Journal Article

Self-Localization based on Ambient Signals

• Johannes Wendeberg
• Thomas Janson
• Christian Schindelhauer

We present an approach for the localization of passive nodes in a communication network using ambient radio or sound signals. In our settings, the communication nodes have unknown positions. They do not emit signals for localization and exchange only the time points when environmental signals are received: the time differences of arrival (TDOA). The signals occur at distant but unknown positions and they can be distinguished. Since no anchors are available, the goal is to determine the relative positions of all communication nodes and the environmental signals. Our novel approach, the Ellipsoid TDOA method, introduces a closed form solution assuming that the signals originate from remote distances. The TDOA measurements characterize an ellipse from which the distances and angles between three network nodes can be inferred. In contrast to existing approaches, we do not require the receiver nodes to be synchronized. Furthermore, we can calculate the time offsets of the receiver clocks as a result of our calculations and synchronize the receivers in this way. The approach is tested in numerous simulations and in indoor and outdoor settings, where the relative positions of mobile devices are determined using only the sounds produced by assistants with noisemakers.

AAMAS Conference 2010 Conference Paper

Decentralized Hash Tables For Mobile Robot Teams Solving Intra-Logistics Tasks

• Dali Sun
• Alexander Kleiner
• Christian Schindelhauer

Although a remarkably high degree of automation has beenreached in production and intra-logistics nowadays, humanlabor is still used for transportation using handcarts andforklifts. High labor cost and risk of injury are the undesirable consequences. Alternative approaches in automatedwarehouses are fixed installed conveyors installed either overhead or floor-based. The drawback of such solutions is thelack of flexibility, which is necessary when the productionlines of the company change. Then, such an installation hasto be re-built. In this paper, we propose a novel approach of decentralized teams of autonomous robots performing intra-logisticstasks using distributed algorithms. Centralized solutionssuffer from limited scalability and have a single point of failure. The task is to transport material between stations keeping the communication network structure intact and mostimportantly, to facilitate a fair distribution of robots amongloading stations. Our approach is motivated by strategiesfrom peer-to-peer-networks and mobile ad-hoc networks. Inparticular we use an adapted version of distributed heterogeneous hash tables (DHHT) for distributing the tasks andlocalized communication. Experimental results presented inthis paper show that our method reaches a fair distributionof robots over loading stations.

TCS Journal 2009 Journal Article

Improving the average delay of sorting

• Andreas Jakoby
• Maciej Liśkiewicz
• Rüdiger Reischuk
• Christian Schindelhauer

In previous work we have introduced an average case measure for the time complexity of Boolean circuits. Instead of fixed circuit depth, for each input we take the minimal number of time steps necessary to perform the computation for that particular input using gates that forward their output values as soon as possible. This measure is called delay. Based on it, the complexity of a whole class of functions that can be described as prefix computations has been analysed in detail. Here we consider the problem to sort large integers that are given in binary notation. Contrary to a word comparator sorting circuit C where a basic computational element, a comparator, is charged with a single time step to compare two elements, in a bit comparator circuit C ′ a comparison of two binary numbers has to be implemented by a Boolean subcircuit CM called comparator module that is built from Boolean gates of bounded fanin. Thus, compared to C, the depth of C ′ will be larger by a factor up to the depth of CM. Our goal is to minimize the average delay of bit comparator sorting circuits. The worst-case delay can be estimated by the depth of the circuit. For this worst-case measure two topologically quite different designs seem to be appropriate for the comparator modules: a tree-like one if the inputs are long numbers, otherwise a linear array working in a pipelined fashion. Inserting these into a word comparator circuit we get bit level sorting circuits for binary numbers of length m, for which the depth is either increased by a multiplicative factor of order log m or by an additive term of order m. We show that these obvious solutions can be improved significantly by constructing efficient sorting and merging circuits for the bit model that only suffer a constant factor time loss on the average if the inputs are uniformly distributed. This is done by designing suitable hybrid architectures of tree compaction and pipelining. These results can also be extended to classes of nonuniform distributions if we put a bound on the complexity of the distributions themselves.

MFCS Conference 2006 Conference Paper

Smart Robot Teams Exploring Sparse Trees

• Miroslaw Dynia
• Jaroslaw Kutylowski
• Friedhelm Meyer auf der Heide
• Christian Schindelhauer

Abstract We consider a tree which has to be completely explored by a group of k robots, initially placed at the root. The robots are mobile and can communicate using radio devices, but the communication range is bounded. They decide based on local, partial knowledge, and exchange information gathered during the exploration. There is no central authority which knows the graph and could control the movements of the robots – they have to organize themselves and jointly explore the tree. The problem is that at every point of time the remaining unknown part of the tree may appear to be the worst case setting for the current deployment of robots. We present a deterministic distributed algorithm to explore T and we use a parameter of a tree called density. We compare the performance of our algorithm with the optimal algorithm having a-priori knowledge of the same tree. We show that the above ratio is influenced only by the density and the height of the tree. Since the competitive ratio does not depend on the number of robots, our algorithm truly emphasizes the phenomena of self-organization. The more robots are provided, the faster the exploration of the terrain is completed.

FOCS Conference 2000 Conference Paper

Randomized Rumor Spreading

• Richard M. Karp
• Christian Schindelhauer
• Scott Shenker
• Berthold Vöcking

Investigates the class of epidemic algorithms that are commonly used for the lazy transmission of updates to distributed copies of a database. These algorithms use a simple randomized communication mechanism to ensure robustness. Suppose n players communicate in parallel rounds in each of which every player calls a randomly selected communication partner. In every round, players can generate rumors (updates) that are to be distributed among all players. Whenever communication is established between two players, each one must decide which of the rumors to transmit. The major problem is that players might not know which rumors their partners have already received. For example, a standard algorithm forwarding each rumor form the calling to the called players for /spl Theta/(ln n) rounds needs to transmit the rumor /spl Theta/(n ln n) times in order to ensure that every player finally receives the rumor with high probability. We investigate whether such a large communication overhead is inherent to epidemic algorithms. On the positive side, we show that the communication overhead can be reduced significantly. We give an algorithm using only O(n ln ln n) transmissions and O(ln n) rounds. In addition, we prove the robustness of this algorithm. On the negative side, we show that any address-oblivious algorithm needs to send /spl Omega/(n ln ln n) messages for each rumor, regardless of the number of rounds. Furthermore, we give a general lower bound showing that time and communication optimality cannot be achieved simultaneously using random phone calls, i. e. every algorithm that distributes a rumor in O(ln n) rounds needs /spl omega/(n) transmissions.

I&C Journal 1999 Journal Article

Malign Distributions for Average Case Circuit Complexity

• Andreas Jakoby
• Rüdiger Reischuk
• Christian Schindelhauer

In contrast to machine models like Turing machines or random access machines, circuits are a static computational model. The internal information flow of a computation is fixed in advance, independent of the actual input. Therefore, size and depth are natural and simple measures for circuits and provide a worst-case analysis. We consider a new model in which an internal gate is evaluated as soon as its result has been determined by a partial assignment of its inputs. This way, a dynamic notion of delay is obtained which gives rise to an average case measure for the time complexity of circuits. In a previous paper we have obtained tight upper and lower bounds for the average case complexity of several basic Boolean functions. This paper examines the asymptotic average case complexity for the set of alln-ary Boolean functions. In contrast to worst case analysis a simple counting argument does not work. We prove that with respect to the uniform probability distribution almost all Boolean functions require at leastn−log n−loglog nexpected time. On the other hand, there is a significantly large subset of functions that can be computed with a constant average delay. Finally, for an arbitrary Boolean function we compare its worst case and average case complexity. It is shown that for each function that requires circuit depthd, i. e. of worst-case complexityd, the expected time complexity will be at leastd−log n−log dwith respect to an explicitly defined probability distribution. In addition, a nontrivial upper bound on the complexity of such a distribution will be obtained.

STOC Conference 1994 Conference Paper

Circuit complexity: from the worst case to the average case

• Andreas Jakoby
• Rüdiger Reischuk
• Christian Schindelhauer