Two Computer Science MSc theses to be presented on 16 May

Friday, 23 May there will be two master thesis presentations in Computer Science at Lund University, Faculty of Engineering.

The presentations will take place in E:2116.

Note to potential opponents: Register as an opponent to the presentation of your choice by sending an email to the examiner for that presentation (firstname.lastname@cs.lth.se). Do not forget to specify the presentation you register for! Note that the number of opponents may be limited (often to two), so you might be forced to choose another presentation if you register too late. Registrations are individual, just as the oppositions are! More instructions are found on this page.

10:15-11:00 in E:2116

Presenters: Klara Tjernström, Vera Paulsson
Title: A Performance Study of Priority Queues: Binary Heap, Fibonacci Heap, Hollow Heap
Examiner: Flavius Gruian
Supervisor: Jonas Skeppstedt (LTH)

This master thesis evaluates the performance of Binary, Fibonacci, and Hollow Heaps used as priority queues in Dijkstra’s algorithm, with the goal of identifying the most suitable data structure for implementation in Panasonic Avionics’ Arc application. The heaps were tested across varying graph types to determine their impact on execution time, memory access patterns, and cache efficiency. Despite its theoretically worse complexity, the Binary Heap consistently outperformed the others due to its contiguous memory layout and predictable access.. Fibonacci and Hollow Heaps suffered from pointer overhead and irregular memory usage. When used as a priority queue in Dijkstra's algorithm on a sparse graph, the Binary Heap demonstrated a speedup of approximately 70–120% over the Fibonacci Heap and about 100–170% over the Hollow Heap.

Implementations in C, Java, and Rust were compared for the Fibonacci Heap, with C showing the fastest execution. Java and Rust offered safer abstractions but introduced runtime and complexity trade-offs. Cache behavior was analyzed using Cachegrind, and exhibited that Binary Heap had the fewest cache misses. Prefetching was explored in all implementations; while it showed some benefit for minimizing L1-misses, overhead added complexity limited its overall execution time. The results demonstrate that the Binary Heap achieves the best execution time and cache performance across the evaluated graphs. Furthermore, the choice of implementation language significantly affects performance, with C yielding the lowest execution times and cache miss rates, particularly in pointer-intensive heap structures such as the Fibonacci and Hollow Heaps.

Link to popular science summary: To be added

11:15-12:00 in E:2116

Presenters: Alfred Grip, Nils Ekstrand
Title: Per-User Rate Limiting in Kafka Queuing Systems: Implementation and Design
Examiner: Michael Doggett
Supervisors: Jonas Skeppstedt (LTH), Anders Berglund Dacke (Sinch AB), Erik Gilbertsson (Sinch AB)

Demand for scalable and resilient distributed systems is growing, and implementing flexible per-user rate limiting in high-throughput queuing systems is becoming increasingly valuable. This thesis investigates the design and implementation of a distributed queuing system built on Apache Kafka that enforces per-user rate limits. We evaluate two core system components – consumer and worker strategies – across various configurations, leveraging frameworks such as LMAX Disruptor and Kafka Streams.

The performance of the systems is evaluated, and results show that although frameworks can offer simpler design and less code, they provide both pros and cons, and as such, no clear performance gain can be concluded. We also explore the trade-offs between fault tolerance and throughput, demonstrating that deterministic systems can enable robust recovery, at the cost of some performance. This work contributes to the understanding of building rate-limited queuing systems and provides insights into practical choices when developing.

Link to popular science summary: To be added