Achtung:

Sie haben Javascript deaktiviert!
Sie haben versucht eine Funktion zu nutzen, die nur mit Javascript möglich ist. Um sämtliche Funktionalitäten unserer Internetseite zu nutzen, aktivieren Sie bitte Javascript in Ihrem Browser.

Der Campus im Frühling. Bildinformationen anzeigen

Der Campus im Frühling.

Foto: Universität Paderborn, Kamil Glabica.

Michael Feldmann

Kontakt
Profil
Publikationen
 Michael Feldmann

Theorie verteilter Systeme

Wissenschaftlicher Mitarbeiter

Telefon:
+49 5251 60-6722
Fax:
+49 5251 60-6697
Büro:
F2.403
Besucher:
Fürstenallee 11
33102 Paderborn
Lehre

Als SHK:

  • WS 10/11: Übungen für "Technische Informatik für Ingenieure"
  • WS 11/12: Übungen für "Technische Informatik für Ingenieure"
  • WS 12/13: Übungen für "Grundlagen der Programmierung für Maschinenbauer"
  • WS 13/14: Übungen für "Grundlagen der Programmierung für Maschinenbauer"
  • WS 14/15: Übungen für "Grundlagen der Programmierung für Maschinenbauer"

Als wissenschaftlicher Mitarbeiter:

  • SS 2016: Übungen für "Datenstrukturen und Algorithmen"
  • WS16/17: Übungen für "Grundlagen der Programmierung I"
  • WS17/18: Übungen für "Programmierung"
  • SS 2019: Übungen für "Software Engineering"
  • WS 19/20: Übungen für "Grundlagen der Programmierung für Maschinenbauer" / "Grundlagen der Programmierung für Ingeneure"

Liste im Research Information System öffnen

2020

Survey on Algorithms for Self-Stabilizing Overlay Networks

M. Feldmann, C. Scheideler, S. Schmid, ACM Computing Surveys (2020)

The maintenance of efficient and robust overlay networks is one of the most fundamental and reoccurring themes in networking. This paper presents a survey of state-of-the-art algorithms to design and repair overlay networks in a distributed manner. In particular, we discuss basic algorithmic primitives to preserve connectivity, review algorithms for the fundamental problem of graph linearization, and then survey self-stabilizing algorithms for metric and scalable topologies. We also identify open problems and avenues for future research.


Time- and Space-Optimal Discrete Clock Synchronization in the Beeping Model

M. Feldmann, A. Khazraei, C. Scheideler, in: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), ACM, 2020

We consider the clock synchronization problem in the (discrete) beeping model: Given a network of $n$ nodes with each node having a clock value $\delta(v) \in \{0,\ldots T-1\}$, the goal is to synchronize the clock values of all nodes such that they have the same value in any round. As is standard in clock synchronization, we assume \emph{arbitrary activations} for all nodes, i.e., the nodes start their protocol at an arbitrary round (not limited to $\{0,\ldots,T-1\}$). We give an asymptotically optimal algorithm that runs in $4D + \Bigl\lfloor \frac{D}{\lfloor T/4 \rfloor} \Bigr \rfloor \cdot (T \mod 4) = O(D)$ rounds, where $D$ is the diameter of the network. Once all nodes are in sync, they beep at the same round every $T$ rounds. The algorithm drastically improves on the $O(T D)$-bound of \cite{firefly_sync} (where $T$ is required to be at least $4n$, so the bound is no better than $O(nD)$). Our algorithm is very simple as nodes only have to maintain $3$ bits in addition to the $\lceil \log T \rceil$ bits needed to maintain the clock. Furthermore we investigate the complexity of \emph{self-stabilizing} solutions for the clock synchronization problem: We first show lower bounds of $\Omega(\max\{T,n\})$ rounds on the runtime and $\Omega(\log(\max\{T,n\}))$ bits of memory required for any such protocol. Afterwards we present a protocol that runs in $O(\max\{T,n\})$ rounds using at most $O(\log(\max\{T,n\}))$ bits at each node, which is asymptotically optimal with regards to both, runtime and memory requirements.


2019

A Loosely Self-stabilizing Protocol for Randomized Congestion Control with Logarithmic Memory

M. Feldmann, T. Götte, C. Scheideler, in: Proceedings of the 21st International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), Springer, Cham, 2019, pp. 149-164

We consider congestion control in peer-to-peer distributed systems. The problem can be reduced to the following scenario: Consider a set $V$ of $n$ peers (called \emph{clients} in this paper) that want to send messages to a fixed common peer (called \emph{server} in this paper). We assume that each client $v \in V$ sends a message with probability $p(v) \in [0,1)$ and the server has a capacity of $\sigma \in \mathbb{N}$, i.e., it can recieve at most $\sigma$ messages per round and excess messages are dropped. The server can modify these probabilities when clients send messages. Ideally, we wish to converge to a state with $\sum p(v) = \sigma$ and $p(v) = p(w)$ for all $v,w \in V$. We propose a \emph{loosely} self-stabilizing protocol with a slightly relaxed legitimate state. Our protocol lets the system converge from \emph{any} initial state to a state where $\sum p(v) \in \left[\sigma \pm \epsilon\right]$ and $|p(v)-p(w)| \in O(\frac{1}{n})$. This property is then maintained for $\Omega(n^{\mathfrak{c}})$ rounds in expectation. In particular, the initial client probabilities and server variables are not necessarily well-defined, i.e., they may have arbitrary values. Our protocol uses only $O(W + \log n)$ bits of memory where $W$ is length of node identifiers, making it very lightweight. Finally we state a lower bound on the convergence time an see that our protocol performs asymptotically optimal (up to some polylogarithmic factor).


Skeap & Seap: Scalable Distributed Priority Queues for Constant and Arbitrary Priorities

M. Feldmann, C. Scheideler, in: Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), ACM, 2019, pp. 287--296

We propose two protocols for distributed priority queues (denoted by 'heap' for simplicity in this paper) called SKEAP and SEAP. SKEAP realizes a distributed heap for a constant amount of priorities and SEAP one for an arbitrary amount. Both protocols build on an overlay, which induces an aggregation tree on which heap operations are aggregated in batches, ensuring that our protocols scale even for a high rate of incoming requests. As part of SEAP we provide a novel distributed protocol for the k-selection problem that runs in time O(log n) w.h.p. SKEAP guarantees sequential consistency for its heap operations, while SEAP guarantees serializability. SKEAP and SEAP provide logarithmic runtimes w.h.p. on all their operations. SKEAP and SEAP provide logarithmic runtimes w.h.p. on all their operations with SEAP having to use only O(log n) bit messages.


2018

Self-stabilizing Overlays for high-dimensional Monotonic Searchability

M. Feldmann, C. Kolb, C. Scheideler, in: Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), Springer, Cham, 2018, pp. 16-31

We extend the concept of monotonic searchability~\cite{DBLP:conf/opodis/ScheidelerSS15}~\cite{DBLP:conf/wdag/ScheidelerSS16} for self-stabilizing systems from one to multiple dimensions. A system is self-stabilizing if it can recover to a legitimate state from any initial illegal state. These kind of systems are most often used in distributed applications. Monotonic searchability provides guarantees when searching for nodes while the recovery process is going on. More precisely, if a search request started at some node $u$ succeeds in reaching its destination $v$, then all future search requests from $u$ to $v$ succeed as well. Although there already exists a self-stabilizing protocol for a two-dimensional topology~\cite{DBLP:journals/tcs/JacobRSS12} and an universal approach for monotonic searchability~\cite{DBLP:conf/wdag/ScheidelerSS16}, it is not clear how both of these concepts fit together effectively. The latter concept even comes with some restrictive assumptions on messages, which is not the case for our protocol. We propose a simple novel protocol for a self-stabilizing two-dimensional quadtree that satisfies monotonic searchability. Our protocol can easily be extended to higher dimensions and offers routing in $\mathcal O(\log n)$ hops for any search request.


Self-Stabilizing Supervised Publish-Subscribe Systems

M. Feldmann, C. Kolb, C. Scheideler, T.F. Strothmann, in: Proceedings of the 32nd IEEE International Parallel & Distributed Processing Symposium (IPDPS), IEEE, 2018

In this paper we present two major results: First, we introduce the first self-stabilizing version of a supervised overlay network (as introduced in~\cite{DBLP:conf/ispan/KothapalliS05}) by presenting a self-stabilizing supervised skip ring. Secondly, we show how to use the self-stabilizing supervised skip ring to construct an efficient self-stabilizing publish-subscribe system. That is, in addition to stabilizing the overlay network, every subscriber of a topic will eventually know all of the publications that have been issued so far for that topic. The communication work needed to processes a subscribe or unsubscribe operation is just a constant in a legitimate state, and the communication work of checking whether the system is still in a legitimate state is just a constant on expectation for the supervisor as well as any process in the system.


Skueue: A Scalable and Sequentially Consistent Distributed Queue

M. Feldmann, C. Scheideler, A. Setzer, in: Proceedings of the 32nd IEEE International Parallel & Distributed Processing Symposium (IPDPS), IEEE, 2018

We propose a distributed protocol for a queue, called Skueue, which spreads its data fairly onto multiple processes, avoiding bottlenecks in high throughput scenarios. Skueuecan be used in highly dynamic environments, through the addition of join and leave requests to the standard queue operations enqueue and dequeue. Furthermore Skueue satisfies sequential consistency in the asynchronous message passing model. Scalability is achieved by aggregating multiple requests to a batch, which can then be processed in a distributed fashion without hurting the queue semantics. Operations in Skueue need a logarithmic number of rounds w.h.p. until they are processed, even under a high rate of incoming requests.


2017

A Self-Stabilizing General De Bruijn Graph

M. Feldmann, C. Scheideler, in: Proceedings of the 19th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), Springer, Cham, 2017, pp. 250-264

Searching for other participants is one of the most important operations in a distributed system.We are interested in topologies in which it is possible to route a packet in a fixed number of hops until it arrives at its destination.Given a constant $d$, this paper introduces a new self-stabilizing protocol for the $q$-ary $d$-dimensional de Bruijn graph ($q = \sqrt[d]{n}$) that is able to route any search request in at most $d$ hops w.h.p., while significantly lowering the node degree compared to the clique: We require nodes to have a degree of $\mathcal O(\sqrt[d]{n})$, which is asymptotically optimal for a fixed diameter $d$.The protocol keeps the expected amount of edge redirections per node in $\mathcal O(\sqrt[d]{n})$, when the number of nodes in the system increases by factor $2^d$.The number of messages that are periodically sent out by nodes is constant.


2015

Monotonic Searchability for distributed sorted Lists and De Bruijn Graphs

M. Feldmann, Masterarbeit, Universität Paderborn, 2015


Liste im Research Information System öffnen

Die Universität der Informationsgesellschaft