Dr. Christian Scheideler

Assistant Professor

The Johns Hopkins University

Address:

Department of Computer Science
Johns Hopkins University
3400 N. Charles Street
Baltimore, MD 21218-2682
USA

Education:

• July 2000, Habilitation (a German postdoc degree), University of Paderborn, Computer Science
• Dec. 1996, Ph.D., University of Paderborn, Computer Science
• Sep. 1993, M.Sc., University of Paderborn, Computer Science

Current Research Interests:

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

Projects (funded and unfunded):

• PALATIN: A Platform for Interactive Algorithms
• Foundations for Information Gathering in Sensor Networks (funded by NSF)
• Secure Peer-to-Peer Overlay Networks (funded by NSF)
• SPON: Supervized Peer-to-Peer Overlay Networks
• RODYNE: Robust and Adaptive Routing in Dynamic Networks
• PARAID: Adaptive Data Management for Disk Systems
• DFG Special Research Program 376 »Massively Parallel Systems: Algorithms · Design Methods · Applications«
  Project C5: Real-Time Data Server: Scheduling, Routing, Chip Design

Courses:

• 600.344/444: Computer Networks (Spring 2002)
• 600.348/448: Theory of Network Communication (Fall 2002, Fall 2003, Fall 2004)
• 600.371/471: Modern Complexity Theory (Spring 2001, Spring 2003, Spring 2004, Spring 2005)
• 600.384/484: Approximation Algorithms (Fall 2001)
• 600.498: Programming Contest Lab (Spring 2004)
• 600.647: Communication in Parallel Systems (Spring 1999, Fall 2000)
• Evolutionary Algorithms (University of Paderborn, Spring 2000)
• Mini Course on Dynamic Networks (MPI Saarbruecken, Summer 2002)

Seminars:

• 600.771: Seminar in Theory ( Spring 2001, Fall 2001, Spring 2002, Fall 2002, Spring 2003, Fall 2003, Spring 2004, Fall 2004)

Other Activities:

• Club for Theoretical Computer Science (since Fall 2000)
• Distinguished Lecture Series of the Computer Science Department (Fall 2002-Fall 2003)
• Seminar Series of the Department of Computer Science (since Fall 2002)
• Member of the Graduate Admissions Committee of the Computer Science Department (since Spring 2003)
• Member of the Undergraduate Admissions Committee of the Whiting School of Engineering and Krieger School of Arts and Sciences (since Fall 2002)
• Coach of the Johns Hopkins ACM-ICPC (International Collegiate Programming Contest) team (since Spring 2004)

---

Published Books:

• 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.

---

Available Papers:

• M. Miller and C. Scheideler.
  Spheres: A new/old model for distributed computing.
  Unpublished manuscript, Johns Hopkins University, October 2004.
  
  
• 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 2004 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.
  
  

---