Closed Projects

Förderung: DFG-Projekt (2018 - 2022)

Beteiligte Partner:
Prof. Dr. Christian Scheideler, Universität Paderborn, Deutschland
Prof. Shlomi Dolev, Ben Gurion University of the Negev, Israel

Ziel dieses Projekts ist die Entwicklung von neuen Modellen und Algorithmen für Schwärme eigenständiger Nano-Roboter, d.h. Gruppen winziger aktiver Einheiten mit stark eingeschränkten individuellen Fähigkeiten, die als Schwarm in physiologischen Umgebungen operieren.

Bei der Entwicklung neuer Modelle werden Fragestellungen berücksichtigt, die in der Vergangenheit nicht oder nur unvollständig betrachtet wurden: Wie können die Nano-Roboter Energie gewinnen, speichern und nutzen (Energiemanagent)? Welche realistischen Modelle (angelehnt an physikalische, biologische oder chemische Prozesse in der Natur) können eine nicht-lokale Kommunikation zwischen einer Gruppe von Nano-Robotern ermöglichen ? Welche Modelle erlauben den Ausfall und die Reparatur fehlerhafter Nano-Roboter durch intakte Nano-Roboter (Fehlertoleranz)?

Algorithmisch ist das Leader-Election Problem ein Schlüsselproblem, dessen Lösung die Lösung anderer wichtiger Probleme durch einen Schwarm von Nano-Robotern erst möglich macht. Die im Projekt entwickelten Modelle werden hinschtlich ihrer Fähigkeiten untersucht, das Leader-Election Problem effizient zu lösen. Aufbauend darauf werden Lösungen für weitere wichtige Aufgabenstellungen entwickelt: Ein Schwarm Nano-Roboter soll eine Umgebung vollständig durchsuchen und ggf. wichtige Positionen in der Umgebung markieren (Exploration). Ein Schwarm Nano-Roboter soll ein Objekt in seiner direkten Umgebung schnellstmöglich umhüllen (Umhüllung). Ein Schwarm Nano-Roboter soll einen Weg von einem Startpunkt zu einem Zielpunkt seiner Umgebung formen (Transport).

Für alle entwickelte Modelle werden durch untere Schranken (und ggf. Unmöglichkeitsresultate) die Grenzen der jeweiligen Modelle aufgezeigt.

Die algorithmischen Ergebnisse werden dann erweitert, um Aspekte wie Robustheit gegenüber Ausfällen von Nano-Robotern und Schwärmen mit unterschiedlichen Nano-Robotern sowie die Lösung obiger Probleme in dreidimensionalen Umgebungen zu untersuchen.

Förderung: DFG-Projekt, 2014-2017

Ziel des Projekts ist es, verteilte Algorithmen für zentrale Probleme im Bereich der selbstorganisierenden Partikelsysteme zu entwickeln und zu analysieren. Konkrete Probleme, auf die wir uns konzentrieren werden, sind das 'Smart-Paint Problem', das 'Shape Formation Problem' und 'Bridging und Covering Probleme'. Beim 'Smart-Paint-Problem geht es darum, die Oberfläche eines 2D- oder 3D-Objects mit einer Partikelstruktur zu überdecken, beim 'Shape Formation Problem' geht es darum, das Partikelsystem in eine gewünschte Form zu bringen, und bei den 'Bridging und Covering Problemen' geht es darum, Lücken in Strukturen mithilfe von Partikeln zu überbrücken oder auszufüllen.

Hier gelangen Sie zur Projekt-Webseite.

Funded by: NSF-Projekt, 2003-2006

In this project, the aim is to develop algorithms for peer-to-peer systems that are provably robust against various attacks, including random and adversarial faults as well as join-leave attacks, Sybil attacks and DoS attacks.

Recent publications:

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

Research Goals:

We are living in the information age. Interactive systems and platforms like social networks and peer-to-peer networks are flourishing and offer unprecedented possibilities to exchange and disseminate information. In order to do that effectively, suitable connections are formed across the Internet which form a so-called overlay network. Interactive systems that are in principle open to anyone can be highly dynamic and vulnerable to adversarial attacks. In order to ensure a high stability, we are currently investigating algorithms that allow an overlay network to recover its topology from any weakly connected state. Ideally, that should be possible by just using local interactions between the nodes in which a node may decide to introduce two of its neighbors to each other or to cut a connection to one of its neighbors. The main problems that we are investigating in this context are:

  • Which network topologies allow local-control self-stabilization mechanisms,
  • can mechanisms be designed to involve only a small amount of work and time per node in order to reach a desired topology from any weakly connected state, and
  • can self-stabilization be achieved even under a dynamically changing set of nodes or adversarial behavior of some of them?

Publications:

  • 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, H. Täubig: Time Complexity of Distributed Topological Self-stabilization: The Case of Graph Linearization. In the 9th Latin American Theoretical Informatics Symposium (LATIN), 2010.
  • R. Jacob, S. Ritscher, C. Scheideler and S. Schmid. A self-stabilizing local Delaunay graph construction. In the 20th Intl. Symp. on Algorithms and Computation (ISAAC), 2009.
  • R. Jacob, A. Richa, C. Scheideler, S. Schmid and H. Täubig. A distributed polylogarithmic time algorithm for self-stabilizing skip graphs. In the 28th ACM Symp. on Principles of Distributed Computing (PODC), 2009.
  • T. Clouser, M. Nesterenko and C. Scheideler. Tiara: A self-stabilizing deterministic skip list. In the 10th International Symposium 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 the Workshop on Algorithm Engineering and Experiments (ALENEX), 2007.

Participants:

Former Participants:

Collaborating researchers:

Supported by: NSF-Projekt, 2003-2006

Here, we are dealing with communication protocols for the efficient and robust exchange and gathering of information in sensor networks and mobile ad-hoc networks.

Recent publications:

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

Organized Workshops:

  • Bertinoro Workshop on Wireless and Sensor Networks, Italien, 2007
  • Bertinoro Workshop on Wireless and Sensor Networks, Italien, 2009

 

Supported by: Internal funds of the Johns Hopkins University, 2003-2005

Here, the goal is to develop scalable and robust peer-to-peer systems that are based on a reliable anchor. That is, a server is handling all join requests and maintaining the network topology, but all other functions are handled by the peers. Such systems can be seen as being between pure peer-to-peer systems and server-based systems.

Publications:

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

 

Supported by: Project C5 of the SFB 376. 1995-2000

In this area, our goal is to design adaptive and robust information systems. Within the SFB project, our research focused on storage systems that can handle storage devices of arbitrary capacities. Our results were later turned by Dr. Andre Brinkmann into a system of commercial strength. Newer research results focus on information systems that are robust against Sybil and DoS attacks.

Recent publications:

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

Supported by: DFG-Project, 2012-2015

The main goal of the proposed research is to investigate adversarial models for the physical layer and to explore the limits of designing provably robust medium access control (MAC) protocols for them. Finding suitable models that on one hand allow the rigorous design and analysis of protocols and on the other hand are useful in practice is a major challenge that has received significant attention in the research community. We will investigate models for wireless communication that promise to cover a wide range of physical layer phenomena and that are yet simple enough so that they are useful in theory.

Förderung: DFG-Projekt (2018 - 2022)

Beteiligte Partner:
Prof. Dr. Christian Scheideler, Universität Paderborn, Deutschland
Prof. Shlomi Dolev, Ben Gurion University of the Negev, Israel

Ziel dieses Projekts ist die Entwicklung von neuen Modellen und Algorithmen für Schwärme eigenständiger Nano-Roboter, d.h. Gruppen winziger aktiver Einheiten mit stark eingeschränkten individuellen Fähigkeiten, die als Schwarm in physiologischen Umgebungen operieren.

Bei der Entwicklung neuer Modelle werden Fragestellungen berücksichtigt, die in der Vergangenheit nicht oder nur unvollständig betrachtet wurden: Wie können die Nano-Roboter Energie gewinnen, speichern und nutzen (Energiemanagent)? Welche realistischen Modelle (angelehnt an physikalische, biologische oder chemische Prozesse in der Natur) können eine nicht-lokale Kommunikation zwischen einer Gruppe von Nano-Robotern ermöglichen ? Welche Modelle erlauben den Ausfall und die Reparatur fehlerhafter Nano-Roboter durch intakte Nano-Roboter (Fehlertoleranz)?

Algorithmisch ist das Leader-Election Problem ein Schlüsselproblem, dessen Lösung die Lösung anderer wichtiger Probleme durch einen Schwarm von Nano-Robotern erst möglich macht. Die im Projekt entwickelten Modelle werden hinschtlich ihrer Fähigkeiten untersucht, das Leader-Election Problem effizient zu lösen. Aufbauend darauf werden Lösungen für weitere wichtige Aufgabenstellungen entwickelt: Ein Schwarm Nano-Roboter soll eine Umgebung vollständig durchsuchen und ggf. wichtige Positionen in der Umgung markieren (Exploration). Ein Schwarm Nano-Roboter soll ein Objekt in seiner direkten Umgebung schnellstmöglich umhüllen (Umhüllung). Ein Schwarm Nano-Roboter soll einen Weg von einem Startpunkt zu einem Zielpunkt seiner Umgebung formen (Transport).

Für alle entwickelte Modelle werden durch untere Schranken (und ggf. Unmöglichkeitsresultate) die Grenzen der jeweiligen Modelle aufgezeigt.

Die algorithmischen Ergebnisse werden dann erweitert, um Aspekte wie Robustheit gegenüber Ausfällen von Nano-Robotern und Schwärmen mit unterschiedlichen Nano-Robotern sowie die Lösung obiger Probleme in dreidimensionalen Umgebungen zu untersuchen.

Further information: