Vor WS 2023/24

2022


Lukas Hintze
November 25, 2022, G-210 and via Zoom: https://uni-hamburg.zoom.us/j/94889228942?pwd=VTY5d3Y1NjJqbEdoaEpxc3pOM3RoZz09

Title: Geometric Bounds on the Fastest Mixing Markov Chain
John Sylveste
November 4, 2022

Title: Choice and Bias in Random Walks

Anna Geisler, Universität Hamburg
October 21, 2022, 14:00

Previous Talks

Title: Tba.

Marten Maack, Universität Paderborn
July 15, 2022, 14:00

Title: Tba.

Christopher Hahn, Universität Hamburg
July 8, 2022, 14:00

Title: Tba.

Malin Rau, Universität Hamburg
June 24, 2022, 14:00

Title: Tba.

Mahsa Eftekhari, University of California, Davis
June 17, 2022, 17:00

Title: Dynamic size counting in population protocols

John Sylvester, University of Glasgow
June 10, 2022, 14:00

Title: Balanced allocations: Caching and Packing, Twinning and Thinning.

Felix Biermeier, University of Hamburg
June 3, 2022, 14:00

Hamed Hosseinpour, University of Hamburg
May 13, 2022, 14:00

2021


Daniel Moldt, University of Hamburg
January 21, 2021, 16:00

Christoph Damerius, University of Hamburg
January 14, 2021, 16:00

David Mosteller, University of Hamburg
January 7, 2021, 16:00

Mohit Garg, Universität Bremen
December 17, 2021, 16:00

Harald Räcke, Technische Universität München
December 10, 2021, 16:00

Florian Schneider, University of Hamburg
December 10, 2021, 16:00

Malin Rau, University of Hamburg
December 3, 2021, 16:00

Hamed Hosseinpour, University of Hamburg
November 19, 2021, 16:30

Dominik Kaaser, University of Hamburg
November 19, 2021, 16:00

Christopher Hahn, University of Hamburg
October 29, 2021, 16:00, zoom:  https://uni-hamburg.zoom.us/j/94889228942

Title: Approximate Majority Using Chemical Reaction Networks

In this talk I will present the work of A. Condon, M. Hajiaghayi, D. Kirkpatrick and Ján Maňuch from Natural Computing, 2019. Chemical Reaction Networks (CRNs) are a model for real-world chemical reactions, for example in DNA computing, and closely related to Population Protocols (PPs). The paper presents four closely related CRNs that solve approximate majority for an initial additive bias of $O(\sqrt{n \log n})$ in several settings. The focus of this presentation is the proof for the tri-molecular CRN "Tri" in the original setting, in the multi-species setting and when the reactions are triggered by a broadcast. The latter is of particular interest, since the needed additive bias remains $O(\sqrt{n \log n})$ - an improvement over $O(n^{3/4})$ for bi-molecular CRNs/PPs..

Felix Biermeier, University of Hamburg
October 22, 2021, 16:00, zoom:  https://uni-hamburg.zoom.us/j/94889228942

Title: Approximate Majority With Catalytic Inputs

In this talk I will present the work of T. Amir, J. Aspnes and J. Lazarsfeld from OPODIS 2020. Population protocols [AAD+06] are a class of algorithms for modeling distributed computation in networks of finite-state agents communicating through pairwise interactions. Their suitability for analyzing numerous chemical processes has motivated the adaptation of the original population protocol framework to better model these chemical systems. In this paper, we further the study of two such adaptations in the context of solving approximate majority: persistent-state agents (or catalysts) and spontaneous state changes (or leaks). Based on models considered in recent protocols for populations with persistent-state agents [DK18,ADK+17,ATU20], we assume a population with n catalytic input agents and m worker agents, and the goal of the worker agents is to compute some predicate over the states of the catalytic inputs. We call this model the Catalytic Input (CI) model. For m = $\Theta(n)$, we show that computing the parity of the input population with high probability requires at least $\Omega(n^2)$ total interactions, demonstrating a strong separation between the CI model and the standard population protocol model. On the other hand, we show that the simple third-state dynamics [AAE08, PVV09] for approximate majority in the standard model can be naturally adapted to the CI model: we present such a constant-state protocol for the CI model that solves approximate majority in O(n log n) total steps with high probability when the input margin is $\Omega(\sqrt{n\log n}). We then show the robustness of third-state dynamics protocols to the transient leaks events introduced by [ADK+17,ATU20]. In both the original and CI models, these protocols successfully compute approximate majority with high probability in the presence of leaks occurring at each step with probability $\beta \leq O(\sqrt{n\log n}/n)$. The resilience of these dynamics to leaks exhibits similarities to previous work involving Byzantine agents, and we define and prove a notion of equivalence between the two.

David Mosteller, University of Hamburg
Febuary 26, 2021

Title: Model Checking of Synchronized Domain-Specific Multi-Formalism Models

Complex systems require the use of different models that are linked with each other. Developers are naturally interested to show that their systems work. Domain practitioners, who work with domain-specific models, want to verify that their created models perform as desired. Correctness statements about the behavior of models are only possible if they have a clear semantics. Support is required for creating the semantics and also for checking properties of the model. With the Rmt approach, we make operational semantics usable for the domain-specific modeling languages (DSML) that are understandable to domain experts. High-level Petri nets as a target language of our transformational approach can be analyzed by the MoMoC CTL model checking tool. In this contribution MoMoC is extended and integrated with the RMT approach so that the results of verification based on the defined operational semantics can be applied to DSML. The presented approach does not work equally well for all languages. However, it is well suited for languages with discrete states that can be uniquely named. Provided that they map well to Petri nets, questions about (reachable) states of multiple linked domain-specific models can be answered.

Matin Urdu, University of Hamburg
January 29, 2021, 12:15, zoom: https://uni-hamburg.zoom.us/j/94889228942?pwd=VTY5d3Y1NjJqbEdoaEpxc3pOM3RoZz09

Title: Scheduling to minimize Calibrations

The calibration minimization problem is an offline scheduling problem introduced by Bender et al. In this scheduling problem machines can only process jobs in intervals they have been calibrated for. The goal is to process every job and minimize the number of calibrations. This problem has applications from manufacturing to cloud computing and many more areas. It is currently not known whether a polynomial algorithm exists that solves the calibration minimization problem. This talk will briefly review the state-of-art, present various dynamic programming approaches that compute the optimal solution, and finish with a discussion on the practicability of the different approaches.

Florian Schneider, University of Hamburg
January 22, 2021, 11:00

Titel: Improved coerage in Lower-Left-Anchored Rectangle Packing

In the Lower-Left-Anchored Rectangle Packing (LLARP) Problem, we are given points P in the unit square U. We are asked to find non-overlapping rectangles of maximum total size whichs lower left corners are the points P. Five decades ago, Allen Freedman conjectured that at least 50% of the unit square can be covered, which remains open up to this day. Dumitrescu et al. has shown that ~9.1% of U can be covered by those squares, which was improved by Nicolaus Möller to ~9.6%. Our work is dedicated to a novel charging scheme that significantly improves this coverage to ~39%. Furthermore, it was conjectured that Dumitrescu's TilePacking algorithm already achieves the desired 50% coverage. We refute this by showing an upper bound of ~43%.

2020


Hamed Hosseinpour, University of Hamburg
November 27, 2020, 14:00, zoom:  https://uni-hamburg.zoom.us/j/94889228942

Title: Analysis of several known protocols for solving Consensus Problems

Consensus problem is defined as follow: We are given a graph $G(V,E)$. Each agent (node) has initially an opinion out of [k] possible opinions such that $k\leq n$. The goal is to design a simple randomised protocol which is fast enough and changes the opinions of (some) agents in each step. We are certain to show that utilising this protocol leads the system to reach a state in which all agents share the same opinion. As the most interesting protocols we are about to compare VOTER, 2-choices, 3-majority and Undecided dynamics protocols. Moreover, we show undecided dynamic protocol will solve consensus problem way faster than others i.e., it runs in poly-log time in |V|. This, also, answer an open question proposed by Becchetti et al. [Distributed computing 2017].

Felix Biermeier, Univrsity of Hamburg
November, 27, 2020, 13:00, zoom: https://uni-hamburg.zoom.us/j/94889228942

Title: Time and Space Optimal Exact Majority Population Protocols

In this talk I will present the following paper of Gasieniec, Stachowiak and Uznanski about exact majority in population protocols. In this paper they study population protocols governed by the random scheduler, which uniformly at random selects pairwise interactions between n agents. The main result of this paper is the first time and space optimal exact majority population protocol which also works with high probability. The new protocol operates in the optimal parallel time O(log n), which is equivalent to O(n log n) sequential pairwise interactions, where each agent utilises the optimal number of O(log n) states. The time optimality of the new majority protocol is possible thanks to the novel concept of fixed-resolution phase clocks introduced and analysed in this paper. The new phase clock allows to count approximately constant parallel time in population protocols.

Henry Engelhardt, University of Hamburg
September 25, 2020, 10:00, zoom: https://uni-hamburg.zoom.us/j/92331910821?pwd=S1JidzJab0NxNjg4RXQ3S2dwSkJjdz09

Um die Korrektheit von komplexen Systemen zu verifizieren, können Model-Checking Algorithmen angewandt werden, die eine Abstraktion des Systems modellieren und überprüfen können. Das Werkzeug Renew ermöglicht die Modellierung durch Petrinetzformalismen. Die Analyse von Petrinetzen, kann aufgrund ihrer potentiell großen Zustandsräume, sehr rechenintensiv werden. Für die Berechnung derartiger Problemen eignet es sich, die Berechnung auf mehrere Rechner zu verteilen. In dieser Arbeit wird die Container-basierte Ausführung von Petrinetzalgorithmen untersucht, um die Berechnung einer Menge an Petrinetzalgorithmen an Container-basierte Ausführungsumgebungen zu verteilen und die Ergebnisse wieder zusammenzuführen. Dafür wird im Laufe dieser Arbeit das Plugin DistributedAnalysis in Renew entworfen und implementiert, das auf den Plugins RenewKube und Distribute aufbaut, die zusammen eine verteilte Simulation von Renew ermöglichen. DistributedAnalysis bindet die Model-Checking Algorithmen des Plugins Mo-MoC ein und wurde entworfen, um durch weitere Analyse-Werkzeuge erweiterbar zu sein. Über DistributedAnalysis können Analyseanfragen lokal erstellt werden, welche automatisch an Rechner in einem Cluster gesendet werden, die das Ergebnis
berechnen und zurück liefern.

Leon Kraft, University of Hamburg
September 25, 2020, 12:00, zoom: https://uni-hamburg.zoom.us/j/92331910821?pwd=S1JidzJab0NxNjg4RXQ3S2dwSkJjdz09

"Issue-Tracking-Systeme wie Redmine oder Jira sind heutzutage in den allermeisten Projekten kaum noch wegzudenken. Digital und damit jederzeit von überall sofort abrufbar, visualisieren sie die Aufgaben jedes Beteiligten in einer vorher noch nie da gewesenen Anschaulichkeit. Doch immer öfter finden sich Nutzer in gleich mehreren Anwendungen wieder. Als Mitglied von etlichen unterschiedlichen Projekten, verwenden diese nämlich häufig parallel noch weitere Werkzeuge. In der Folge sind relevante Informationen über die ihnen zugewiesenen Arbeiten auf mehrere Systeme verteilt und müssen mühselig zusammengesucht werden.

Vor diesem Hintergrund beschäftigt sich diese Bachelorarbeit mit der Entwicklung einer iOS-basierten Applikation, welche an die Schnittstellen von verschiedenen bereits existierenden Issue-Tracking-Systemen andockt und alle für eine bestimmte Person wesentlichen Tickets in einer einheitlichen Sicht zusammenträgt.

Da jede Schnittstelle anders funktioniert, muss für jedes Issue-Tracking-System eine maßgeschneiderte Unterstützung bereitgestellt werden. Ziel dieser Arbeit ist es, die Applikation intern so zu gestalten, dass solch eine Erweiterung jeweils mit einem minimalen Aufwand erfolgen kann. Insbesondere wird dabei der Frage nachgegangen, wo genau die Grenzen einer derart adaptiven Gestaltung im Kontext der Vereinheitlichung liegen und wie viel Mühe für das Hinzufügen von neuen Issue-Tracking-Systemen durch eine ausgeklügelte Architektur maximal eingespart werden kann."

Louis Kobras, University of Hamburg
September 25, 2020, 2:15, zoom: https://uni-hamburg.zoom.us/j/92331910821?pwd=S1JidzJab0NxNjg4RXQ3S2dwSkJjdz09

Titel: Darstellung der Orientierungseinheit Informatik an der Universität Hamburg mithilfe des PAOSE-Ansatzes und Workflownetzen

Die Orientierungseinheit Informatik am Fachbereich Informatik der Universität Hamburg ist ein komplexes, stark vernetztes System aus vielen autonomen Agenten, welches in jährlicher Iteration die Einführungsphase für Studienanfänger*innen organisiert. Ziel dieser Arbeit ist es, die Organisationsstruktur und Arbeitsweise der Orientierungseinheit mithilfe des PAOSE-Ansatzes zu erfassen und zu modellieren, um mithilfe der visuellen Zugänglichkeit von Petrinetz-Komponenten und UML-Grafiken eine zugängliche Dokumentation zur Struktur eines Ausschnittes der Orientierungseinheit zu bieten. Nach Darlegung der dafür relevanten Grundlagen inklusive einem kurzen Überblick über den PAOSE-Ansatz folgt die Arbeit den Phasen von PAOSE, um die gewünschten Modelle zu erstellen. Um die Arbeitsweise festzuhalten, wird sich der Workflow-Semantik von Petrinetzen bedient.

Kuan Yang, University of Hamburg
Sepember 18, 2020, 2:15, zoom https://uni-hamburg.zoom.us/j/98805641476?pwd=MFZiVjBIT0tJbEJnWlhIN2hrclhoUT09

Title: Counting Solutions to Random CNF Formulas

Abstract:
We give the first efficient algorithm to approximately count the number of solutions in the random k-SAT model when the density of the formula scales exponentially with k. The best previous counting algorithm was due to Montanari and Shah and was based on the correlation decay method, which works up to densities $2(1+o_k(1))\log k/k$, the Gibbs uniqueness threshold for the model. Instead, our algorithm harnesses a recent technique by Moitra to work for random formulas. The main challenge in our setting is to account for the presence of high-degree variables whose marginal distributions are hard to control and which cause significant correlations within the formula.

Michael A. Bender, Stony Brook University
August 07, 2020 , 2:15, zoom:  https://uni-hamburg.zoom.us/j/96435714449?pwd=dno2WWVzMnhTSUlFeS9YU3gweUJFQT09

Title: Contention Resolution without Collision Detection

In this talk we revisit the classical problem of randomized exponential backoff on a multiple-access channel. We show how to achieve constant throughput even when the players cannot detect collisions, i.e, simultaneous transmissions, on the channel.

Joint work with Tsvi Kopelowitz, William Kuszmaul, and Seth Pettie.

Hauke Reddmann, University of Hamburg
July 31, 2020, 2:15, zoom: https://uni-hamburg.zoom.us/j/91963935612?pwd=V0ZlNWxSeU5ZbHhoUzNCY2FPLzZpQT09

Title: On the Geometric Equivalent of Instance Optimal Binary Search Tree Algorithms 

Binary search trees (BSTs) are a venerable data structure for finding some element in a collection. While they do this in $O(\log n)$ time which can be proven optimal by information theory, practical considerations (especially the allowance of insert/delete operations) were the driving force for developing several dynamic BSTs that reorganize themselves while serving a query series.

This gave rise to the question of instance optimality: Can a series of $m$ consecutive queries be served faster than $O(m \cdot \log n)$? More precisely, is there an algorithm that can serve all possible query series with a mere $O(1)$ overhead factor, with respect to the optimal algorithm (which knows the instance beforehand and may take as low as $O(m)$, depending on the instance)? This property is known as $\gamma$-competetiveness in the framework of Competitive Analysis.

Splay trees are a variant of dynamic BSTs that rotate any current query to the root by three simple rules, depending on which side(s) of the BST the query is located at the moment. Since decades, the Sleator-Tarjan conjecture, which asserts that splay trees are instance optimal, is still open. Since a few years it is also known that the problem of instance optimality for BSTs may be rephrased: It is equivalent to the purely geometric formulation of finding a minimal arborally satisfied ($AS$) superset of a point set defined via the search query. $AS$ is very easily defined: two points of a set are in $AS$ if their axis-parallel induced rectangle is flat or contains another point of this set, and a point set is in $AS$ if all point pairs are.

An excellent approximation algorithm “Greedy Future” (which is at least very close to being instance optimal, but this question is open either) was already known, but is also considerably more elegant in the geometric formulation. An introduction to the theme complex will be given, and from the geometric approach questions are derived that are suited for an upcoming Master thesis.

Hamed Hosseinpour, University of Hamburg
July 24, 2020, 2:15, zoom: https://uni-hamburg.zoom.us/j/92459819104?pwd=MnR3djh2KzJHdTNBYnZacEd6d3EwQT09

Title: Fast Consensus via the Unconstrained Undecided State Dynamics

This talk is about sovling Plurality consensus problem via undecided state dynamics protocol. Consider a network of agents.
Initially, each agent has one of $k$ different opinions. Any agent may choose up to one random interaction partner per time step.
After such an interaction, the agent may revise its state according to some fixed transition function, depending on its own state and the state of its interaction partner. The goal is to design a protocol (i.e., a transition function) that causes all agents to eventually agree on the same opinion. We distinguish between the gossip model and the population model. In the former, each time step all agents choose a random interaction partner. In the latter, each time step only one agent chooses a random interaction partner and the time to consensus is expressed as parallel time -the number of time steps divided by $n$-, to account for the sequential nature of that model. All related works considered some assumptions on the inupt. We provide the first polylogarithmic population protocol solving consensus in unconstrained sitting.

Christoph Damerius
July 10, 2020, 2:15 PM. zoom: https://uni-hamburg.zoom.us/j/97419826765?pwd=d05oampUZ2pSWjgvU1FnVEtVS0xnZz09

Title: Towards 20%? coverage in Lower-Left-Anchored Rectangle Packing 

In the Lower-Left-Anchored Rectangle Packing (LLARP) Problem, we are given points P in the unit square U. We are asked to find non-overlapping rectangles of maximum total size whichs lower left corners are the points P. Five decades ago, Allen Freedman conjectured that at least 50% of the unit square can be covered, which remains open up to this day. Dumitrescu et al. has shown that ~9.1% of U can be covered by those squares, which was improved by Nicolaus Möller to ~9.6%. Our work is dedicated to a novel charging scheme that could significantly improve the coverage. Furthermore, it was conjectured that Dumitrescu's TilePacking algorithm already achieves the desired 50% coverage. We refute this by showing an upper bound of ~46.9%.

Felix Biermeier
June 26, 2020, 2:15 PM, zoom: https://uni-hamburg.zoom.us/j/96049915954?pwd=LzNZSzB2TEE4RVNhQlUwNVFzOTFKdz09

Title: An Analysis of the Unconstrained Undecided State Dynamics

This is the first part about the Undecided-State Dynamics. We are given a system of $n$ annonymous agents where each agent has initially one of $k$ opinions. We analyze the Undecided-State Dynamics in an unconstrained setting, i.e. the initial number of opinions and bias are not further restricted,in either the gossip and population model. The objective is the convergence time towards a single majority opinion and the local memory overhead of each agent.

Peter Kling
June 19, 2020, 2:15 PM, zoom: https://uni-hamburg.zoom.us/j/97812558690?pwd=Qk91WEtIR0ZjekNuYlhHME9nZ1hQUT09

Optimal Time and Space Leader Election in Population Protocols

Population protocols are a model of distributed computing, where $n$ agents with limited computational power and memory perform randomly scheduled pairwise interactions. A fundamental problem in this setting is that of \emph{leader election}, where all agents start from the same state, and they seek to reach and maintain a global state where exactly one agent is in a dedicated leader state.

A significant amount of work has been devoted to the study of the time and space complexity of this problem. Alistarh et al. (SODA'17) have shown that $\Omega(\log\log n)$ states per agent are needed in order to elect a leader in fewer than $\tilde \Theta(n^2)$ expected interactions. Moreover, $\Omega(n\log n)$ expected interactions are required regardless of the number of states (Sudo and Masuzawa, 2019). On the upper bound side, Gasieniec and Stachowiak (SODA'18) have presented the first protocol that uses an optimal, $\Theta(\log\log n)$, number or states and elects a leader in $O(n \log^2 n)$ expected interactions. This running time was subsequently improved to $O(n \log n\log\log n)$ (Gasieniec et al., SPAA'19).

In this talk I present the first leader election population protocol that is both time and space optimal:
it uses $\Theta(\log\log n)$ states per agent, and elects a leader in $O(n\log n)$ interactions in expectation. A key novel component of our approach is a simple protocol that efficiently selects a small set of agents, of $\poly(\log n)$ size, given an initial set of $s = O(n^\epsilon)$ selected agents. Unlike existing approaches, which proceed by shrinking the initial set monotonically over time, our novel component first increases the set in a controlled way to a specific size (which is independent of $s$), before it shrinks the set to a $\poly(\log n)$ size.

This is joint work with Petra Berenbrink and George Giakkoupis. To appear at STOC 2020.

Nicolaus Möller
June 19, 2020, 2:15 PM, zoom: https://uni-hamburg.zoom.us/j/97812558690?pwd=Qk91WEtIR0ZjekNuYlhHME9nZ1hQUT09

Improved Bounds for Lower-left Anchored Rectangle Packing

A "Lower-left Anchored Rectangle Packing" Problem (LLARP) is a geometrical problem in computer science. LLARP consists of finding non-overlapping rectangles in a unit square from given points (one of which is the origin) whereby all rectangles are anchored on its lower left corner by an input point. In the paper "Packing anchored rectangles" of Dumitrescu et al., a greedy algorithm was presented, which was used to prove a lower bound for LLARP. The submitted thesis improves that lower bound, proving that the worst-case performance of their algorithm covers at least 9.6% of the unit square. This work stands among other efforts in proving a long-standing conjecture stating that 50% of the unit square can always be covered.

Christopher Hahn (University of Hamburg)
May 22, 2020, 2:15 PM, zoom: https://uni-hamburg.zoom.us/j/92898090604?pwd=b1IxYzRYY3BXUmYrUk1NYWMvT3pmQT09

An Infinite Parallel Balls-into-bins Process with Limited Capacity II + Modeling epidemic spreading

The first part concludes the talk from November 2019 and summarizes the final state of our research. Suppose we create λn balls per round and throw all un-allocated balls independently and uniformly at random into n bins. The bins each have capacity c and only allocate balls until that limit is reached. They delete one ball per round. We showed that the capacity has a similar effect on the waiting time as letting balls chose among d bins: Balls wait for no longer than log log n + O( ln(1/(1-λ)) / c ) + O(c) . We also extended the analysis of the case where c=1 to allow the balls to pick a bin up to d times per round if they were not successful. The second part gives an overview over the state of the art in modeling and analysing the behaviour of epidemics in networks.

Florian Schneider (University of Hamburg)
May 22, 2020, 3:00 PM, zoom: https://uni-hamburg.zoom.us/j/92898090604?pwd=b1IxYzRYY3BXUmYrUk1NYWMvT3pmQT09

Modeling epidemic spreading II

I give an overview over the state of the art methods used in physics to analyse models used to describe the behaviour of epidemics in networks and obtain critical values for the model parameters.

Sarel Cohen (Tel Aviv University)
May 07, 2020, 10:15 am, Zoom

Dynamic and Fault-Tolerant Data-Structures and Algorithms

In this talk I present several results obtained during my PhD studies.

We first present the model of dynamic and fault-tolerant graph algorithms. We then focus on variants of shortest path algorithms and data-structures in
setting with failures. In particular, we study the following problems.

{\bf Distance Sensitivity Oracles}.
An f-Sensitive Distance Oracle (f-DSO) with stretch \alpha preprocesses a graph G(V,E) and produces a small data structure that is used to answer subsequent queries. A query is a triple consisting of a set F \subset E of at most f edges, and vertices s and t. The oracle answers a query (F,s,t) by returning a value \tilde{d} which is equal to the length of some path between s and t in the graph G\setminus F (the graph obtained from G by discarding all edges in F). Moreover, \tilde{d} is at most \alpha times the length of the shortest path between s and t in G\setminus F. The oracle can also construct a path between s and t in G\setminus F of length \tilde{d}.

Here we present several results regarding distance sensitivity oracles.

First, in a joint work with Shiri Chechik, Amos Fiat and Haim Kaplan [SODA 2017] we presented, to the best of our knowledge the first nontrivial f-sensitive distance oracle with fast query time and small stretch capable of handling multiple edge failures. Specifically, for any f = o(\frac{\log n}{\log \log n}) and a fixed \eps > 0 our oracle answers queries (F,s,t) in time \widetilde{O}(1) with (1+\eps) stretch using a data structure of size n^{2+o(1)}. For comparison, the na\"{\i}ve alternative requires m^fn^2 space for sublinear query time.

Second, in a joint work with Shiri Checik [STOC 2020], we presented the first distance sensitivity oracle with subcubic preprocessing time and very fast query time for directed graphs with integer weights in the range [-M,M]. Our distance sensitive oracle supports a single vertex/edge failure in subcubic \Otilde(Mn^{\omega+1/2}) = \Otilde(Mn^{2.873}) preprocessing time for \omega=2.373, and near optimal query time of \tilde{O}(1). For comparison, with the same \Otilde(Mn^{2.873}) preprocessing time the DSO of Grandoni and Vassilevska Williams [FOCS 12] has \Otilde(n^{0.693}) query time. In fact, the best query time their algorithm can obtain is \Otilde(Mn^{0.385}) (with \Otilde(Mn^3) preprocessing time).

{\bf The Replacement Paths problem}.
Let G = (V,E) be a directed unweighted graph with n vertices and m edges and let P be a shortest path from s to t in G. The {\sl replacement paths} problem is to find for every edge e \in P the shortest path from s to t avoiding e. Roditty and Zwick [ICALP 2005] obtained a randomized algorithm with running time of \Otilde(m \sqrt{n}).

In a joint work with Shiri Chechik and Noga Alon we presented the first deterministic algorithm for this problem [ICALP 2019], with the same \Otilde(m \sqrt{n}) time. Due to matching conditional lower bounds of Williams {\sl et. al.} [FOCS 2010], our deterministic combinatorial algorithm for the replacement paths problem is optimal up to polylogarithmic factors (unless the long standing bound of \Otilde(mn) for the combinatorial boolean matrix multiplication can be improved).

{\bf The Single Source Replacement Paths Problem}.
Given a graph G=(V,E) with n vertices and m edges, a source vertex s and a shortest paths tree T_s rooted in s, output for every vertex t \in V and for every edge e in T_s the length of the shortest path from s to t avoiding e.

In a joint work with Shiri Chechik [SODA 2019], we presented near optimal upper bounds, by providing \tilde{O}(m\sqrt{n} +n^2) time randomized combinatorial algorithm for unweighted undirected graphs, and matching conditional lower bounds for the SSRP problem.

Joachim Schmidberger (Universität Hamburg)
February 7, 2020, 2:00 PM, G-203

Entwicklung einer Web‐Anwendung für Workflowgeführte Tutorials in der Lehre

Petrinetze bieten eine einzigartige, graphische Sprache, mit der sowohl einfache Zusammenhänge, als auch komplexe Systeme übersichtlich und dennoch exakt beschrieben werden können. Der Arbeitsbereich ART am Fachbereich Informatik der Universität Hamburg bietet in Vorlesungen, Seminaren, Praktika und Projekten einen Einblick in die Welt graphischer Modellierungssprachen. Dennis Schmitz hat in seiner Masterarbeit das Lehrmaterial für diese Lehrprojekte überarbeitet und den Übungstexten auch statische Workflowgraphiken zur Seite gestellt. Anhand der dargestellten Workflownetze sollen sich die Lernenden beim Übungsfortschritt orientieren.

Die erstellten Workflownetze wurden, wie Schmitz feststellte, von den Lernenden nur wenig genutzt. Der Grund hierfür wird vor allem in der Wahl des Mediums Papier vermutet: Der häufige Wechsel zwischen Aufgaben- und Workflow-Papieren brachte mehr Umstände als Nutzen. Ziel dieser Arbeit ist es nun, eine Lösung zu finden, die den Vorteil der workflowgeführten Übungen in der Lehrpraxis nutzbar macht. Um das gesteckte Ziel zu erreichen, sollte der Wechsel des Mediums vollzogen werden. Die Workflowpapiere konnten so durch eine Webanwendung ersetzt und direkt mit den Übungsaufgaben der Übungsblätter verknüpft werden.

Im Rahmen dieser Bachelorarbeit wurde eine Webanwendung entwickelt, die Workflownetze nutzt, um durch die Übungsaufgaben der Tutorials zu führen. Die Wahl einer browserbasierten Applikation sollte die Einstiegshürde für die Benutzung der Tutorials so gering wie möglich halten. Die entwickelte Software kann ohne weitere Vorbereitungen von jedem Endgerät mit einem der gängigen Webbrowsern genutzt werden.

Die erarbeitet Lösung stellt eine Verschmelzung der Übungspapiere mit den Workflownetzen dar. Der Einsatz der Webtechnologie macht die Nutzung der Workflownetze als Navigationshilfe durch die Übungen sinnvoll. Das entwickelte System ist in der Praxis einsetzbar, kann aber zugleich als Anregung für zukünftige Weiterentwicklungen und weitere Anwendungsbereiche gesehen werden.

Sven Willrodt (Universität Hamburg)
January 31, 2020, 11:00 AM, G-203

A Modular Model Checking Framework for Reference Nets in Renew

A working prototype for the model checking problem for Reference nets, the Modular Model Checker (MoMoC), is presented. The purpose of MoMoC is to deliver a sustainable basis for future research on the topic of model checking for Reference nets. Therefore, a modular structure, based on comparable model checking tools for simpler Petri net formalisms is developed.

MoMoC can perform the CTL model checking algorithm with selected atomic propositions and specific operators that are developed for the Reference net formalism. Additionally, the plugin offers a stepwise inspection of the results of the CTL algorithm by a dynamic colourisation of the reachability graph. This should particularly help to teach the topic of model checking.

Florian Schneider (Universität Hamburg)
January 27, 2020, 2:15 PM, G-203

A brief overview over the defender-attacker model "FlipIt", and its derivatives

"FlipIt" aims to give a simple model to analyse typical attacker-defender situations common in cyber-security. Many different variants for FlipIt have been proposed and many results are shown for each of them.

The goal of this talk is to provide a brief overview over the FlipIt model/FlipIt derivatives and the results derived for them, as well as the methods used to derive them.

Lukas Hintze (Universität Hamburg)
January 20, 2020, 3:00 PM, G-203

Infinite Parallel Job Allocation through Limited-Capacity Queues

We consider the following infinite parallel job allocation problem, which we model using the language of balls-and-bins processes, with balls corresponding to jobs and bins corresponding to processors: In each discrete, synchronous round, some number of balls are generated in a distributed manner, so that the balls must be allocated in parallel to a set of $n$ bins, each of which processes one ball in each round in which its queue is non-empty. Each bin has a first-in first-out queue in which arriving balls are placed and from which to-be-processed balls are removed. The number of balls arriving each round is, in expectation, $\lambda n$, where $\lambda$ is called the \emph{arrival rate} and may be a function in $n$ (e.g. $\lambda(n) = 1 - n^{-\alpha}$ for positive $\alpha \in \R$).

In this work, we analyze the following strategy: The capacity of each bin's queue is limited to some capacity $c$, so that balls may fail to be allocated to their preferred bin since that bin's queue may be full. If in a round, a bin gets more requests than there is unused capacity in its queue, it accepts those balls which were oldest among all requesting balls, that is, those that were generated the earliest. Balls send their allocation requests to a bin chosen independently and uniformly at random.

Hamad Hosseinpour (Universität Hamburg)
January 20, 2020, 2:15 PM, G-203

Consensus Problem using Undecided Dynamics Protocol

We are given a complete graph in which each node has an opinion out of a finite-size set of opinions. We do iteratively an specific and common randomized updating rule for each node such that at the end we reach a state in which all nodes share the same opinion. The updating rule we are using is undecided dynamics consisting of two parts. In a nutshell, time is devided as phases each one consists of $\log n$ rounds. At the start of each phase, every opinion loses a fraction of its support and during the remaining rounds of this phase, each color takes new supports based on a function of the fraction of its first support. We will show this protocol reaches consensus in $poly(\log n)$ rounds in which $n$ is the number of nodes in the underlying graph.

Matthias Feldmann (Universität Hamburg)
January 17, 2020, 2:15 PM, G-203

Containerization of the Reference Net Workshop and Evaluation of Interprocess Communication Technologies for Containerized Multi-Agent Net Applications

The goal of this work was to run Renew with Mulan in Docker containers to allow creating and running portable, scalable multi-agent systems. As communication is an important part of multi-agent systems, memory-based interprocess communication was evaluated as an alternative to the existing message passing system in Mulan. The talk shows how the Docker images were created and how to use them, as well as the problems with running Renew in Docker containers, as well as how the continuous integration pipeline was upgraded to make deployment easier. Regarding interprocess communication, multiple approaches to memory-based communication are presented and the process of one of the implementations and its results are discussed.

2019


Jan Hendrik Röwekam (Universität Hamburg)
December 16, 2019, 2:15 PM, G-203

Scalable Execution of Distributed System Models based on Renew, Spring, Docker and Kubernetes

Designing distributed systems is a challenging task. With different options for the solution, one promising approach is to introduce a global model of the system. While models and implementations are usually separate entities, the reference net formalism - a specific Petri net formalism - unifies both and features executable models. Up until a few years ago execution was only available on a local system, which defied a lot of the advantages. As scalability is one of the major concerns in todays enterprise grade application deployments, it is an important aspect to consider while creating a distributed execution environment for reference nets. The talk will give an overview of the current status regarding a scalable architecture for the Renew simulator as well as its progression in the direction of a microservice platform.

Christiane Frede (Universität Hamburg)
December 9, 2019, 2:15 PM, G-203

Exploring in which Assignments Students Struggle in Theory of Computation Introductory Courses

In 2018, I began to investigate in which assignments and topics computer science students have the worst performance in the theory of computer introductory courses. After presenting the results of an explorative data analysis of student performance in the final exams and homework assignments from 2016 last time, this time I did the same analysis for the years 2017 and 2018. Additionally, I calculated if the results differ significantly between the years and what could be reasons for the different performance.

Hamed Hosseinpour (Universität Hamburg)
November 27, 2019, 4:00 PM, G-210

Excisting Open Problems in Complex System Networks

This presentation is about the poster of our group consisting of four kind of related problems in distributed and collaborative systems of agents. One model for modeling and predicting the behavior of such problems is known as Complex System. Briefly, We have given a graph in which nodes are agents and each one has an opinion out of a set of opinions and also the edges showing the possible interactions between agents. Each agent can interact with a limited number of agents and update its opinion based on a function defined over the opinions of randomly sampled neighbors. In some problems the goals are proving the fast convergence time of the system to a state in which all agents have the same opinion or to a Nash equilibrium by doing the update rules repeatedly. The problems are voter processes, majority processes (and undecided dynamics), processes with private beliefs and Epidemic spreading. We will talk about the mentioned problems and also the techniques to deal with those.

Christoph Damerius (Universität Hamburg)
November 25, 2019, 2:15 PM, G-203

A 1.5-approximation Algorithm for Shared Job Resource Scheduling on Two Machines

We consider a scheduling problem where a set of jobs have to be scheduled on a number of machines. Each job j has a processing time (workload) p_j and a resource requirement r_j. The machines share a resource, which we wish to distribute over time among the jobs. A job which is granted its full resource requirement r_j over time processes in p_j time. Assigning a job less resource leads to a slower execution of that job. Another hurdle is that the time is slotted and the scheduler is only allowed to change the resource assignment from slot to slot. Our goal is to minimize the schedule's makespan. We present a (1.5+epsilon)-approximation for the case of two machines.

Christopher Hahn (Universität Hamburg)
November 18, 2019, 2:15, G-203

An Infinite Parallel Balls-into-bins Process with Limited Capacity

The static balls-into-bins problem considers a number of balls m to be thrown into n bins independently and uniformly at random. In the sequential dynamic case, one ball per round is deleted according to a given schedule and a new ball is thrown over an infinite number of rounds. It is well known, that the highest bin load is O( log n / log log n ) w.h.p. and can be reduced to O( log log n / log d ) in both the static and the dynamic system when letting each ball chose the least loaded of d bins. Similarly, when throwing λn balls in parallel per round and deleting one ball per bin two choices decrease the highest bin load (and therefore the maximal time until a ball is deleted) significantly. We extent the parallel dynamic case by limiting the capacity of the bins by a constant c. Therefore, balls might be rejected and have to be rethrown next round. We want to show that this has a similar effect on the number of rounds a ball waits until its deletion.

Projekt "Algorithmic Games in TCS" (Universität Hamburg)
October 1, 2019, 2:00 AM, G-228
Abschlussvortrag Projekt

Mastermind

In the Master's programme project "Algorithmic Games in Theoretical Computer Science" in the 2018/2019 instance "Mastermind", several new versions of the Mastermind game have been investigated. A simulator has been programmed to play these variants. Many simulations were run and utilized to find hypotheses on the effectivity of several strategies of the two player types (code maker and breaker), and first proofs have been made. The talk will be structured as follows:

In the first part of the talk, an overview of the project management is given and the general rules of the game are explained. This is then followed by our theoretical foundation work, with regards to the researched variants and our hypotheses on strategy effectivenes. Third, we will present the simulator that was created during the project to gather empirical data regarding out hypotheses, as well as an excerpt of the data. The fourth part will be dealing with several insights and taken steps regarding quality management, mainly with regards to the simulator discussed before. A recap of the achievements in comparison to our original plans and an outlook conclude the talk and lead into the discussion.

ARKADI DASCHKEWITZ (Universität Hamburg)
September 30, 2019, 2:40 PM, G-203
Abschlussvortrag Masterarbeit

Modularisierung des Renew-Plugin-Systems

Die Digitalisierung innerhalb der Gesellschaft durchdringt jeden Bereich unseres Lebens. Vom Web, Smartphones, Augmented Reality bis zu Smart Cities, wird die Entwicklung und Beherrschung komplexer Softwaresysteme eine bedeutende Aufgabe sein. Dementsprechend spielt der Wartungsaufwand, die Erweiterbarkeit und die Flexibilität des Systems, eine zentrale Rolle für die Softwareentwicklung. Diesen wichtigen Aufgaben hat sich das Modulsystem von Java gewidmet und ermöglicht das Erstellen von Modulen, die spezifische Aufgaben kapseln und die Komplexität innerhalb einer Applikation bändigt.

Die Präsentation behandelt das Thema der Modularisierung des Renew-Plugin-Systems. Es geht um die neue eingeführten Konzepte des Modulsystems von Java, wie Module, Modulschichten, und die damit verbunden Konsequenzen.

MARIE KLEIN (Universität Hamburg)
July 19, 2019, 11:15 AM, G-228
Abschlussvortrag Bachelorarbeit

Betrachtung der Evakuierung als Variation des Suchproblems

Seit 2014 kam vermehrt das Evakuierungsproblem in der theoretischen Informatik auf. Bei diesem relativ neuen und aktuellen Problem suchen mehrere Agenten einen Ausgang in einem unerforschten Raum. Im Gegensatz zum bekannten Suchproblem wird hierbei nicht die Zeit betrachtet, bis das Suchobjekt - der Ausgang - gefunden wird, sondern bis alle Agenten diesen erreicht haben. Dabei gibt es verschiedene Modelle und Algorithmen, die das Evakuierungsproblem lösen und verfeinern. Diese Modelle werden betrachtet und ausgewählte Veröffentlichungen diskutiert. Von diesen Publikationen werden die wichtigsten Algorithmen vorgestellt und simuliert.

MOHAMMAD DORGHAM (Universität Hamburg)
June 28, 2019, 2:15 PM, G-203
Abschlussvortrag Masterarbeit

Cover Time of Coalescing-Branching Random Walks with Arbitrary Branching Factor

Coalescing-Branching random walk (CoBra) is a generalization of the standard random walk on graphs. It proved to be an efficient way of speeding up random walks on graphs. CoBra walk begins with one particle at a random node in the graph, this particle is split into $k$ identical copies ($k$ is called the branching factor). Each one of these $k$ particles independently chooses one neighbor node uniformly at random and moves to that neighbor node. If two or more particles meet in the same node they coalesce together forming one new particle. This process of branching-moving-coalescing repeats for all particles in the graph each round. The cover time of CoBra walk with branching factor $k=2$ is studied recently in many papers for some classes of graphs. However, no analysis is performed for CoBra walk with an arbitrary branching factor to see how increasing $k$ affects the speed of the cover time. In this thesis, the cover time of CoBra walk with arbitrary branching factor is studied on some classes of graphs. This project began as an attempt to find a bound for the class of regular graphs, but it was discovered later that not all regular graphs behave similarly to increasing the branching factor. A cover time of $\Theta(N)$ is proved for $d$-dimensional tori graphs $T_N$ with $N$ nodes in each dimension, showing no effect of increasing $k$. On the other hand, a lower bound on the cover time on complete graphs shows a logarithmic dependence on $k$. In addition, simulations performed suggest a logarithmic speedup in the cover time over complete graphs, random regular graphs and other subclasses of regular graphs.

MINMING LI (City University of Hong Kong)
June 19, 2019, 11:15 AM, G-228

Energy-Aware Real-Time Task Scheduling on Local/Shared Memory Systems

The rapid development of the Real-Time and Embedded System (RTES) has increased the requirement on the processing capabilities of sensors, mobile phones and smart devices, etc. Meanwhile, energy efficiency techniques are in desperate need as most devices in RTES are battery powered. Following the above two trends, this work explores the memory system energy efficiency for a general multi-core architecture. This architecture integrates a local memory in each processing core, with a large off-chip memory shared among multiple cores. Decisions need to be made on whether tasks will be executed with the shared memory or the local memory to minimize the total energy consumption within real-time constraints. This paper proposes optimal schemes as well as a polynomial-time approximation algorithm with constant ratio.

FLORIAN SCHNEIDER (Universität Hamburg)
June 12, 2019, 2:15 PM, G-228

Das CPT-Theorem in Quanten-Feld-Theorien

In dem Vortrag werde ich eine kurze Zusammenfassung meiner Masterarbeit präsentieren. Dazu werde ich zu Beginn eine Einführung in die Theorie von QFTs, sowie die Bedeutung von C,P, und T-Transformationen geben, um anschließend das CPT-Theorem zu formalisieren. Im Anschluss folgt eine Beweisskizze für das axiomatische CPT-Theorem von Jost/Wightman/Streater, sowie eine kurze Diskussion über die Anwendbarkeit des Theorems in modernen QFTs. Zum Schluss gebe ich noch eine Beweisskizze für eine Version des CPT-Theorems, welches für interagierende Dirac-Felder anwendbar ist.

LASSE WULF (Karlsruhe Institute of Technology)
June 11, 2019, 2:15 PM, G-228

Das Kartenspiel "Supertrumpf" und ein Labeling für die Weite

Wir untersuchen eine bestimmte Relation R, die von dem Spiel "Supertrumpf" inspiriert ist. Supertrumpf ist ein Kartenspiel, das viele Leute aus ihrer Kindheit kennen. Obwohl das Spiel selbst recht einfach ist, und noch nie wissenschaftlich untersucht wurde, ist die dahinterliegende Theorie überraschend nichttrivial. Wir zeigen, dass das Thema verwandt ist mit dem Begriff der Weite einer partiell geordneter Menge (Poset). Als besondere Konsequenz ergibt sich, dass die Weite eines Posets P genau die minimale Dimension n ist, in der eine Beschriftung von P mit n-dimensionalen Labels existiert, sodass die Relation R über diesen Labels genau P ergibt. Diese Tatsache war bislang unbekannt.

UTZ PÖHLMANN
May 14, 2019, 2:00 PM, G-210
Abschlussvortrag Bachelorarbeit

Analyse über Möglichkeiten der Erkenntnisgewinnung aus temporalen Sterngraphen

Diese Bachelorarbeit befasst sich mit dem TSP unter der Voraussetzung, dass der zugrundeliegende Graph ein temporaler Sterngraph ist. Es wird, basierend auf den Ergebnissen von Akrida et al. [6], das TSP erst auf allgemeinen Bäumen untersucht. Dann werden einige Ideen hinsichtlich der Komplexität erläutert. Daraufhin werden mehrere Ansätze von neuen Approximationsalgorithmen vorgestellt. Zum Schluss wird einer dieser Ansätze noch zu Anschauungszwecken auf seine Qualität hin heuristisch untersucht. Währenddessen werden immer wieder neue Ideen und Ansätze zur Anregung mitgeliefert.

JANNICK SUNDERMEIER (Universität Paderborn)
April 11, 2019, 2:15 PM, G-203

Stretching a Communication Chain of Oblivious Mobile Robots

We consider a chain of oblivious robots with limited viewing range. In the chain, each inner robot has exactly two neighbors and the two outer robots have only a single neighbor. The viewing range of each robot is assumed to be 1. The aim of our strategy is to transform an arbitrary connected initial chain into a straight line of length n-1. We study both the FSYNC model in which robots operate in synchronous rounds and the continuous time model in which robots are able to immediately react on the movements of their neighbors.

In the talk, I present the Max-Go-To-The-Middle Strategy (FSYNC) and the Max-Move-On-Bisector-Strategy (continuous) together with some already known runtime results and current ongoing research.

CHRISTIANE FREDE (Universität Hamburg)
March 1, 2019, 2:15 PM, G-203

Current state of my dissertation about students’ problems with Theory of Computation topics

A high number of Computer Science students regularly fail to pass Theory of Computation courses and there is a lack of empirical investigation about the reasons for this situation and the students’ actual difficulties. I conducted several preliminary quantitative and qualitative studies to reach a better insight into the nature of students’ difficulties and to frame the main study of my dissertation. This presentation is about the current state of the main study including my motivation and the used learning theory as well as the results from my preliminary studies. Additionally, I will motivate my further steps and present the data I collected.

CHRISTOPH DAMERIUS (Universität Hamburg)
February 15, 2019, 2:15 PM, G-228

On Hardness and Approximation Results of the Center-anchored Rectangle Packing Problem

Given a [0,1]^2 square and a finite set of points inside of that square, the CARP problem asks to cover most possible area by packing one rectangle around each point such that the point is in the center of the rectangle and the packed rectangles do not overlap. The presentation discusses an NP-completeness proof and a PTAS for CARP.

MARCEL ELLERMANN
February 8, 2019, 2:15 PM

Untersuchung der Nebenläufigkeit im Renew Simulationsalgorithmus

Ziel der Arbeit ist es, die Implementation des Simulationsalgorithmus in Renew auf Nebenläufigkeit zu untersuchen und diese zu verbessern. Dabei wurde ein schwerwiegender Fehler in einem der Simulatoren gefunden und im Zuge dieser Arbeit behoben. Unter Berücksichtigung verschiedener Aspekte wie Speichernutzung, Menge an Codeänderungen, sowie Leistungseinbuße wurden verschiedene Prototypen entwickelt. Es wird aufgezeigt, welche Probleme beim nebenläufigen Simulieren von Referenznetzen auftreten und wie sie in Java zu lösen sind.

2018


CARLOS SANTOS OLIVEIR
Decembre 14, 2018, 2:15 PM

Konzeption und Realisierung eines Spiels in OpenOLAT zur Unterstützung des Lernprozesses von FGI-1 und FGI-2 

Lernen und Lehren sind zwei Aspekte der Bildung, die immer zusammengehören. Die Rolle der Technologie im Lernprozess wird immer größer und Erweiterungen der Unterrichtseinheiten, Vorlesungen und Seminare immer präsenter durch die Benutzung von den sogenannten Learning Management Systems (LMS) wie OpenOlat und Moodle.

Lernen macht mehr Spaß, wenn einem nicht offensichtlich bewusst ist, dass man lernt. Dieses Prinzip verfolgt jeder von uns in der Kindheit. Dies verliert aber im erwachsenen Leben seine Bedeutung und seine Präsenz. Wenn in der Schule noch der didaktische Aspekt des Ludus (Latein für Spiel) eine Rolle spielt, wird es im akademischen Bereich in vielen Disziplinen, Vorlesungen, Seminaren und Übungen vergessen.

Die Zielsetzung dieser Arbeit ist durch eine eigene entwickelte Software im Format eines Quiz-Spiels, das an die OpenOlat Umgebung angekoppelt werden soll, zu analysieren, ob Studenten, die durch das Spiel die Konzepte und Übungen der Vorlesungen FGI-1 und FGI-2 wiederholen können und diese besser verinnerlichen, sodass ihre Leistung in Form von Klausur- und Übungsnoten besser werden. 

MARC RICHTER
Decembre 14, 2018, 2:15 PM

Herr Richter berichtet über den Stand seiner BSc-Arbeit mit der Möglichkeit der anschließenden Diskussion.

LOUIS KOBRAS,
Decembre 14, 2018, 2:15 PM

Herr Kobras stellt das Thema seiner BSc-Arbeit vor mit der Möglichkeit der anschließenden Diskussion.

MICHAEL SIMON
Decembre 13, 2018, 10:30 AM

Curry-Coloured Petri Nets
A Concurrent Simulator for Petri Nets with Purely Functional Logic Program Inscriptions

The concept and implementation of the Curry-coloured Petri net (CCPN) simulator are presented. The CCPN formalism combines Petri nets with the purely functional logic programming language Curry. The most notable aspects of this formalism are the absence of side effects in function evaluation and the use of the logic program evaluation for the transition binding search. Furthermore, non-deterministic programs can be inscribed to transitions.

A concurrent simulator implementation in Haskell exploits the concurrency, inherent in the CCPN formalism. This allows the use of the simulator for general purpose programming of concurrent software systems.

An integration into Renew provides a practical graphical interface for editing CCPNs as well as observing and controlling their simulation. It can simulate a CCPN or generate the reachability graph.

The CCPN simulator can also be integrated as a library into other Haskell programs. The CCPN library provides different interfaces to control the simulation. It offers the same high-level control commands as used by the CurryCPN Renew plugin. Furthermore, it can interact with the marking as well as fire specific transition sequences.

JIYAN JONSDOTTER
Novembre 9, 2018, 2:15 PM

Untersuchung des Travelling Salesman Problems unter verschiedenen Variationen

Das Travelling Salesman Problem (TSP) befasst sich mit der Fragestellung, inwiefern in einem Graphen eine bestimmte Menge an Knoten in kürzester Zeit besucht werden kann.
In diesem Vortrag werden die Ergebnisse einer Masterarbeit vorgestellt, welche verschiedene Variationen des Online TSP untersucht hat. Dabei wurde insbesondere versucht die Idee eines scharfen Algorithmus auf der Linie auf eine andere Metrik (eines Sterns) zu übertragen.

MARTIN WINCIERZ
Novembre 1, 2018, 2:15 PM

Verbesserung der Erweiterbarkeit und Benutzbarkeit der grafischen Oberfläche des Petrinetz Simulators Renew

Der Petrinetz Simulator Renew wird seit vielen Jahren aktiv weiterentwickelt. Gerade durch seine auf Erweiterbarkeit ausgelegte Plugin Struktur und durch seine vergleichsweise mächtigen grafischen Modellierungs-Möglichkeiten ist die Software für die Forschung im Bereich der Petrinetze und Domänenspezifischen Sprachen interessant. Die Benutzungsoberfläche hat sich in den letzten Jahren jedoch kaum verändert. Dieser Vortrag stellt die Ergebnisse der gleichnamigen Masterarbeit vor, in der Verbesserungen der Oberfläche ausgearbeitet und umgesetzt wurden.

FREDERIK THOMSSEN
June 12, 2018, 3:00 PM

Unterstützung der Analyse von Prozessen in Paose-Lehrprojekten - Konzeption, Bereitstellung und Nutzung spezieller Werkzeuge für Process-Mining-Verfahren

Im Bereich der Softwareentwicklung ist es üblich, dass die Entwicklung der Software sowie die Koordination der Ressourcen gemäß zuvor definierter Prozesse ablaufen. Hierbei gibt es eine große Bandbreite von statischen bis hin zu dynamischen und agilen Prozessen. Gerade bei den agilen Prozessen liegt eine Menge Verantwortung zur Einhaltung des Prozesses bei den einzelnen Entwicklerinnen und Entwicklern.

An dieser Stelle kann das Process-Mining zur Erstellung eines möglichst effizienten Prozesses sowie zur Optimierung bestehender Prozesse beitragen. Zudem kann es die Entwickler und Entwicklerinnen bei der Einhaltung ihrer Ziele und Zeiten unterstützen.  Weiterhin kann das Process-Mining die Projektleitung bei der Planung von Zeiten und Ressourcen unterstützen.

Diese Arbeit konzipiert und stellt Werkzeuge bereit, die dafür genutzt werden können, um die Analyse von Prozessen in
Paose-Lehrprojekten zu unterstützen. Konkret wird im Rahmen dieser Arbeit die Integration der entwickelten Werkzeuge in das
Projektmanagementsystem, die grafische Oberfläche und das Versionsverwaltungssystem sowie letztlich in die Entwicklungsprozesse besprochen.

Resultate der vorgenommenen Integrationen sind beispielsweise, dass die gebuchten Arbeitszeiten der Projektteilnehmenden deutlich
genauer sind und dadurch lang laufende Aufgaben gefunden werden können. Weiterhin kann nun herausgefunden werden, wann Teilnehmende vom
vorgegebenen Prozess abweichen.

GEORGE GIAKKOUPIS (IRISA/INRIA Rennes)
Juli 19, 2018, 4:15 PM

Random Binary Search Trees with Concurrent Insertions

We consider the following simple random experiment to determine the impact of concurrency on the performance of binary search trees: n randomly permuted keys arrive one at a time. When a new key arrives, it is first placed into a buffer of size c. Whenever the buffer is full, or when all keys have arrived, an adversary chooses one key from the buffer and inserts it into the binary search tree. The ability of the adversary to choose the next key to insert among c buffered keys, models a distributed system, where up to c processes try to insert keys concurrently. We show that the expected average depth of nodes in the resulting tree is 2ln n + O(c), for any adversarial strategy of choosing the next buffered key to inserted into the tree. This result is tight, and answers an open question by Aspnes and Ruppert (DISC 2016).

Ref: George Giakkoupis, Philipp Woelfel: An Improved Bound for Random Binary Search Trees with Concurrent Insertions. STACS 2018: 37:1-37:13

HAUKE REDDMANN
June 8, 2018, 2:15 PM

Über die Laufzeit von Konsensus-Algorithmen

Der Aufstieg der Sozialen Medien befeuerte erneut das Interesse an den mathematischen Aspekten von Konsensus-Algorithmen, wie Effektivität, Laufzeit und Fehlertoleranz. Ein vielversprechendes einfaches, stabiles und schnelles Protokoll ist m-MAJORITY, welches rundenbasiert abläuft und zu einem Konsens konvergiert, in dem jeder Teilnehmer die Meinung von m Nachbarn einholt und seine eigene zu der von ihm gesehenen Mehrheitsmeinung ändert. Es ist intuitiv plausibel, dass ein höheres m eine schnellere Laufzeit zur Folge hat. Mit Methoden aus der Theorie der Markov-Ketten und der Majorisation wurde versucht, dies zu beweisen, letztlich ohne Erfolg. Mit eigenen Programmen vorgenommene Simulationen sprechen aber deutlich für die Richtigkeit der These.

CHRISTOPH DAMERIUS (Universität Hamburg)
June 1, 2018, 2:15 PM

Vorstellung der Masterarbeit mit dem Titel "Festparametet-berechenbare Algorithmen für Vertex-Cover"

In der Masterarbeit wurde die grundlegende Theorie parametrisierter Algorithmen und ihre Anwendung auf das parametrisierte Vertex-Cover-Problem (VC-k) betrachtet. Zu den Techniken zählen in erste Linie tiefenbeschränkte Suchbäume und die problemkernreduktion. Der aktuell beste Algorithmus für VC-k wurde auf theoretischer Ebene sowie in der Implementation mit einem einfachen Algorithmus verglichen. Ziel der Arbeit war einerseits ein besseres Verständnis vorhandener Algorithmen für VC-k, andererseits die Frage nach der Performanz aktueller Algorithmen auf schweren Testinstanzen. Hieraus ergab sich im theoretischen Teil eine Verbesserung der Faltungsoperation und im praktischen Teil Methoden zur besseren Implementation dieser Algorithmen.

In the master thesis the basic theory of parameterized algorithms and their application on the parameterized vertex cover problem (VC-k) was presented. The most important techniques include depth-restricted search trees and kernelization. The current best algorithm for VC-k has been compared with a simple algorithm on the theoretical level as well as in the implementation. The goal of the work was on the one hand a better understanding of existing algorithms for VC-k, and on the other hand the question of performance current algorithms have on difficult test instances. This resulted in an improvement in the theoretical part, namely the folding operation,
and in the practical part methods for better implementation of these algorithms.

JIYAN JONSDOTTER
May 11, 2018, 2:15 PM

Variationen des Travelling Salesman Problems
Das Travellings Salesman Problem (TSP) befasst sich mit der Frage wie auf einem Graphen algorithmisch die kürzeste Route gefunden werden kann, welche alle Knoten des Graphen besuchen. Im Rahmen des Vortrages soll ein Einblick gegeben werden über Variationen des TSP und untersuchbaren Fragestellungen im Hinblick auf Online Algorithmen. Mögliche Änderungen umfassen: spezielle Metriken, Variation der Anzahl der Server oder Beschränkung des Adversaries.

CHRISTIANE FREDE (Universität Hamburg)
April 27, 2018, 2:15 PM

Exploring how students perform in Theory of Computation courses using final exam and homework assignments data
A high number of Computer Science students regularly fail to pass Theory of Computation courses and there is a lack of empirical investigation about the reasons for this situation and the students’ actual difficulties. In order to gain a differentiated picture of students’ overall performance and learn about potential challenges all students are faced with, I used exploratory data analysis. For that matter, I used numerical data from students’ final exam results and homework assignment scores obtained in an introductory course to explore this research field and develop hypotheses about it comparable to qualitative approaches. The results show that all students scored low in formal proof assignments during the exam while their scores varied in homework assignments independent from their overall performance in the final exam. These results strengthen the need for pedagogical approaches in ToC that are addressing all students and are particularly focusing on teaching them formal proofing.

2017


JAN STENZEL
December 15, 2017, 2:15 PM

Populationsprotokolle für Leader Election

In meiner Arbeit wird das Protokoll Leader-Minion-Coin vorgestellt. Dieses Protokoll stellt eine Verbesserung des Protokolls Leader-Minion aus dem Paper “Space-optimal majority in population protocols” dar. Der Algorithmus aus dem Protokoll wird leicht verändert, indem ein Anführer nicht immer seinen Wert um 1 erhöht, wenn er ein Anführer geblieben ist. Stattdessen wird eine Münze verwendet, die mit einer Wahrscheinlichkeit von 1/log(n) “Kopf” anzeigt und mit einer Wahrscheinlichkeit von 1 - 1/log(n) “Zahl” anzeigt. Das führt dazu, dass die Rundenzahl reduziert wird und dasss die Anführer deutlich geringere Werte haben, sodass weniger Speicherplatz benötigt wird. Es werden nicht mehr O(n log^3 n) Interaktionen verwendet, wie bei Leader-Minion, sondern nur noch O(n log^2 n) Interaktionen. Der Platzbedarf ist bei Leader-Minon-Coin nicht mehr O(log^3 n), sondern O(log^2 n): Eine genaue Analyse der Ergebnisse sowie eine empirische Auswertung finden Sie in meiner Bachelorarbeit.

FELIX BIERMEIER (Paderborn University)
December 8, 2017, 3:00 PM

Continuous Monitoring of Distributed Data Streams for Partitioning Problems

Continuous monitoring of distributed data streams attracts attention in recent years. In this thesis we introduce and analyze the γ-Interval Partitioning Monitoring problem in which the server is asked to continuously output a disjoint partition of n nodes into intervals such that nodes of the same interval observe similar values with respect to an error value γ. The goal is to minimize the communication cost between the server and the nodes. We present randomized algorithms for the γ-Interval Partitioning Monitoring problem and variants of it.
At first, we present a randomized algorithm that solves a simplified variant of this problem for a single time step using O(m log γ log n) messages in expectation. The factor m is the minimum partition size of an optimal solution.
Then, we present a filter-based online algorithm that solves the γ-Interval Partitioning Monitoring problem and compare it with an restricted optimal offline algorithm that is also filter-based and its partition size is bounded by a parameter k. We show that the online algorithm is O(k log2 n log γ)-competitive. At last, we investigate another variant of the γ-Interval Partitioning Monitoring problem in which the online algorithm is allowed to double its error γ, whereas the restricted optimal offline algorithm remains as before. We present a filter-based online algorithm that improves the previous competitiveness from O(k log2 n log γ) to O(k log2 n).

KATJA MÖHRING
December 8, 2017, 2:15 PM

Awn2Uppaal

Awn2Uppaal is a program that transforms protocol specifications in AWN to a model of automata for the UPPAAL model checker. It aims to make the process of verifying protocols easier and therefore open to a wider audience. Using this program, a user needs to specify a protocol in AWN and can simulate and verify the system in UPPAAL.

VERA ERMAKOVA
November 28, 2017, 4:15 PM

Verification on nested Petri nets by means of unfoldings

Nested Petri nets (NP-nets) proved to be one of the best formalisms for distributed systems analysis and modeling. They naturally represent multi-agent systems structure, because tokens in the main system net are Petri nets (P/T-nets) themselves, and can have their own behavior.

To check nested Petri net model properties one of the most popular verification method, model checking, could be used. However, there is a crucial problem for verification of highly concurrent systems using model checking approach - a large number of interleavings of concurrent processes. This leads to the so-called state-space explosion problem.
To tackle this problem unfolding theory was introduced. In a paper of D. Frumin and I. Lomazova applicability of unfoldings for NP-nets was studied and the method for constructing unfoldings for safe conservative NP-nets was proposed. However, as safe conservative NP-nets are bounded, for such net it is possible to construct a P/T net with equivalent behavior, for which the standard unfolding techniques can be applied. Then the question is whether direct unfolding is really better than constructing unfoldings via translation of NP-nets into safe P/T nets is better in terms of time complexity.
We study this question. For that we developed an algorithm for translating a safe conservative NP-net into a behaviorally equivalent P/T net. We proved that the reachability graphs of a source NP-net and the obtained P/T net are isomorphic, and hence both unfolding methods give the same (up to isomorphism) result. From general considerations translating an NP-net into a P/T net and then constructing unfoldings will be more time consuming, than constructing unfoldings directly. To check whether this time gap reveals itself in practice, we implemented all the algorithms and compare both methods experimentally. We have shown that each conservative safe NP-net can be converted into a behaviorally equivalent classical P/T net.

MATJAŽ KRNC (University of Salzburg)
October 16, 2017, 11:15 AM

Fast and Simple Consensus in Networks

We study the problem of distributed plurality consensus in a complete graph,in which initially every node holds one of k distinct opinions. We present a simple protocol which allows nodes to converge to the initial majority opinion,and in some cases improve the asymptotic running times of the current state-of-the-art protocols.

MARKUS KUPPE 
July 11, 2017, 2:00 PM

A Verified and Scalable Hash Table for the TLC Model Checker
Towards an Order of Magnitude Speedup

Die Einsetzbarkeit von explizitem Model-Checking wird durch das explosionsartige Anwachsen des Zustandsraums eingeschränkt, wodurch die Größe der prüfbaren Modelle begrenzt wird. Dem Anwachsen des Zustandsraums lässt sich jedoch mit (vertikaler) Skalierung auf Multiprozessor-Systemen begegnen.
In diesem Vortrag wird zur Steigerung der Skalierbarkeit eine nicht-blockierende, Speicherplatz-optimale Hashtabelle vorgestellt, die - kombiniert mit weiteren Optimierungen der Breitensuche - die Skalierbarkeit des TLA+ Model-Checker um eine Größenordnung verbessert. Eine Besonderheit dabei ist, dass der TLA+ Model-Checker und somit die Hashtabelle nicht auf den Primärspeicher begrenzt sind. Demnach lassen sich Modelle beliebiger (endlicher) Größe mit ihm prüfen. Da ein Model-Checker selbst kritische Software darstellt, wurde die Hashtabelle mit TLA+ formal spezifiziert und mit dem Model-Checker auf Korrektheit überprüft. Die nicht-funktionale Anforderung Skalierbarkeit wurden anschließend anhand einer Implementierung empirisch sichergestellt und mit dem SPIN Model-Checker verglichen.

JAN HICKEN 
July 11, 2017, 3:00 PM

Ermittlung von Data Provenance zur Integration in ein Metadatenmanagementsystem im Kontext eines Big Data Ökosystems mit Hadoop und Hive

RÜDIGER VALK
June 20, 2017, 2:15 PM, G-203

Über Populations-Protokolle und Petrinetze

Es wird gezeigt, dass Populations-Protokolle einer Unterklasse von Petrinetzen entsprechen. Dadurch können Petrinetzwerkzeuge auch zu deren Darstellung, Simulation und Analyse herangezogen werden. Über 10 Jahre alte offene Entscheidbarkeits-Probleme von Populations-Protokollen konnten durch Reduktion auf das Petrinetz-Erreichbarkeitsproblem gelöst werden. Da es jedoch bis jetzt keine primitiv-rekursiven Algorithmen dafür gibt, wurde kürzlich eine Unterklasse von Populations-Protokollen entwickelt, die gleichmächtig zu dem allgemeinen Modell ist (d.h. semilineare Prädikate berechnet), alle bekannten Beispiele umfasst und in der Komplexitäts-Klasse DO (Durchschnitt von Elementen aus NP und coNP) liegt.

JAN HENRIK RÖWEKAMP (Universität Hamburg)
June 13, 2017, 3:00 PM, G-203

Fast Thresholding of High Dimensional Euclidean Distances using Binary Squaring

This paper presents a new approximative method to threshold Euclidean distances. The procedure utilizes so called binary squares, which will be introduced and formally put into relation to conventional square computations. The proposed method can significantly speed up distance matching. The speed gain depends on several parameters, like dimension count (the higher the better), total distances and the percentage of distances outside of the desired thresholded area. In the worst case its running time degenerates to the running time of conventional square based computation. The method is essentially presented for integer coordinates, but can – to a certain degree – be applied to floating point coordinates as well. Though being an approximation method the results diverge from the correct results only by a small margin in most cases.

LENA OTTERBACH (Universität Hamburg)
May 30, 2017, 2:15 PM, G-203

Majority and Leader Election in Population Protocols

In the population protocol model we consider a collection (or population) of simple agents that interact randomly and cooperatively solve a global problem. Agents have limited local states and update these states during an interaction according to their own state and the state of their communication partner by simple rules. These rules are specified by a protocol. All agents have to perform the same protocol.
In this talk we consider two problems: majority and leader election. In majority each agent starts with one of two possible opinions. The goal is to reach a configuration where all agents agree on the initial majority opinion. In leader election all agents start in the same initial state and the goal is to converge to a configuration where exactly one agent is in a distinct leader state.
Complexity measures of interest are the convergence time and the required states per agent. I am going to present an overview of current results.

KONSTANTIN MÖLLERS (Universität Hamburg)
May 23, 2017, 2:15 PM, G-203

Ein grafisches Metamodellierungsframework für das Web angewandt auf Backend-as-a-Service-Systeme

Außerhalb des Web setzen Forschung und Wirtschaft für ihre Projekte domänenspezifische Modellierung ein, welche das Generieren von ausführbarem Quelltext anhand eines grafischen Modells erlaubt. Daher existieren dazu viele desktopbasierte Ansätze in der Literatur. Betrachtet man hingegen Web-Applikationen, so ist festzustellen, dass ein Mangel solcher Ansätze besteht. Insbesondere grafische Ansätze fehlen, da die Browsertechnologie bisher noch nicht die Möglichkeit eröffnete, interaktive CAD-Anwendungen für das Web auszuführen. Einen solchen Ansatz zu schaffen ist vor allem in Hinblick auf ServerlessArchitekturen heutiger CloudPlattformen wichtig. Daher wird das Metamodellierungsframework „Metagram“ nach heutigen Web-Standards realisiert, welches domänenspezifische Modellierung im Web ermöglicht. Es stellt eine grafische Bedienoberfläche zur Verfügung mit der im Browser Modelle gezeichnet werden können, um daraus ausführbaren Code generieren zu lassen. In dieser Arbeit wird gezeigt, wie dieses Metamodellierungsframework umgesetzt wird und mit welcher grafischen Metamodellierungssprache es arbeitet. Es wird ein Anwendungsfall vorgestellt, bei dem das Framework in Orestes, ein Backend-as-a-Service-System, eingebaut und benutzt wird. Außerdem werden der produktive Einsatz, Skalierung und Erweiterbarkeit des Frameworks evaluiert. Das Metagram-Framework erlaubt der Orestes-Plattform in Zukunft, ihre Schemamodellierung durch eine grafische Schnittstelle zu verbessern und Codegenerierung zum Einsatz zu bringen, was Benutzerfreundlichkeit erhöht und Möglichkeiten für neue Funktionen eröffnet.

DOMINIK KAASER (Universität Hamburg)
May 9, 2017, 2:15 PM, G-203

Towards Rapid Asynchronous Plurality Consensus

We consider distributed plurality consensus in a complete graph of size n with k initial opinions. We design an efficient and simple protocol that ensures that all nodes eventually agree on the initially most frequent opinion in the following asynchronous communication model. In our model, each node is equipped with a random Poisson clock with parameter lambda=1. Whenever a node's clock ticks, it samples some neighbors, uniformly at random and with replacement, and adjusts its opinion according to the sample.

Distributed plurality consensus has been deeply studied in the synchronous communication model, where in each round, every node chooses a sample of its neighbors, and revises its opinion according to the obtained sample. A prominent example is the so-called two-choices algorithm, where in each round, every node chooses two neighbors uniformly at random, and if the two sampled opinions coincide, then that opinion is adopted. This protocol is very efficient and well-studied when k=2. If k=O(n^epsilon) for some small epsilon, we show that it converges to the initial plurality opinion within O(k log n) rounds, w.h.p., as long as the initial difference between the largest and second largest opinion is Omega(sqrt(n log n)). On the other side, we show that there are cases in which Omega(k) rounds are needed, w.h.p.

One can beat this lower bound by combining the two-choices protocol with push-pull broadcasting. The main idea is to divide the process into several phases, where each phase consists of a two-choices round followed by several broadcasting rounds. This, however, is difficult to realize in an asynchronous model, as we can no longer rely on nodes performing the same operations at the same time.

Our main contribution is just that: a non-trivial adaptation of this approach to the above asynchronous model. If the support of the most frequent opinion is at least (1+epsilon) times that of the second-most frequent one and k=O(Exp(log n / log log n)), then our protocol achieves the best possible run time of O(log n), w.h.p. Key to our adaptation is that we relax full synchronicity by allowing o(n) nodes to be poorly synchronized, and the well synchronized nodes are only required to be within a certain time difference from one another. We enforce this “sufficient” synchronicity by introducing a novel gadget into the protocol. Other parts of the adaptation are made to work using arguments and techniques based on a Pólya urn model.

THOMAS SAUERWALD (University of Cambridge)
April 12, 2017, 3:00 PM, G-021

On coalescence time in graphs – When is coalescing as fast as meeting?

Coalescing random walks is a fundamental stochastic process, where a set of particles perform independent discrete-time random walks on an undirected graph. Whenever two or more particles meet at a given node, they merge and continue as a single random walk. The coalescence time is defined as the expected time until only one particle remains, starting from one particle at every node. Despite recent progress such as by Cooper et al. and Berenbrink et al., the coalescence time for graphs such as binary trees, d-dimensional tori, hypercubes and more generally, vertex-transitive graphs, remains unresolved.
We provide a powerful toolkit that results in tight bounds for various topologies including the aforementioned ones. The meeting time is defined as the worst-case expected time required for two random walks to arrive at the same node at the same time. As a general result, we establish that for graphs whose meeting time is only marginally larger than the mixing time (a factor of log²n), the coalescence time of n random walks equals the meeting time up to constant factors. This upper bound is complemented by the construction of a graph family demonstrating that this result is the best possible up to constant factors. For almost-regular graphs, we bound the coalescence time by the hitting time, resolving the discrete-time variant of a conjecture by Aldous for this class of graphs. Finally, we prove that for any graph the coalescence time is bounded by O(n³). By duality, our results give bounds on the voter model.

CHRISTINA KOLB (Universität Paderborn)
March 24, 2017, 3:00 PM, G-203

Hybrid Communication Networks with Holes - How to route in unknown graphs?

Think of you having a contract with a smartphone provider. This contract offers a fixed Internet volume that is available for free, but that volume is rather small, so you want to use it as scarcely as possible. How can we use some of the Internet volume only in order to exchange control information, such as the current geographic positions of your friends or the location and dimension of radio holes (i.e., areas with no participants)? And how efficiently would that be?
In this talk, we present first ideas to answer the questions above by setting up a so-called hybrid communication network between you and your friends as participants in order to find routes for WLAN communication.

2016


EVA MÜLLER (Universität Hamburg)
November 29, 2016, 4:00 PM, G-203

Bereitstellung eines JavaScript-basierten Frameworks für die Entwicklung von agentenorientierten Webanwendungen

Der Vortrag beinhaltet die Motivation des Themas, die Vorstellung des Frameworks und eine Live-Demo.

CHRISTIAN RÖDER (Universität Hamburg)
November 22, 2016, 3:00 PM, G-203
Abschlussvortrag Diplomarbeit

Entwicklung eines Netzplantechnik-Plugins für Renew und
eine prototypische Einbettung von Netzplantechnik in den PAOSE-Softwareentwicklungsansatz

MARTIN WINCIERZ (Universität Hamburg)
November 22, 2016, 4:00 PM, G-203
Bericht AOSE-Masterprojekt

Automatisiertes Testen von Petrinetzen mit JUnit

Petrinetze werden bereits, z.B. im Rahmen von PAOSE, zum Programmieren eingesetzt. Dies bringt einen Bedarf an Tests mit sich. Für das automatisierte Testen bietet es sich an, auf vorhandene frameworks wie das weit verbreitete JUnit zurückzugreifen.
In diesem Vortrag soll ein neuer JUnit TestRunner vorgestellt werden, der das einfache Starten und Ausführen von Netzen im Renew Petrinetzsimulator erlaubt, sowie dessen Erweiterung um ein simples Verfahren zum Starten beliebig vieler nebenläufiger Tests mit unterschiedlichen Startparametern.

ALEXANDER SCHMIDT (Universität Hamburg)
November 13, 2016, 3:00 PM, G-203
Abschlussvortrag Diplomarbeit

Integration von ActiveMQ in eine Petrinetz-basierte Agentenumgebung

Die verteilte Ausführung von Software bringt viele Vorteile mit sich, die sich innerhalb einer durchdachten und funktionierenden Infrastruktur nutzen lassen. Verteilung ist ein zentraler Bestandteil der agentenorientierten Softwareentwicklung. Diese ist darauf spezialisiert, Aufgaben und Prozesse durch Interaktion von unabhängigen Softwarekomponenten abzuarbeiten. Diese Agenten sind auf eine Infrastruktur angewiesen, die sie bei der Kommunikation mit anderen Agenten unterstützt.

Das Multiagentensystem Mulan und die Plattformarchitektur Capa bieten Agenten eine Umgebung, die verteiltes Lösen von Aufgaben ermöglicht und zur Entwicklung verteilter Software eingesetzt wird. Doch auch diese Umgebung lässt sich weiterentwickeln. So soll im Rahmen dieser Arbeit die Verwendung von ActiveMQ, einer Implementation des Java Message Services, in Capa untersucht werden. Dazu werden mehrere Prototypen entwickelt, die Funktionen von Capa und ActiveMQ kombinieren.

GEORGE GIAKKOUPIS (IRISA/INRIA Rennes)
November 8, 2016, 2:15 PM, G-203

Amplifiers and Suppressors for the Moran Process on Undirected Graphs

We consider the classic Moran process modeling the spread of genetic mutations, as extended to structured populations by Lieberman et al. (Nature, 2005). In this process, individuals are the vertices of a connected graph. Initially, there is a single mutant vertex, chosen uniformly at random. In each step, a random vertex is selected for reproduction with a probability proportional to the its fitness: mutants have fitness $r>1$, while non-mutants have fitness~$1$. The vertex chosen to reproduce places a copy of itself to a uniformly random neighbor, replacing the individual that was there. The process ends when the mutation either reaches fixation (i.e., all vertices are mutants), or gets extinct. The principal quantity of interest is the probability with which each of the two outcomes occurs.

A problem that has received significant attention recently concerns the existence of families of graphs, called strong amplifiers of selection, for which the fixation probability tends to 1 as the order of the graph increases, and the existence of strong suppressors of selection, for which this probability tends to 0. For the case of directed graphs, it is known that both strong amplifiers and suppressors exist. For the case of undirected graphs, however, the problem has remained open, and the general belief has been that neither strong amplifiers nor suppressors exist. In this talk we disprove this belief, by providing the first examples of such graphs. Both examples are surprisingly simple. Moreover, our strong amplifier is existentially optimal.