Oberseminar WS 2023/2024
22. November 2023, 14:00 Uhr, F2.419,
Vortragender: Julian Werthmann
Titel: Peer-to-Peer assisted Cloud Computing with malicious Peers
Abstract:
We consider a new model of distiributed computation where a powerful
computational entity (the cloud) is assisted by several potentially malicious
weaker entities (the peers). The main focus on this talk is the presentation
and analysis of a distributed mergesort algorithm for this setting.
Additionally, we will briefly discuss other problems and connections to already
established models.
06. Dezember 2023, 14:00 Uhr, F2.419,
Vortragender: Björn Beckendorf (Masterarbeit)
Titel: Self-Stabilizing Skip-Graph with Growth-bounded Metric
Abstract: In this thesis, we tackle the challenge of creating and maintaining graph structures that support efficient
routing in overlay networks with a distributed, self-stabilizing algorithm. There exist different algorithms for
several graph structures, that mostly use identifiers to build the networks. The (B,c)-Skip-Graph is based on
the well-established Skip-Graph and takes a metric and two integers B and c as parameters. The distance
between two nodes in a (B,c)-Skip-Graph is at most stretched by a factor 1 + ε. As far as we know, there is
no self-stabilizing algorithm for a metric graph with such a stretch. In this thesis, we extend the (B,c)-Skip-
Graph to the (B,c)-Skip+Graph with some additional edges to allow the construction of a self-stabilizing
algorithm for it. Our algorithm builds the graph in poly-logarithmic time from an arbitrary weekly connected
graph.
15. Dezember 2023, 17:00 Uhr, F0.530,
Vortragender: Prof. Dr. Martin Gairing, University of Liverpool, UK
Titel: Fair Interventions in Weighted Congestion Games
Abstract: In this work we study the power and limitations of fair interventions in weighted congestion games. Specifically, we focus on interventions that aim at improving the equilibrium quality (price of anarchy) and are fair in the sense that identical players receive identical treatment. Within this setting, we provide three key contributions: First, we show that no fair intervention can reduce the price of anarchy below a given factor depending solely on the class of latencies considered. Interestingly, this lower bound is unconditional, i.e., it applies regardless of how much computation interventions are allowed to use. Second, we propose a taxation mechanism that is fair and show that the resulting price of anarchy matches this lower bound, while the mechanism can be efficiently computed in polynomial time. Third, we complement these results by showing that no intervention (fair or not) can achieve a better approximation if polynomial computability is required. We do so by proving that the minimum social cost is NP-hard to approximate below a factor identical to the one previously introduced. In doing so, we also show that the randomized algorithm proposed by Makarychev and Sviridenko [JACM’2018] for the class of optimization problems with a “diseconomy of scale” is optimal, and provide a novel way to derandomize its solution via equilibrium computation.
Joint work with Miriam Fischer and Dario Paccagnan.
20. Dezember 2023, 14:00 Uhr, F2.419,
Vortragende: Jinfeng Dou
Titel: Cloud Assisted Blockchain
Abstract: We introduce the Cloud Assisted Blockchain (CAB) model, a novel approach to distributed computing that leverages the inherent characteristics of cloud environments. The primary focus is developing a scalable state machine replication (SMR) solution within a federated cloud model. The CAB model integrates various techniques, including hashing, median rule, Merkel hash tree, and the arrow protocol, to achieve consensus with less time(round) and work(message communication and transaction memories). The comprehensive model presented in this paper provides insights into the intricate balance between decentralization, reliability, and practical considerations in distributed computing scenarios.
10. Januar 2024, 14:00 Uhr, F2.419,
Vortragender: André Graute
Titel: Accelerate NeRF Rendering by Point Clouds
Abstract: Neural Rendering using Neural Radiance Fields (NeRF) is a technique that uses deep learning algorithms to create photorealistic images and videos. It is widely used in computer graphics and animation to create more realistic and lifelike images. One of the main challenges in rendering NeRF are the high computational costs, which can make it difficult to achieve real-time performance. For real-time applications, it is therefore crucial to speed up the rendering process and make it more efficient without suffering any loss of quality. Common techniques for accelerating rendering are the use of spatial data structures or approximation algorithms. In this talk, a technique will be presented that uses point clouds to both speed up rendering and improve quality.
17. Januar 2024, 14:00 Uhr, F2.419,
Vortragender: Shariq Majeed, Mastervortrag
Titel: Strengths and Weaknesses of Classical Occlusion Culling Algorithms
Abstract: This study investigates the strengths and weaknesses of classical occlusion culling algorithms on modern hardware. It focuses on how occlusion culling affects the efficiency and effectiveness of the algorithms. It also tries to dertermine the impact of occlusion queries on the final image. It compares five redenering algorithms that employ different occlusion culling strategies. Tehe algorithms elected in this study were implemented in PADrend using C++ and EScript. This study tests each algorithm, the studycompares these algorithms. The result reveals that the frame duration is not directly proportional to the occlusion queeries. However, the complexity of the scene directly affects the frame duration. The study concludes that no algorithm is significantly superior to the other.
24. Januar 2024, 14:00 Uhr, F2.419,
Vortragender: Jan-Luca Hansel
Titel: Embodied conversational agents for social virtual worlds
Abstract: Conversational agents, i.e., systems which try to emulate human dialogue, allow users to interact with automated services in a more natural way. When they appear in a virtual world in the guise of a normal user, they can increase the feeling of immersion in this virtual world. Now, to be able to conduct a multi-turn conversation with a human, a conversational agent needs a dialogue strategy. In this talk, a technique is presented which is able to enhance an initial dialogue strategy by the means of statistical methods. Furthermore, a framework for conversational agents is presented which demonstrates how a dialogue strategy is employed to build a conversational agent.
31. Januar 2024, 14:00 Uhr, F2.419,
Vortragender: Jonas Harbig
Titel: Forming Large Patterns with Local Robots in the OBLOT Model
Abstract: We consider the problem of forming an arbitrary connected pattern $P$ with $n$ robots in the \oblot model.
In this model, the (deterministic) robots are indistinguishable, have no common orientation, and cannot store past observations nor communicate with each other.
The robots receive $P \subseteq \R^2$ as a finite subset of coordinates and the goal is to place one robot at each coordinate.
Previous work considered this problem under global visibility~\cite{DBLP:journals/tcs/YamashitaS10} and limited visibility but with memory~\cite{DBLP:conf/sirocco/YamauchiY13} (robots can store past observations).
In both cases it was shown that $P$ can be formed if the robots' initial placement is not too symmetric compared to $P$.
Without memory and with limited visibility, forming such patterns remains an open problem.
We solve this setting partially by showing that any connected pattern can be formed if the robots see each other in the (not too symmetric) initial placement.
For this, we partition $P$ into suitable components that are rotation-symmetric to each other and exploit the robots' initial mutual visibility to form one cluster per component.
Using a careful placement of the clusters and their robots, we show that each cluster can move in a coordinated way through its component, dropping one robot per pattern coordinate along the way, yielding the desired pattern.
07. Februar 2024, 14:00 Uhr, F2.419,
Vortragende: Svitlana Dorociak, Bachelorvortrag
Titel: Implementierung eines Algorithmus zur motivbasierten Schnitt-Sparsifizierung
Abstract: Zahlreiche relevante Systeme der realen Welt lassen sich als Netzwerke bzw. Graphen abbilden und ermöglichen umfassende Analysen. Beispiele dafür umfassen soziale Netzwerke (z. B. Freundschafts- und Beziehungsnetzwerke), technologische Netzwerke (z. B. Energieversorgungsnetze), biologische Netzwerke (z. B. Protein-Protein-Interaktionsnetzwerke), interorganisationale Netzwerke (z. B. Netzwerke von Geschäftsbeziehungen) sowie Informationsnetzwerke (z. B. Zitationsnetzwerke).
Durch die Analyse der in realen Netzwerken häufig vorkommenden Verbindungsmuster wird ein besseres Verständnis für Netzwerkstrukturen höherer Ordnung ermöglicht. In diesem Zusammenhang gewinnen diese sogenannten Netzwerkmotive in verschiedenen Anwendungsgebieten zunehmend an Bedeutung. Eine Herausforderung besteht darin, dass Analysen komplexer Netzwerke erheblichen Rechen- und Speicheraufwand erfordern. Einen Lösungsansatz stellen Methoden zur Sparsifizierung der Graphen dar, wobei relevante Eigenschaften des ursprünglichen Graphen dabei möglichst erhalten bleiben sollten.
Im Rahmen der vorliegenden Arbeit wurde ein Algorithmus zur motivbasierten Schnitt-Sparsifizierung implementiert. Der implementierte Algorithmus wurde mit verschiedenen Werten der Parameter auf verschiedene Eingabegraphen angewendet, um seine Leistung in verschiedenen Szenarien zu überprüfen. Aus den durchgeführten Tests konnten Erkenntnisse zur Auswahl der Parameterwerte sowie der Wahrscheinlichkeit für die Kantenwahl gewonnen werden.
14. Februar 2024, 14:00 Uhr, F2.419,
Vortragender: Heena Thakur, Mastervortrag
Titel: Evaluating the Implications of AI in Healthcare, Privacy, Ethics, and Security perspective
Abstract: Artificial Intelligence (AI) is becoming one of the fastest-growing technologies in the current time. It is being used in almost all fields like the IT sector, finance sector, education sector, etc. It is slowly becoming an integral part of our day-to-day lives. It is now also becoming increasingly useful in the field of Healthcare. AI finds many uses in the healthcare sector, these include, chat-based diagnosis, drug discovery, health monitoring, etc. But unlike other sectors, where major issues cause loss of money or reputations, any issue in the field of healthcare can lead to catastrophic effects since they directly impact human life. Loss of human life is the most dangerous loss which is why we need to ensure that AI is working to benefit humans and not harm them in any way. Thus, it becomes important to understand what AI is doing when it comes to the field of healthcare. Most importantly, it needs to be ensured that AI is working in a private, secure, and ethical manner. To do this, one first needs to understand what exactly is private, secure, and ethical use of AI in healthcare. This thesis aims to do just that by highlighting various privacy, security, and ethical issues that are prevalent in AI-based healthcare. In this thesis, the AI-based strategies and techniques that have been created to overcome these issues in privacy, security, and ethics, are also briefly discussed. This thesis uses literature from various sources and creates a comprehensive overview of AI in healthcare, keeping privacy, security, and ethical aspects as the main focus.
21. Februar 2024, 14:00 Uhr, F2.419,
Vortragende: Jie Liu
Joint work with Gleb Polevoy
Title: Social Welfare, Discrepancy, and Strength -- Interconnections between properties of Nash Equilibria
Abstract: When evaluating different Nash equilibrium profiles, there are several properties that are important to consider. The most important properties include Social Welfare, which measures the overall benefit to the entire group; Discrepancy, which refers to the difference of utilities of every player; and Uniqueness, which ensures that players will be certain which strategy to use. The strength of a solution concept is crucial as well. It reveals how likely a group of players might want to deviate. Consideration of these properties is essential for selecting an optimal equilibrium for a given game.
The current literature needs a comprehensive comparison integrating these key properties, to allow for an educated comparison and selection of solution concepts.
This gap hinders the full appreciation of the implications that each refinement may have on the aforementioned metrics. Our research thus aims to bridge this gap by finding the relationship between important properties of solution concepts.
In summary, we prove that there are interconnections between properties of Nash equilibria, some stands for general cases while others only apply to certain important classes of games.
28. Februar 2024, 14:00 Uhr, F2.419,
Vortragender: Gleb Polevoy
Title: When Effort May Fail: Equilibria of Shared Effort with a Threshold
Abstract: People, robots, and companies mostly divide time and effort between
projects, and shared effort games model people investing resources in public
projects and sharing the generated values. In linear θ sharing (effort) games,
a project’s value is linear in the total contribution, thus modelling predictable
and scalable activities. The threshold θ for effort defines which contributors
win and receive their share, equal share modelling standard salaries, equity-
minded projects, etc. Thresholds between 0 and 1 model games such as paper
co-authorship and shared assignments, where a minimum positive contribu-
tion is required for sharing in the value. We constructively characterise the
conditions for the existence of a pure equilibrium for θ ∈ {0, 1}, and for
two-player games with a general threshold, and find the prices of anarchy
and stability. For more players, we also provide existence and efficiency re-
sults, and use generalised fictitious play simulations to show when a pure
equilibrium exists and what its efficiency is. We propose a novel method for
studying solution concepts by defining a new concept and proving its equiv-
alence to a previously known on a large subclass of games. This means that
the original concept narrows down to a more demanding concepts on certain
games, providing new insights and opening a path to study both concepts
conveniently. We also prove mixed equilibria always exist and bound their
efficiency. This facilitates reaching socially efficient equilibria.
13. März 2024, 14:00 Uhr, F2.419,
Vortragender: Rajesh Doddegowda (Master)
Title: Optimal Drone Strategies For Packet Delivery
Abstract: This thesis investigates a comparative analysis of heuristic algorithms and reinforcement learning for solving complex combinatorial optimization problems, particularly focusing on variants in drone-based delivery systems such as the Traveling Salesman Problem with Drones (TSP-D), the Multiple Drone Routing Problem (MDRP), and the Drone-Truck Routing Problem, using the Christofides algorithm. Recognizing the limitations inherent in basic algorithms when applied to these complex scenarios, the study proposes different heuristic methods, including the 2-opt heuristic, the Steady-state genetic algorithm, and the Christofides algorithm. Additionally, the thesis implements advanced reinforcement learning techniques, including attention-based encoder-decoder models and Long Short-Term Memory (LSTM) networks. The primary objective of this model is to enhance the coordination and routing efficiency of trucks and drones in logistics networks, taking into account critical factors like node probabilities, customer demands, and depot capacities. The thesis thoroughly tests and evaluates the efficiency, runtime, operational challenges, and cost implica- tions associated with these methods. It aims to identify an optimal balance between effectiveness and resource constraints, crucial in real-world logistics and delivery sce- narios. The findings highlight the adaptability of heuristic methods under varying conditions and underscore the potential of reinforcement learning for deeper and more complex analytical tasks. This thesis offers valuable insights into algorithm selection, tailored to the specificities of the problem and resource availability. It contributes significantly to the field by providing a comprehensive understanding of the strengths and limitations of both heuristic and reinforcement learning approaches in the context of modern, complex, and dynamic routing problems.
Keywords: traveling salesman problem with drone, multiple drone routing problem, drone-truck routing problem, reinforcement learning, neural networks.
27. März 2024, 14:00 Uhr, F2.419,
Vortragender: Carsten de Groote (Master)
Title: A Dispersion Algorithm for Robot Swarms Inside Polygonal Boundary Shapes
Abstract: We present a simple algorithm for the dispersion of n robots. Robots are tasked with distributing themselves in order to cover an area by moving away from their nearest neighbour. With only small changes the algorithm is applicable to unbounded two-dimensional space, circle-, convex polygon- and non-convex polygon boundaries. In bounded areas P, we assume n = O(Area(P)).
The algorithm is based on the assumptions of the OBLOT robot model. The robots execute the same algorithm under the Look-Compute-Move model, they are indistinguishable from another, they have no means of communication or persistent memory across executions and act only based on their local surroundings. Furthermore, the local coordinate systems of the robots are not aligned and their chirality (sense of left and right) can vary.
We provide select results about the correctness and limitations of the provided algorithms as well as hypotheses about the algorithms quality. Results are supported by extensive simulations.