Resilience of Networks against random node faults is an important property of communication networks and distributed systems. While there exist parameters such as Graph expansion, which can be used as measures for connectivity and routing capabilities, they often do not suffice to characterize the robustness of a network under random node failures.To address this, Bagchi et al., in their paper ”The Effect of Faults on Network Expansion” have…
Im Rahmen dieser Bachelorarbeit werden drei Algorithmen zur Graphrekonstruktion untersucht. Diese werden zunächst praktisch umgesetzt und auf zufällig generierte, ungerichtete und zusammenhängende Graphen angewendet. Dabei werden Daten erhoben über die Laufzeit, den Speicherbedarf und die Genauigkeit der Algorithmen. Die gesammelten Daten werden ausgewertet und miteinander verglichen, um beurteilen zu können, welche Algorithmen hinsichtlich…
We study centralized reconfiguration problems for geometric amoebot structures. A set of $n$ amoebots occupy nodes on the triangular grid and can reconfigure via expansion and contraction operations. We focus on the joint movement extension, where amoebots may expand and contract in parallel, enabling coordinated motion of larger substructures. Prior work introduced this extension and analyzed reconfiguration under additional assumptions such as…
The decomposition of complex structures into "simpler" substructures is a powerful technique with a wide range of applications. We study the computation of decompositions in the context of programmable matter using the amoebot model. In particular, we show how to decompose arbitrary amoebot structures into O(|H|) hole-free, geodesically convex regions within O(log n) rounds (w.h.p.), where |H| denotes the number of holes in the amoebot structure.
We present a lightweight solution for state machine replication. Specifically, we show how a simple median rule for the stabilizing consensus problem can be adapted to obtain a low-latency solution for state machine replication. Further, in our solution servers only need to maintain the part of the state machine pertaining to uncommitted commands, and clients hold certificates for each committed command. Our approach remains resilient even under…
Diese Bachelorarbeit untersucht verschiedene Datenstrukturen zur effizienten Kollisionserkennung im zweidimensionalen Raum. Dafür wurden Quadtrees, Bounding Volume Hierarchies, Uniform Grids sowie hybride Varianten in einem eigens entwickelten C++-Testframework implementiert und anhand mehrerer Szenarien hinsichtlich Laufzeit und Speicherverbrauch verglichen. Die Ergebnisse zeigen, dass es keine universell beste Datenstruktur gibt. Insgesamt…
Programmierbare Materie kann ihre physikalischen Eigenschaften (Form, Dichte, Leitfähigkeit usw.) autonom oder basierend auf Benutzereingaben verändern. Das Amoebot-Modell abstrahiert programmierbare Materie zu einem verteilten System aus kleinen, anonymen Partikeln mit lokalen Informationen, wenig Rechenleistung und limitierten Bewegungsfähigkeiten.Die Reconfigurable Circuits Extension erweitert dieses Modell, indem sie jeden Amoebot mit einer…
Understanding the fundamental performance limits of distributed graph algorithms is a central challenge in the design of large-scale systems such as Google's Pregel and Facebook's Giraph. A key theoretical parameter in this space is ShortcutQuality, which captures how efficiently the parts of a distributed network can communicate — but computing it is highly intractable in general. This thesis takes a first practical step toward that goal by…
My initial thesis presentation will show how serious games are becoming an important direction for education and how the rise of generative AI enables more personalized tutoring within serious games. This benefits both students’ learning progress and the efficient use of teacher resources. However, single GenAI solutions face limitations when used as tutoring systems in serious games. Agentic AI may address these limitations using specialized…
This presentation provides an overview of our VirtuTutor2 project group and the work over the past year. The main objective of our project was to improve the interaction between users and the virtual tutor in the serious game “VirtuChemLab” by implementing several key features, including an adaptive feedback mechanism, interactive question handling, context-aware explanations, and a system for estimating user skill levels in categories based on…
A Locally Checkable Labeling (LCL) is a specification describing a set of labels that are valid with respect to a set of conditions that characterize a local part of a solution to a global problem. Conditions can only refer to nodes and labels within a constant radius neighborhood of each node. In this talk, we will discuss local labeling schemes whose global consistency implies solutions to leader election which is a classical problem in…
Concurrency at runtime is inherently non-deterministic and Go provides strong built-in support for concurrent programming. It also offers runtime tracing tools that capture rich execution evidence, including goroutine lifecycle and scheduling events, channel operations, blocking and unblocking behaviour, and both runtime and system activity.Although this information is valuable for understanding concurrency, standard Go trace viewers often fail…
3D-Realtime-Rendering-Anwendungen wie Spiele erfordern eine stabile und vorhersehbare Framezeit, um eine flüssige Darstellung zu gewährleisten. Besonders die GPU-Framezeit stellt dabei einen zentralen Einflussfaktor dar, da sie maßgeblich von der Komplexität der verwendeten Szene abhängt.Das Ziel dieser Arbeit ist die Entwicklung eines GPU-Framezeit-Schätzers zur Abschätzung der GPU-Framezeit auf Basis ausgewählter Renderingparameter für…
Drones are increasingly used in diverse scenarios, from disaster response to temporary communication support in isolated networks. This thesis investigates a theoretical framework in which drones act as communication pathways to connect separated local networks, abstracted as nodes in a two-dimensional Euclidean space.Nodes with a certain proximity can freely communicate forming connected components (CC), while connecting distant nodes incurs a…
The thesis aims to solve graph-coloring problems within different variations of the amoebot model, an abstraction of programmable matter, where a each vertex is a assigned a color matching no neighboring color. Understanding efficient coloring using the underlying structure and restrictions of the amoebot model and comparison with other distributed algorithms is essential for developing higher level algorithms. The central question of the paper…
