Forschungsschwerpunkte
Gegnerische Modelle für drahtlose Kommunikation
Förderungen: DFG-Projekt, 2012-2015
Das zentrale Ziel des beantragten Projekts ist die Erforschung
gegnerischer Modelle für die physikalische Schicht und die Auslotung der
Grenzen beweisbar robuster Medium Access Control (MAC) Protokolle dafür.
Geeignete Modelle zu finden, die einerseits die rigorose Erforschung von
Protokollen erlauben und andererseits nützlich für die Praxis sind,
stellt eine große Herausforderung dar und hat bereits reges
Forschungsinteresse gefunden. Wir werden Modelle erforschen, die
vielversprechend erscheinen, um eine große Bandbreite
physikalischer Phänomene abzudecken, und doch einfach genug sind für die
Theorie.
Verteilte Algorithmen und Datenstrukturen für hochskalierbare Systeme
Förderungen: SFB 901, TP A1 und C1, 2011-2015
Hier beschäftigen wir uns zurzeit mit Methoden, verteilte Algorithmen und Datenstrukturen zu entwickeln, die hochskalierbar sind. Zentrale Forderungen sind dabei, dass die Methoden vollständig dezentral und auch in dynamischen Systemen anwendbar sind, d.h. diese in der Lage sein müssen, sich an Systemveränderungen mit geringem Aufwand anzupassen. Weiterhin wollen wir einen hohen Wert auf die Robustheit der Methoden legen, d.h. diese können aus einem beliebigen illegalen Zustand heraus wieder einen legalen Zustand für den entsprechenden Algorithmus oder die entsprechende Datenstruktur erreichen, selbst wenn sich Teile des Systems während der Erholung fehlerhaft oder gegnerisch verhalten sollten.
Selbststabilisierende Algorithmen für Overlay Netzwerke
Förderungen: DFG-Projekt, 2008-2011
Hier beschäftigen wir uns mit selbststabilisierenden Overlay-Netzwerken, d.h. anwendungsorientierten Netzwerken, die sich aus jeder Situation, in dem schwacher Zusammenhang gewährleistet ist, wieder in einen legalen Zustand zurückversetzen können. Dieses soll ohne zentrale Kontrolle, d.h. rein durch lokale Interaktionen seiner Teilnehmer geschehen.
Aktuelle Forschungsberichte:
- A. Richa, C. Scheideler and P. Stevens. Self-stabilizing De Bruijn Networks. In 13th Intl. Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), 2011.
- R. Nor, M. Nesterenko and C. Scheideler. Corona: A Stabilizing Deterministic Message-Passing Skip List. In Proc. of the 13th Intl. Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), 2011.
- S. Kniesburges, A. Koutsopoulos and C. Scheideler.
Re-Chord: a self-stabilizing chord overlay network.
In 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2011. - D. Gall, R. Jacob, A. Richa, C. Scheideler, S. Schmid and H. Täubig.
Time complexity of distributed topological self-stabilization: The case of graph linearization.
In 9th Latin American Symposium on Theoretical Informatics (LATIN), 2010. - R. Jacob, S. Ritscher, C. Scheideler and S. Schmid.
A self-stabilizing local Delaunay graph construction.
In 20th Intl. Symp. on Algorithms and Computation (ISAAC), 2009. - R. Jacob, A. Richa, C. Scheideler, S. Schmid and Hanjo Täubig.
A distributed polylograithmic time algorithm for self-stabilizin skip graphs.
In 28th ACM Symp. on Principles of Distributed Computing (PODC), 2009. - T. Clouser, M. Nesterenko and C. Scheideler.
Tiara: A self-stabilizing skip list.
In 10th Intl. Symp. on Stabilization, Safety and Security of Distributed Systems (SSS), 2008. - M. Onus, A. Richa and C. Scheideler.
Linearization: Locally self-stabilizing sorting in graphs.
In Workshop on Algorithm Engineering and Experiments (ALENEX), 2007.
Kommunikation in Sensor-Netzwerken und mobilen ad-hoc Netzen
Förderungen: NSF-Projekt, 2003-2006
Wir beschäftigen uns hier mit Kommunikationsprotokollen für den effizienten und robusten Austausch und das Sammeln von Informationen in Sensor-Netzwerken und mobilen ad-hoc Netzen.
Aktuelle Forschungsberichte:
- A. Richa, C. Scheidleer, S. Schmid and J. Zhang.
A jamming-resistant MAC protocol for multi-hop wireless networks.
In 24th Intl. Symp. on Distributed Computing (DISC), 2010. - B. Awerbuch, A. Richa and C. Scheideler.
A jamming-resistant MAC protocol for single-hop wireless networks.
In 27th ACM Symp. 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 9th ACM Symp. on Mobile Ad Hoc Networking and Computing (MobiHoc), 2008.
Organisierte Workshops:
- Bertinoro Workshop on Wireless and Sensor Networks, Italien, 2007
- Bertinoro Workshop on Wireless and Sensor Networks, Italien, 2009
Sichere Peer-to-Peer Systeme
Förderungen: NSF-Projekt, 2003-2006
In diesem Projekt geht es darum, Overlay-Netzwerke zu finden, die robust gegenüber verschiedenen Attacken sind, angefangen von zufälligen und gegnerischen Ausfällen bis hin zu Join-Leave-Attacken, Sybil-Attacken und DoS-Attacken.
Aktuelle Forschungsberichte:
- C. Scheideler and S. Schmid.
A distributed and oblivious heap.
In 36th Intl. Colloquium on Automata, Languages and Programming (ICALP), 2009. - B. Awerbuch and C. Scheideler.
Towards scalable and robust overlay networks.
In 6th Intl. Workshop on Peer-to-Peer Systems (IPTPS), 2007. - B. Awerbuch and C. Scheideler.
Robust random number generation for peer-to-peer systems.
In 10th Intl. Conf. on Principles of Distributed Systems (OPODIS), 2006. - B. Awerbuch and C. Scheideler.
Towards a scalable and robust DHT.
In 18th ACM Symp. on Parallelism in Algorithms and Architectures (SPAA), 2006. - C. Scheideler.
How to spread adversarial nodes? Rotate!
In 37th ACM Symp. on Theory of Computing (STOC), 2005. - B. Awerbuch and C. Scheideler.
Group Spreading: A protocol for provably secure distributed name service.
In 31st Itl. Colloquium on Automata, Languages and Programming (ICALP), 2004. - B. Awerbuch and C. Scheideler.
Robust distributed name service.
In 3rd Intl. Workshop on Peer-to-Peer Systems (IPTPS), 2004.
Zentral verwaltete Peer-to-Peer Systeme
Förderungen: Interne Mittel der Johns Hopkins University, 2003-2005
Hier geht es uns darum, skaliserbare und sichere Peer-to-Peer Systeme zu entwickeln, die auf einem vertrauenswürdigen Anker beruhen, d.h., einem Server, über den alle Join-Anfragen gehen müssen und der sich um die Verwaltung der Netzwerktopologie kümmert, aber alle anderen Funktionalitäten den Peers überlässt. Solche Systeme sind zwischen reinen Peer-to-Peer Systemen und serverbasierten Systemen angesiedelt.
Forschungsberichte:
- K. Kothapalli and C. Scheideler.
Supervised peer-to-peer systems.
In Proc. Intl. Symp. on Parallel Architectures, Algorithms and Networks (I-SPAN), 2005. - C. Riley and C. Scheideler.
A distributed hash table for computational grids.
In IEEE Intl. Parallel and Distributed Processing Symposium (IPDPS), 2004. - C. Riley and C. Scheideler.
Guaranteed broadcasting using SPON: Supervised P2P overlay network.
In 2004 Intl. Zurich Seminar on Communications.
Verteilte Informationssysteme
Förderungen: Teilprojekt C5 des SFB 376. 1995-2000
Hier beschäftigen wir uns mit fairen, adaptiven und robusten Informationssystemen. Den Anfang bildeten Speichersysteme mit beliebig heterogenen Speichern, die im Rahmen des SFB 376 in Paderborn untersucht wurden und später unter der Regie von Dr. Andre Brinkmann bis zur kommerziellen Reife weiterentwickelt wurden. Neuere Forschungen beschäftigen sich mit Informationssystemen, die robust gegenüber Sybil- und Denial-of-Service Attacken sind.
Aktuelle Forschungsberichte:
- M. Baumgart, C. Scheideler, and S. Schmid.
A DoS-resilient information system for dynamic data management.
In 21st ACM Symp. on Parallelism in Algorithms and Architectures (SPAA), 2009. - M. Mense and C. Scheideler.
SPREAD: An adaptive scheme for redundant and fair storage in dynamic heterogeneous storage systems.
In 19th ACM-SIAM Symp. on Discrete Algorithms (SODA), 2008. - B. Awerbuch and C. Scheideler.
A denial-of-service resistant DHT.
In 21st Intl. Symp. on Distributed Computing (DISC), 2007. - B. Awerbuch and C. Scheideler.
Consistent ad compact data management in distributed storage systems.
In 16th ACM Symp. on Parallelism in Algorithms and Architectures (SPAA), 2004.
Subjects: Ein Paradigma für sichere verteilte Systeme
Das ist unsere neueste Forschungsrichtung. Es geht darum, ein Paradigma zu entwickeln, das es uns erlaubt, beweisbar effiziente, sichere und robuste Anwendungen für Probleme zu entwickeln, für die es bis heute keine vernünftigen Lösungen gibt, wie SPAM, Identity Theft, Digital Rights Management, Denial-of-Service Attacken, Viren etc.