Prof. Dr. Christian Scheideler

Since March 2009 I am at the University of Paderborn

	Email:	scheideler@in.tum.de
	WWW:	http://wwwmayr.in.tum.de/personen/scheideler/
	Phone:	+49-89-289-17709
	Fax:	+49-89-289-17707
	Address:	Lehrstuhl für Effiziente Algorithmen Institut für Informatik Technische Universität München Boltzmannstr. 3 D-85748 Garching
	Room:	MI 03.09.044 (I14)

Office hours: Wed 4-5 pm or by appointment

Research Interests:

distributed algorithms and data structures
security in distributed systems
randomized algorithms and stochastic processes
theory of network communication
(in particular peer-to-peer systems, mobile ad-hoc networks and sensor networks)
combinatorics and discrete mathematics

Job Openings:

A PhD / postdoc position in the DFG Project "Algorithms for self-stabilizing overlay networks"
Student assistant positions (19h/week or 9.5h/week) in the DFG Project "Algorithms for self-stabilizing overlay networks"

Current Courses:

Current Activities:

Coordinator of the InnovaTUM Security Initiative at the TU Munich.
Coach of the ACM ICPC team of the TU Munich.
Secretary of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA).
Local arrangements chair of the ACM SPAA 2008 Conference.
Local arrangements chair of the GI-Jahrestagung 2008.
PC member of IPSN 2008, ICALP 2008, DCOSS 2008 and Algosensors 2008.
PC chair (algorithms track) of IPDPS 2009.

Books:

B. Vöcking, H. Alt, M. Dietzfelbinger, R. Reischuk, C. Scheideler, H. Vollmer and D. Wagner (Ed.)
Taschenbuch der Algorithmen.
Springer Verlag, 2008.
P. Gibbons and C. Scheideler (Ed.)
Proceedings of the 19th ACM Symposium on Parallel Algorithms and Architectures (SPAA).
ACM Press, 2007.
J. Aspnes, C. Scheideler, A. Arora and S. Madden (Ed.)
Proceedings of the 3rd IEEE International Conference on Distributed Computing in Sensor Networks (DCOSS).
Springer Verlag, 2007.
C. Scheideler.
Probabilistic Methods for Coordination Problems.
HNI-Verlagsschriftenreihe 78, University of Paderborn, 2000.
ISBN: 3-931466-77-9.
C. Scheideler.
Universal Routing Strategies for Interconnection Networks.
Lecture Notes in Computer Science 1390, Springer Verlag, 1998.
ISBN: 3-540-64505-5.

Chapters in Books:

C. Scheideler. Overlay Networks for Wireless Systems. To appear in Chansu Yu (Editor), Performance Analysis of Mobile and Ad Hoc Networks, Wireless Networks and Mobile Computing Series, Vol. 7, Nova Science Publishers, 2007.
A. Richa and C. Scheideler. Overlay Networks for Peer-to-Peer Networks. In Teofilo Gonzales (Editor), Handbook of Approximation Algorithms and Metaheuristics, Chapman \& Hall / CRC Press, Chapter 72, 2007.

Papers:

T. Clouser, M. Nesterenko and C. Scheideler.
Tiara: A self-stabilizing deterministic skip list.
To appear in the 10th International Symposium on Stabilization, Safety and Security of Distributed Systems (SSS), 2008.
B. Awerbuch, A. Richa and C. Scheideler.
A jamming-resistant MAC protocol for single-hop wireless networks
In the 27th ACM Symposium on Principles of Distributed Computing (PODC), 2008.
C. Scheideler, A. Richa and P. Santi.
An O(log n) dominating set protocol for wireless ad-hoc networks under the physical interference model
In the 9th ACM Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), 2008.
M. Mense and C. Scheideler.
SPREAD: An adaptive scheme for redundant and fair storage in dynamic heterogeneous storage systems.
In the 19th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2008.
B. Awerbuch and C. Scheideler.
A denial-of-service resistant DHT.
In 21st International Symposium on Distributed Computing (DISC), 2007. A brief announcement also appeared in the 26th ACM Symposium on Principles of Distributed Computing (PODC), 2007.
V. Aggarwal, A. Feldmann and C. Scheideler.
Can ISPs and PSP users cooperate for improved performance?
In ACM Computer Commucation Review, July 2007.
A. Brinkmann, S. Effert, F. Meyer auf der Heide and C. Scheideler.
Dynamic and redundant data placement.
In IEEE International Conference on Distributed Computing Systems (ICDCS), 2007.
B. Awerbuch and C. Scheideler.
Towards scalable and robust overlay networks.
In the 6th Intl. Workshop on Peer-to-Peer Szstems (IPTPS), 2007.
M. Onus, A. Richa and C. Scheideler.
Linearization: Locally self-stabilizing sorting in graphs
In the Workshop on Algorithm Engineering and Experiments (ALENEX), 2007.
B. Awerbuch and C. Scheideler.
Robust random number generation for peer-to-peer systems.
In 10th Int. Conference On Principles of Distributed Systems (OPODIS), pp. 275-289, 2006.
B. Awerbuch and C. Scheideler.
Towards a scalable and robust DHT.
In 18th ACM Symp. on Parallelism in Algorithms and Architectures (SPAA), pp. 318-327, 2006.
K. Kothapalli, M. Onus, C. Scheideler and C. Schindelhauer.
Distributed coloring in O(sqrt{log n}) bit rounds
In IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2006.
C. Scheideler.
Towards a paradigm for robust distributed algorithms and data structures
In 6th Int. HNI Symposium on New Trends in Parallel and Distributed Computing, 2006.
(Here is also the talk, last updated 09/01/06. Also a header file for the Subjects simulation environment and an example program are available for C++.)
C. Scheideler.
Overlay networks for wireless ad hoc networks
In the Proceedings of the IMA Workshop on Wirless Communications, 2005.
K. Kothapalli, M. Onus, A. Richa and C. Scheideler.
Efficient broadcasting and gathering in wireless ad-hoc networks.
In Proc. of 2005 International Symposium on Parallel Architectures, Algorithms, and Networks (I-SPAN), pp. 346-351, 2005.
K. Kothapalli and C. Scheideler.
Supervised peer-to-peer systems
In Proc. of 2005 International Symposium on Parallel Architectures, Algorithms, and Networks (I-SPAN), pp. 188-193, 2005.
M. Korzeniowski and C. Scheideler.
Transparent data structures, or how to make search trees robust in a distributed environment
In Proc. of 2005 International Symposium on Parallel Architectures, Algorithms, and Networks (I-SPAN), pp. 182-187, 2005.
K. Kothapalli, M. Onus, A. Richa and C. Scheideler.
Constant density spanners for wireless ad-hoc networks
In Proc. 17th ACM Symposium on Parallel Algorithms and Architectures (SPAA), 2005.
C. Scheideler.
How to spread adversarial nodes? Rotate!
In Proc. 37th ACM Symposium on Theory of Computing (STOC), 2005.
B. Awerbuch and C. Scheideler.
Group Spreading: A protocol for provably secure distributed name service.
In Proc. 31st Int. Colloquium on Automata, Languages, and Programming (ICALP), 2004.
A. Bagchi, A. Bhargava, A. Chaudhary, D. Eppstein, and C. Scheideler.
The effects of faults on network expansion
In Proc. 16th ACM Symposium on Parallel Algorithms and Architectures (SPAA), 2004.
A. Bhargava, K. Kothapalli, C. Riley, C. Scheideler, and M. Thober.
Pagoda: A dynamic overlay network for routing, data management, and multicasting.
In Proc. 16th ACM Symposium on Parallel Algorithms and Architectures (SPAA), 2004.
B. Awerbuch and C. Scheideler.
Consistent and compact data management in distributed storage systems
In Proc. 16th ACM Symposium on Parallel Algorithms and Architectures (SPAA), 2004.
C. Riley and C. Scheideler
A distributed hash table for computational grids
In IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2004.
G. Ateniese, C. Riley, and C. Scheideler
Survivable monitoring in dynamic networks
In 2nd IEEE International Information Assurance Workshop, 2004.
C. Riley and C. Scheideler
Local load balancing in distributed hash tables.
Unpublished manuscript, Johns Hopkins University, February 2004.
B. Awerbuch and C. Scheideler
Robust distributed name service.
In 3rd Internation Workshop on Peer-to-Peer Systems (IPTPS), 2004.
C. Scheideler and A. Terzis
PALATIN: A platform for interactive algorithms
In 2004 International Zurich Seminar on Communications.
C. Riley and C. Scheideler
Guaranteed broadcasting using SPON: Supervised P2P overlay network
In 2004 International Zurich Seminar on Communications.
B. Awerbuch and C. Scheideler
The Hyperring: A low-congestion deterministic data structure for distributed environments
In Proc. 15th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2004.
V. Damerov, F. Meyer auf der Heide, H. Raecke, C. Scheideler, and C. Sohler
Smoothed motion complexity
In Proc. 11th European Symposium on Algorithms (ESA), 2003.
A. Czumaj, C. Riley, and C. Scheideler
Perfectly balanced allocation
In RANDOM 2003.
B. Awerbuch and C. Scheideler
Peer-to-peer systems for prefix search
In Proc. 22nd ACM Symposium on Principles of Distributed Computing (PODC), 2003.
B. Awerbuch and C. Scheideler
Chord++: Low-congestion routing in Chord
Unpublished manuscript, Johns Hopkins University, June 2003.
B. Awerbuch, A. Brinkmann, and C. Scheideler
Anycasting in adversarial systems: Routing and admission control
In 30th International Colloquium on Automata, Languages, and Programming (ICALP), 2003.
K. Kothapalli and C. Scheideler
Information gathering in adversarial systems: Lines and cycles
In Proc. 15th ACM Symposium on Parallel Algorithms and Architectures (SPAA), 2003.
L. Jia, R. Rajaraman, and C. Scheideler
On local algorithms for topology control and routing in ad hoc networks
In Proc. 15th ACM Symposium on Parallel Algorithms and Architectures (SPAA), 2003.
B. Awerbuch, A. Brinkmann, and C. Scheideler
Anycasting and Multicasting in Adversarial Systems: Routing and Admission Control
Unpublished manuscript, Johns Hopkins University, March 2002.
A. Bagchi, A. Chaudhari, P. Kolman, and C. Scheideler
Algorithms for Fault-Tolerant Routing in Circuit Switched Networks
In Proc. 14th ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 265--274, 2002.
A. Brinkmann, K. Salzwedel, and C. Scheideler.
Compact, Adaptive Placement Strategies for Non-Uniform Capacities
In Proc. 14th ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 53--62, 2002.
C. Scheideler.
Models and Techniques for Communication in Dynamic Networks
In Proc. 19th Symposium on Theoretical Aspects of Computer Science (STACS), pp. 27--49, 2002.
(Here is also the talk).
P. Kolman, C. Scheideler.
Improved Bounds for the Unsplittable Flow Problem (Full Version)
In Proc. 13th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2002.
B. Awerbuch, P. Berenbrink, A. Brinkmann, C. Scheideler.
Simple Routing Strategies for Adversarial Systems (Full Version)
In Proc. 42nd IEEE Symposium on Foundations of Computer Science (FOCS), pp. 158-167, 2001.
P. Kolman, C. Scheideler.
Simple On-Line Algorithms for the Maximum Disjoint Paths Problem (Full Version)
In Proc. 13th ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 38-47, 2001.
P. Berenbrink, A. Brinkmann, C. Scheideler.
SimLab - A Simulation Environment for Storage Area Networks (Extended Abstract)
In 9th Euromicro Workshop on Parallel and Distributed Processing (PDP), 2000.
A. Brinkmann, K. Salzwedel, C. Scheideler.
Efficient, Distributed Data Placement Strategies for Storage Area Networks (Extended Abstract)
In Proc. 12th ACM Symposium on Parallel Algorithms and Architectures (SPAA), 2000.
A. Czumaj, C. Scheideler.
A New Algorithmic Approach to the General Lovasz Local Lemma with Applications to Schedulung and Satisfiability Problems (Full Version)
In Proc. 32nd ACM Symposium on Theory of Computing (STOC) , pp. 38-47, 2000.
A. Czumaj, C. Scheideler.
Coloring Non-uniform Hypergraphs: A New Algorithmic Approach to the General Lovasz Local Lemma (Full Version)
In Proc. 11th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 30-39, 2000.
P. Berenbrink, A. Brinkmann, C. Scheideler.
Design of the PRESTO Multimedia Storage Network (Extended Abstract)
In International Workshop on Communication and Data Management in Large Networks (CDMLarge), pp. 2-12, 1999.
P. Berenbrink, M. Riedel, C. Scheideler.
Simple Competitive Request Scheduling Strategies (Extended Abstract)
In Proc. 11th ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 33-42, 1999.
C. Scheideler, B. Vöcking.
From Static to Dynamic Routing: Efficient Transformations of Store-and-Forward Protocols (Full Version)
Extended Abstract appeared in: Proc. 31 ACM Symposium on Theory of Computing (STOC), pp. 215-224, 1999.
P. Berenbrink, C. Scheideler.
Locally Efficient On-Line Strategies for Routing Packets along Fixed Paths (Preliminary Version)
In Proc. 10th ACM-SIAM Symposium on Discrete ALgorithms (SODA), pp. 112-121, 1999.
M. Adler, C. Scheideler.
Efficient Communication Strategies for Ad-Hoc Wireless Networks (Full Version)
Extended Abstract appeared in: Proc. 10th ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 259-268, 1998.
U. Feige, C. Scheideler.
Improved Bounds for Acyclic Job Shop Scheduling (Full Version)
Extended abstract appeared in: Proc. 28th ACM Symposium on Theory of Computing (STOC), pp. 624-233, 1998.
M. Flammini, C. Scheideler.
Simple, Efficient Routing Schemes for All-Optical Networks (Full Version)
Extended abstract appeared in: Proc. 9th ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 170-179, 1997.
S. Bock, F. Meyer auf der Heide, C. Scheideler.
Optimal Wormhole Routing in the (n,d)-Torus (Full Version)
In Proc. 11th International Parallel Processing Symposium (IPPS), 1997.
F. Meyer auf der Heide, C. Scheideler.
Communication in Parallel Systems (Full Version)
In 23rd Conference on Current Trends in Theory and Practice of Informatics (SOFSEM) '96, pp. 16-33, 1996.
F. Meyer auf der Heide, C. Scheideler.
Deterministic Routing with Bounded Buffers: Turning Offline into Online Protocols (Full Version)
Extended abstract appeared in: Proc. 37th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 370-379, 1996.
C. Scheideler, B. Vöcking.
Universal Continuous Routing Strategies (Full Version)
Extended abstract appeared in: Proc. 8th ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 142-151, 1996.
R. Cypher, F. Meyer auf der Heide, C. Scheideler, B. Vöcking.
Universal Algorithms for Store-and-Forward and Wormhole Routing (Extended Abstract)
In Proc. 26th ACM Symposium on Theory of Computing (STOC), pp. 356-365, 1996.
F. Meyer auf der Heide, C. Scheideler.
Routing with Bounded Buffers and Hot-Potato Routing in Vertex-Symmetric Networks (Extended Abstract)
In Proc. 3rd European Symposium on Algorithms (ESA), pp. 341-354, 1995.
F. Meyer auf der Heide, C. Scheideler.
Space-Efficient Routing in Vertex-Symmetric Networks (Full Version)
Extended abstract appeared in: Proc. 7th ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 137-146, 1995.
F. Meyer auf der Heide, C. Scheideler, V. Stemann.
Exploiting Storage Redundancy to Speed Up Randomized Shared Memory Simulations (Full Version)
Extended abstract appeared in: Proc. 12th Symposium on Theoretical Aspects of Computer Science (STACS), pp. 267-278, 1995.