 |
 |
| Department of Computer Science |
| Algorithms
and Complexity Christian Schindelhauer |
| |
   
  |
| |
 
|
| |
| Teaching of Christian Schindelhauer |
| Bachelor thesis: Peer to peer networks | Network Coding in
random networks Contact Christian Schindelhauer/Peter Mahlmann
By the use of special encoding techniques (so-called network coding) data can be broadcasted in a very efficient, fast and robust way. This technique is used to distribute large files such as music files, video files, and software packages by peer-to-peer networks. In this bachelor thesis the student implements a download system which combines a random network with a random linear network coding. This work extends an existing random Java based peer-to-peer-network. |
| Bachelor thesis: On-line algorithms | On-line
exploration and on-line Routing: Visualization of JITE (Just in
time
multiple message on-line routing) Contact Christian Schindelhauer/Stefan Rührup We consider the problem of routing a message in a mesh network with faulty nodes. The number and positions of faulty nodes is unknown. It is known that a flooding strategy like expanding ring search can route a message linear in the minimum number of steps h while it causes a traffic (i.e. the total  number of messages) of O(h2).
For optimizing traffic a single-path strategy is optimal producing
traffic O(h+p), where p is the number of border nodes neighbored to
faulty nodes. The JITE protocol is a deterministic multi-path online
routing algorithm that delivers a message within O(h) steps causing
traffic O((h+p) log3h). In this bachelor thesis the student implements a Java applet that presents the JITE-algorithm and other algorithms. |
| Bachelor Thesis
Ad-hoc-networks: |
Efficiency and
Fairness in the medium access layer (MAC) Contact: Christian Schindelhauer Mobile ad-hoc-networks are distributed self-organizing wireless communications networks without central control. The frequency band available for such networks is limited and concurrent systems cannot distinguish other networks from static noise. If network protocols simply ignore this fact and increase signal strength then all eventually no communication is possible. So, it is advisable to back off like the AIMD-strategy within TCP. In this bachelor thises the student examines distributed probabilistic procedures according to their ability to share the transmission medium. Using simulation models the student investigates fairness and efficiency, i.e. bandwidth utilization. |
| Topics
for Master Theses also refer to current research. Topics cover the following areas.
|
|
| Master Thesis: Distributed Algorithms |
Distributed data
aggregation in the Push and Pull model Contact: Christian Schindelhauer/Peter Mahlmann
The following game describes that
Random call model. In each round each player selects a random
communication partner. If the information is transmitted from the
calling to the callee, this transfer is called a "push". If the callee
transfers an information to the caller this operaiton is called "pull". |
| Master thesis: Peer to peer networks |
The mixing time of
coincidental Peer ton Peer networks Contact: Christian Schindelhauer/Peter Mahlmann Many networks, like for example Gnutella, have no central structures or hierarchies. Thus they are nearly invulnerable and indestructible. Further improvements are possible if Peers exchange regularly neighbors. A possibility is the Plush operation (see illustration). 
One can prove, the Plush (also known as Push&Pull) always produces a uniform random graph. However, the speed of convergence is an open problem. A goal of this master thesis is to enhance our knowledge on this process. This can be done by empirical experiments of via rigorous analysis of the underlying Markov. |
| Master thesis: Sensor networks | Energy efficient
protocols for sensor networks Contact: Christian Schindelhauer Wireless sensor networks have become a very important research subject due to their potential of providing diverse services to numerous applications. In Paderborn we have developed a protocol called 1QK, enabling an energy efficient wireless multi-hop sensor network. It collects sensor data from sensor nodes and to send application data to sensor nodes. Due to many restrictions concerning hardware and software, both, the use of energy  efficient components and the development of new
protocols and architectures are necessary to satisfy all conditions.
Moreover the cost aspect in our application has to be mentioned as an
extra critical point, since the industry plans to produce millions of
these sensor nodes.In its latest version 1QK uses only 128 Bytes RAM (1Q = 1 quarter Kilobyte) and utilizes several channels. This is the result of a preceding master thesis and a bachelor thesi As the next step this protocol may be improved and experimental studies on an implementation. |
| Master thesis: Ad hoc networks |
Analysis
and test of a mobile Ad-hoc-network Contact: Christian Schindelhauer Ad-hoc-networks are wireless networks without central control and control. They connect laptop with each other and with the Internet. PAMANET (the Paderborn Mobile Ad hoc NETwork) has been developed in cooperation with the research groups of Franz Rammig and Stefan Böttcher within a students' project group. The main advantage of PAMANET is its scalability, i.e. it can  connect arbitrarily many network nodes.A goal of this master thesis is the theoretical analysis of PAMANET and/or the execution and evaluation of field tests with a large number network nodes (> 100). This master thesis uses the results of a preceding students' project group and a preceding bachelor thesis. |
| Master thesis: Computational complexity |
Expected hard problems Contact: Christian Schindelhauer Leonid Levin introduced the theory of Average-NP-compeletenes. In a nutshell this theory says, that if an Average-NP-complete problem can be solved in average polynomial time, then all NP problems can be solved in polynomial time. For this he considered problem and probability distribution as so-called distributional problem. Furthermore, he used a weaker notion than the expectation measure, which bounds the expectation of a polynomial root of the running time. The reason is that the expectation measure preserves simulation properties. The goal of this master thesis is to revisit the reasons to choose this weaker (now called Levin's) measure. Is it possible to define Average-NP-completeness based on the expectation? And if not, why? |
| Topics
for Phd Theses Please contact me. If there are open positions for Phd students in our research group this information will be stated here. |
|
Current
and past students
|
|
|
Created 2005-10-02 Last Change 2006-02-09 Copyright Christian Schindelhauer |