Ober­se­mi­nar 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.

Sie interessieren sich für: