OverHyPeD Project Group

Building an Overlay Hybrid Peer-2-Peer Distributed Simulator

 

Supervisors

Thorsten Götte, Kristian Hinnenthal, and Prof. Dr. Christian Scheideler

Motivation

This PG is about algorithms and simulations for Hybrid Communication Networks (HCN).
In an HCN each node has several modes of communication with different limitations and capabilities.
Even our normal human interaction uses hybrid communication as we use spoken as well as body language to convey different kinds of information to each other.
For a more technological example, consider a smartphone: On the one hand it can use the cellular network to access the internet. In this mode, we can contach any device which is also connected to the internet, but the communication is limited by the data plan.
On the other hand, the phone can use its local interfaces, e.g., bluetooth, to communicate with nearby devices. Here, the communication is limited to nodes in transmission range, but we are not bound to a data plan and may send arbitrarily large files.

Inspired by this, we will consider a more theoretical model in which each node has the following two modes of communication:

  • The Ad-Hoc Mode: Each node has coordinates (x,y) and can communicate with all nodes within radius 1. In particular, each node can send O(n) bits to each node in its transmission range.
  • The Overlay Mode: Each node has a unique and immutable ID. A node can send messages to all nodes whose ID it knows. Here, we can construct arbitrary topologies by passing around the IDs and are not bound to transmission ranges. However, this mode has a capacitated data rate as each node can only receive O(log n) bits per round.

The goals of this PG are twofold: First, we want to implement a simulator that can simulate distributed algorithms on HCNs consisting of hundreds of thousands of nodes. Second, we want to develop algorithmic solutions for interesting problems and evaluate them using the simulator.

Technology Stack

The simulator will be written in a language/framework that supports a high number of concurrent processes, e.g., Elxir, Go, or Akka. Furthermore, we need a GUI/Visualization. This can be written in a language/framework of your choice. However, we strongly encourage a web-based implementation based on Angular or React. For the visualization of the network we may use GraphStream or sigma.js.


Algorithmic Problems

Here are some examples for algorithmic problems which may be solved in this PG:

  •  Smallest Enclosing Circle. Given a set of nodes and their coordinates find the smallest circle that contains all these nodes.
  •  Minimum Spanning Tree. Given a set of nodes and their coordinates find a set of edges that connects all nodes and minimizes the sum of the distances.


Further Material

Prerequisites

At least one of the following three things should apply to you:

  1. You have strong interest (or even experience) in theoretical problems and the design/analysis of distributed algorithms.
  2. You have strong interest (or even experience) in progamming high concurrency frameworks/languages.
  3. You have strong interest (or even experience) in designing and implementing web-based UIs that display dynamic data.

Contact

If you have any question send an email to Thorsten Götte (thgoette@mail.upb.de).

Sie interessieren sich für: