Abstract: The amoebot model is a model of the concept of programmable matter, in which tiny processors called amoebots work as distributed actors to solve problems in the global model structure. This model, along with its necessary limitations, introduces a new perspective on well-studied distributed algorithms. We mainly focus on the concept of amoebot regions, where the amoebot structure is split into many regions of amoebots, and we solve …
With the growing importance and capabilities of serious games and generative AI (GenAI), the VirtuChemLab has been fitted with a GenAI-powered virtual laboratory tutor called VirtuTutor. The role of this tutor within the simulated chemistry laboratory is to help users resolve difficulties, answer their questions, and improve learning outcomes without human supervision. In my thesis, I replaced VirtuTutor’s basic GenAI components with an agentic…
Das Kürzeste-Wege-Problem ist ein fundamentales Problem der Graphentheorie. Für den Fall der Berechnung auf Graphen mit ausschließlich positiven Kantengewichten haben sich schon länger Algorithmen etabliert, welche das Problem in nahe-linearer Laufzeit berechnen. Ein Beispiel dafür ist der Algorithmus nach Dijkstra. Werden nun Graphen mit beliebigen, sprich auch negativen Kantengewichten betrachtet, so produzieren diese Algorithmen, insbesondere…
Replication exists to eliminate single points of failure. Yet classical statemachine replication routes every command through a leader, at once athroughput bottleneck and the system's most exposed attack target. "ALightweight Approach for State Machine Replication" (Cachin, Dou, Scheideler,Schneider, 2025) instead adapts a simple median rule from stabilizingconsensus into a leaderless, gossip-based protocol with compact server state.The proven…
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…
