List of Publications Christian Ortolf

• Journal Articles
• Conference papers
• Other publications

Journal Articles

 back to the top of all publications

2015

• Ortolf C, Schindelhauer C
  Strategies for parallel unaware cleaners
  2015 Theor Comput Sci, volume: 608, issue: 2, pages: 178 - 189
  » show abstract« hide abstract
  Abstract

  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.
  
  
   
  Download file
• Schindelhauer C, Ortolf C
  Strategies for parallel unaware cleaners
  2015 Theor Comput Sci, issue: 608, pages: 178 - 189
• A. Bannoura, C. Ortolf, L. Reindl, C. Schindelhauer
  The Wake Up Dominating Set Problem
  2015 Theoratical Computer Science, pages: 1 - 16
• Bannoura A, Ortolf C, Reindl L, Schindelhauer C
  The wake up dominating set problem
  2015 Theor Comput Sci, issue: 0
  
   
  Download file
• Schindelhauer C, Reindl L, Bannoura A, Ortolf C
  The wake up dominating set problem
  2015 Theor Comput Sci, issue: 608, pages: 120 - 134

Conference papers

 back to the top of all publications

2014

• Ortolf C, Schindelhauer C
  A Recursive Approach to Multi-robot Exploration of Trees
  2014 21th International Colloquium on Structural Information and Communication Complexity, Hida Takayama, Japan Springer, volume: 8576, pages: 343 - 354
  
   
  Download file
• Ortolf C, Schindelhauer C
  Strategies for Parallel Unaware Cleaners
  2014 10th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, Wrocław, Poland

2013

• Bannoura A, Ortolf C, Schindelhauer C, Reindl L M
  The Wake Up Dominating Set Problem
  2013 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, Sophia Antipolis, France Springer, volume: 8243, pages: 35 - 50
• Ortolf C, Schindelhauer C
  Optimal data distribution for heterogeneous parallel storage servers streaming media files
  2013 IEEE 4th International Conference on Cognitive Infocommunications (CogInfoCom), Budapest, Hungary , pages: 45 - 50
  » show abstract« hide abstract
  Abstract

  We consider the problem of distributing media files for streaming on a distributed storage network, where servers have heterogeneous capacities and bandwidths. Regarding networking the servers' bandwidths are the bottlenecks for streaming. We present an algorithm that computes an assignment of n files to m servers for distributing media files such that the streaming speed requirements and capacity constraints are kept. As an additional feature this assignment algorithm works online, i.e. it can assign each file without files to be stored later on. Our algorithm computes the data assignment in time O(nm+mlogm) outperforming linear program solvers.
  
  
   
  Download file
• Schindelhauer C, Ortolf C
  Maximum Distance Separable Codes based on Circulant Cauchy Matrices
  2013 Structural Information and Communication Complexity - 20th International Colloquium, SIROCCO 2013, Ischia, Italy Springer International Publishing, Moscibroda, Thomas and Rescigno, AdeleA., volume: 8179, pages: 334 - 345
• A. Bannoura, C. Ortolf, C. Schindelhauer, L.M. Reindl
  The Wake Up Dominating Set Problem
  2013 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, Sophia Antipolis, France

2012

• Ortolf C, Schindelhauer C
  Online multi-robot exploration of grid graphs with rectangular obstacles
  2012 24th ACM Symposium on Parallelism in Algorithms and Architectures, Pittsburgh, Pennsylvania, USA , pages: 27 - 36
  » show abstract« hide abstract
  Abstract

  We consider the multi-robot exploration problem of an unknown n x n grid graph with oriented disjoint rectangular obstacles. All robots start at a given node and have to visit all nodes of the graph. The robots are unrestricted in their computational power and storage. In the local communication model the robots can exchange any information if they meet at the same node. In the global communication model all robots share the same knowledge. In this paper we present the first nontrivial upper and lower bounds. We show that k robots can explore the graph using only local communication in time O( n log2(n) + (f log n)/k), where f is the number of free nodes in the graph. This establishes a competitive upper bound of O(log2 n). For the lower bound we show a competitive factor of Ω((log k)/(log log k)) for deterministic exploration and Ω(√(log k)/(log log k)) for randomized exploration strategies using global communication.
  
  
   
  Download file as PDF

2010

• Vater A, Schindelhauer C, Ortolf C
  Tree Network Coding for Peer-to-Peer Networks
  2010 Annual Symposium on Parallelism in Algorithms and Architectures SPAA '10: Proceedings of the 22nd ACM symposium on Parallelism in algorithms and architectures, ACM, pages: 114 - 123
  » show abstract« hide abstract
  Abstract

  Partitioning is the dominant technique to transmit large files in peer-to-peer networks. A peer can redistribute each part immediately after its download. BitTorrent combines this approach with incentives for uploads and has thereby become the most successful peer-to-peer network. However, BitTorrent fails if files are unpopular and are distributed by irregularly participating peers. It is known that Network Coding always provides the optimal data distribution, referred as optimal performance. Yet, for encoding or decoding a single code block the whole file must be read and users are not willing to read O(n^2) data blocks from hard disk for sending n message blocks. We call this the disk read/write complexity of an encoding. It is an open question whether fast network coding schemes exist. In this paper we present a solution for simple communication patterns. Here, in a round model each peer can send a limited amount of messages to other peers. We define the depth of this directed acyclic communication graph as the maximum path length (not counting the rounds). In our online model each peer knows the bandwidth of its communication links for the current round, but neither the existence nor the weight of links in future rounds. In this paper we analyze BitTorrent, Network Coding, Tree Coding, and Tree Network Coding. We show that the average encoding and decoding complexity of Tree Coding is bounded by O(k n \log^2 n) disk read/write-operations where k is the number of trees and n the number of data blocks. Tree Coding has perfect performance in communication networks of depth two with a disk read/write complexity of O(p n t \log^3 n) where p is the number of peers, t is the number of rounds, and n is the number of data blocks. For arbitrary networks Tree Coding performs optimally using 2({\delta+1})^{t-1} p \log^2 n trees which results in a read/write complexity of O(({\delta+1})^{t-1} n\log^3 n) for t rounds and in-degree \delta.
  
  
   
  Download file as PDF

2009

• Ortolf C, Schindelhauer C, Vater A
  Classifying Peer-to-Peer Network Coding Schemes
  2009 Annual Symposium on Parallelism in Algorithms and Architectures SPAA '09: Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures, ACM, pages: 310 - 318
  » show abstract« hide abstract
  Abstract

  Modern peer-to-peer file sharing systems distribute large files among peers using block partitioning. Blocks can be redistributed by a peer even before the whole file is available which highly decreases the distribution time. All peer-to-peer networks face the problem of dynamic participation of the peers and dynamic bandwidth in the network. A leaving peer can cause an unrecoverable loss of blocks and obstruct further downloads of the file. Furthermore, the choice which block needs to be sent to which peer is a hard question. A random choice leads to the coupon collector problem which decreases the transmission rate. Filesharing networks like BitTorrent or Splitstream face such problems. Network Coding overcomes this problem by using error redundant codes of all blocks of the file. An efficient randomized variant of it, Practical Network Coding, transmits and recombines random linear combinations of the blocks of the partitioned file. As soon as enough linear combinations have been gathered, the original file can be decoded by a matrix operation, optimizing the network flow in any peer-to-peer network. All known Network Coding schemes, however, suffer from a quadratic cost of read/write disk operations for both encoding and decoding. Since there is an increasing gap between the speed of mass storage devices and the main memory, this poses an obstacle to a wider use of Network Coding schemes. In this paper we present and investigate new network coding schemes, which form a compromise between Network Coding and uncoded block transfer schemes like BitTorrent. These schemes, called Paircoding and Treecoding have smaller read/write costs for encoding and decoding than Practical Network Coding and higher throughput than BitTorrent. We develop a new framework for comparing the throughput of data (performance) of such peer-to-peer file sharing systems and classify these systems, as well as a BitTorrent variant which uses forward error correction. The dynamics of peer-to-peer networks are described by a round model where the set of participating peers and their link quality changes after each round. The framework compares two schemes for all possible dynamic scenarios. If the transmission rate of scheme A is at least as well as scheme B, then we say A performs as well as B. If this is the case and there is a scenario where A is better than B, we say A outperforms B. We show that all of our proposed coding schemes outperform BitTorrent, while being outperformed by Network Coding. This leads to a hierarchy, where BitTorrent is the worst performer and Network Coding is the best performer regarding throughput. Regarding computation (disk read/write) complexity for decoding, BitTorrent and Foward Error Correction have linear time behavior, for Paircoding it is almost linear, Treecoding with one coding tree needs time O(n) and Network Coding has time O(n^2).
  
  
   
  Download file as PDF
• Ortolf C, Schindelhauer C, Vater A
  Paircoding: Improving File Sharing Using Sparse Network Codes
  2009 Fourth International Conference on Internet and Web Applications and Services ICIW '09: Proceedings of the 2009 Fourth International Conference on Internet and Web Applications and Services, IEEE Computer Society, pages: 49 - 57
  » show abstract« hide abstract
  Abstract

  BitTorrent and Practical Network Coding are efficient methods for sharing files in a peer-to-peer network. Both face the problem to distribute a given file using peers with different and dynamic bandwidth and only temporal availability. For this, BitTorrent partitions the files and uses the upload and download of each peer. In addition to this, Practical Network Coding uses a random linear combination of the parts. The original file can be decoded by a matrix operation as soon as enough linear combinations have been gathered at a peer. It is known that Practical Network Coding optimizes the network flow in any peer-to-peer network, yet suffers from the cost of read/write disk operations for encoding and decoding. In this respect, BitTorrent is very efficient, yet falls behind because it has to face the coupon collector problem when distributing parts. We present Paircoding as an alternative which is regarding filesharing at least as good as BitTorrent and shares nearly the same computational disk access complexity with BitTorrent. In some scenarios Paircoding outperforms BitTorrent regarding network flow and performs as well as Practical Network Coding. Paircoding distributes only a linear combination of two parts which alleviates the coupon collector problem of BitTorrent without the computational overhead of Practical Network Coding. For analytical proofs of these statements we formalize filesharing in a peer-to-peer network in a round model and introduce a computational model which allows to compare the efficiency of the filesharing algorithms in a distributed environment. Since BitTorrent tries to overcome the coupon collector problem with various policies we face a family of BitTorrent systems. We show that for each BitTorrent policy there is a Paircoding policy which is at least as good regarding filesharing quality.
  
  
   
  Download file as PDF

Other publications

 back to the top of all publications

2013

• Bannoura A, Ortolf C, Schindelhauer C, Reindl L
  Technical report: The Wake Up Dominating Set Problem
  , issue: 273, 2013
• A. Bannoura, C. Ortolf, C. Schindelhauer, L.M. Reindl
  The Wake Up Dominating Set Problem. Technical Report 273, Department of Computer Science, University of Freiburg
  , 2013