Selbst­sta­bil­is­i­er­ende Al­gorith­men für Over­lay Net­zwerke

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: