Oberseminar SS 2024
17.04.2024, 14:00 Uhr, F2.419,
Vortragender: Sebastian Korzeczek (Master)
Title: Shape Formation with Passive Objects and Joint Movements in the Amoebot Model
Abstract: In the shape formation problem, the goal is to transform an initial shape into a given target shape. The scale of the formed target shape is maximal with respect to the number of passive objects in the initial shape. Such an algorithm was formalized in the Amoebot Model with joint movements and partially implemented in the AmoebotSim2.0 simulation environment. The shape formation algorithm presented here is capable of forming the target shape in O(m^2) rounds, where m is the number of passive objects in the initial shape.
24.04.2024, 14:00 Uhr, F2.419,
Vortragender: Matthias Artmann (Master)
Title: On the Shape Containment Problem within the Amoebot Model with Reconfigurable Circuits
Abstract: Programmable matter is envisioned as a material that can alter its physical properties
(shape, conductivity, appearance etc.) and react to external stimuli intelligently to
fulfill a large variety of tasks in construction, maintenance, medicine and other
application domains. Such materials are often imagined as large numbers of small
computational entities, called particles, with very limited sensing, communication and
movement abilities. By modeling programmable matter as distributed systems, we can study
its theoretical capabilities and limitations under varying assumptions and independent of
physical implementations.
The problem of shape formation, i.e., reorganizing an arbitrary initial configuration of
particles into a desired shape, has been studied extensively in various models due to its
high practical relevance. We consider the related problem of shape containment, where the
particles have to find the maximum scale at which a given shape can be represented by the
initial configuration (i.e., without movement) and identify a subset of particles
representing the maximally scaled shape. A shape containment solution could serve as a
preparation for fast shape formation algorithms or other complex procedures, but the
problem has not been studied in the context of programmable matter so far.
In this master's thesis, we present solutions to the shape containment problem in the
amoebot model, using the model's reconfigurable circuits extension to enable fast
communication over long distances. In addition to a solution of the most general problem
case, we identify several classes of shapes and initial configurations with more
efficient solutions, achieving sublinear runtimes in the number of particles. The final
presentation of this thesis gives an overview of the considered problem cases and
presents the key algorithmic ideas used to solve these cases efficiently.
08.05.2024, 14:00 Uhr
Vortragender: Dominik Delgado Steuter (Bachelor)
Title: Realizing Concurrency on Top of the Microkernel seL4 via Improved Threads
Abstract: What is the best way to make programs concurrent? How can threads be made more efficient and easier to use? In this paper, threads and the event model are compared for realizing concurrency in programs and opportunities for improvement of threads are presented. The microkernel seL4 is showcased and the threads it provides are implemented and analyzed regarding their ease of use and performance. Can they be improved? Also, a concurrency-optimal binary search tree is showcased and a partial implementation of it in the programming language C is discussed.
15.05.2024, 14:00 Uhr
Vortragender: Vincent Griebel (Bachelor)
Titel: Designing a financial system on a centralized blockchain with distributed backend
Abstract:Spätestens seit dem Bitcoin-Boom im Jahr 2020 haben Kryptowährungen die breite Öffentlichkeit erreicht. Doch obwohl einige Länder wie El Salvador Bitcoin sogar als offizielles Zahlungsmittel eingeführt haben, bleiben die Anwendungsmöglichkeiten eher limitiert. Gründe dafür lassen sich unter anderem in den Gegebenheiten des Bitcoin Protokolls finden. So ist die maximale Anzahl der Transaktionen auf zehn pro Minute beschränkt, und alle Transaktionsdaten sind öffentlich für jedermann zugänglich. Wie könnte man ein Zahlungsmittel schaffen, das einer Kryptowährung ähnelt, aber einige dieser Probleme löst?
In der Präsentation wird zuerst einmal Bitcoin analysiert, um zu verstehen, woher einige der Probleme kommen. Danach wird eine zentrale Blockchain konstruiert, welche keinen speziellen Konsensus Mechanismus benötigt. Zum Schluss wird noch betrachtet, wie die Beträge in Transaktionen so verschlüsselt werden können, sodass der Server die Transaktionen validieren, aber nichts weiteres über sie herausfinden kann.
26.06.2024, 14:00 Uhr
Vortragender: Varun Maitreya Eranki, Master
Titel: Fever: Optimal Responsive View Synchronisation
Abstract: In this thesis an exploration into the role of hardware and software combination for improving Byzantine Fault Tolerant State Machine systems with integration of novel Fever algorithm. The role of partial synchrony model in a consensus decision making, can improve the reliability and resiliency in the event of faults. Tolerance of such a system is explored practically in the presence of adversarial behaviour. An addition of cost effective precision clock overall improves the Fever algorithm.
17.07.2024, 14:00 Uhr
Vortragender: Andreas Padalkin
Titel: Polylogarithmic Time Algorithms for Shortest Path Forests in Programmable Matter
Abstract: In this talk, we study the computation of shortest paths within the \emph{geometric amoebot model}, a commonly used model for programmable matter. Shortest paths are essential for various tasks and therefore have been heavily investigated in many different contexts. For example, in the programmable matter context, which is the focus of this paper, Kostitsyna et al.\ have utilized shortest path trees to transform one amoebot structure into another [DISC, 2023]. We consider the \emph{reconfigurable circuit extension} of the model where this amoebot structure is able to interconnect amoebots by so-called circuits. These circuits permit the instantaneous transmission of simple signals between connected amoebots.
We propose two distributed algorithms for the \emph{shortest path forest problem} where, given a set of $k$ sources and a set of $\ell$ destinations, the amoebot structure has to compute a forest that connects each destination to its closest source on a shortest path. For hole-free structures, the first algorithm constructs a shortest path tree for a single source within $O(\log \ell)$ rounds, and the second algorithm a shortest path forest for an arbitrary number of sources within $O(\log n \log^2 k)$ rounds. The former algorithm also provides an $O(1)$ rounds solution for the \emph{single pair shortest path problem} (SPSP) and an $O(\log n)$ rounds solution for the \emph{single source shortest path problem} (SSSP) since these problems are special cases of the considered problem.
24.07.2024, 14:00 Uhr
Vortragender: Gbadamosi Damiloda, Master
Title: Implementation and Evaluation of Iterative Deepening A* Algorithm on a 3D game map.
Abstract: Path-finding algorithms are critical for developing interactive games, providing effective routes for characters to perform in virtual environments with complex scene structures. This thesis investigates the performance and suitability of three prominent path-finding algorithms: A*, Dijkstra, and Iterative Deepening A* (IDA*) which are practically applicable in a game prototype environment. This paper includes a study of six scenarios, each with difficult passages like obstacle blockages and complex terrain.
The introduction provides an in-depth explanation of the game mechanics and how the IDA* algorithm is combined with the iterative deepening procedure, demonstrating the role of the algorithm in path optimization. My strategy is to integrate the algorithms within the game layers, where significant aspects such as memory consumption, time performance, route length, and the appearance of smooth paths are considered. Visual explanation of the algorithm implementation is due to the screenshots of the coding process.
Scenario-delimited metrics from the evaluation give a detailed view of the scenarios' computational complexity. A* and Dijkstra algorithms can achieve consistently and reliably better performance as the algorithms enhance the adaptability of different gaming environments. On the other hand, IDA* demonstrates different efficiency levels when coping with scenario complexity, but there are unique improvements for the scenarios that embrace the IDA* iterative deepening strategy.
Moreover, another aspect of the analysis is the study of each algorithm's pros and cons. The advantages and disadvantages include the space and time complexity of each algorithm, heuristic function and limitations of the algorithms' optimization. The algorithm comparison reveals the usage of grid and octree in different scenes, making it easy for game developers to choose a suitable algorithm for their purpose.
The study's implications highlight the relevance of choosing algorithms according to the gaming system's environmental features. Developing an algorithm that will optimize the path-finding mechanisms and strike the right balance between computational effort and path-finding accuracy can be a task. This research is a step in the path-finding process in game development; it offers an elementary framework for further exploration and innovation in the design of interactive games.
24.07.2024, 14:45 Uhr
Vortragender: Natiq Sihab Akram, Master
Title: Anomaly Detection in N-Sensor Data for Accurate Field Mapping Using Machine Learning
Abstract: This study presents a detailed examination of anomaly detection within N-Sensor data, aiming to enhance precision agriculture by refining field boundary delineation using machine learning techniques integrated with geospatial analysis. Focusing on Yara International’s N-Sensor and Varda’s Global Field ID system, this study addresses challenges posed by redundant data through spatial joins that effectively detect farm-relevant data points and remove non-farm points, significantly improving data accuracy. Machine learning limitations were encountered, notably a high rate of false negatives due to an imbalanced dataset for non-farm points. However, applying spatial joins offers a solution for removing non-farm points, optimizing data quality, and providing better computational efficiency. Consequently, this approach supports more accurate agricultural practices.