Apache Spark is a popular batch processing framework that is integrated into the ASML data analytics platform. However, having multiple users share the same resources creates fairness and efficiency problems in the scheduler, where some users may receive more resources than others, or the scheduler slows down all jobs equally. Apache Spark provides a built-in fair scheduler that attempts to mitigate these issues, but cannot account for changing user environments and has been shown to slow down overall job execution. Previous literature has already proposed improvements to the Spark fair scheduler, however, it does not account for user contexts to ensure fair resource distribution among users, and does not account for task skews that are present in the Spark ecosystem.


In this work, we present User Weighted Fair Queuing (UWFQ) scheduler that can minimize the response time of jobs in Apache Spark, while ensuring that users are allocated a fair share of resources that they equally distribute among their jobs. This is done by simulating a virtual fair scheduler, and assigning the highest priority to jobs that complete the earliest in the virtual scheduler. The algorithm is an extension to Cluster Fair Queuing designed by C. Chen et al., with an added fairness layer to ensure that each user is entitled to a fair share of resources. To address the problem of task skew present in Spark, we introduce runtime partitioning that can more effectively avoid task skew by splitting them into more partitions. We implement our scheduler in the Apache Spark framework and show that UWFQ with runtime partitioning can decrease the average response time of small jobs by up to 70% in certain workloads, while still providing fair resource allocation in critical scenarios.

Organisations are increasingly adopting Microservice and Service-Oriented Architectures, moving from monolithic applications to (service-oriented) distributed systems. By their nature, distributed systems are prone to partial failures, where a subset of processes fail while others continue to operate. To assess the behaviour of the system when subjected to partial failures, we can inject faults that mimic partial failures. By automatically injecting all relevant combinations of faults, we can verify the system’s resilience or uncover resilience bugs. However, the search space consisting of all combinations of faults grows exponentially. Moreover, it requires significant engineering effort to adjust systems to work with existing state-of-the-art tools. This work investigates a practical approach to automated fault injection for service-oriented distributed systems while remaining efficient. We design a novel automated fault injection tool that uses network-level instrumentation to inject faults. By using an abstraction to model the system’s behaviour, we can dynamically infer information available to service-level instrumentation. Furthermore, we efficiently represent the search space as a search tree and prune it using multiple pruning policies. To evaluate our design, we developed an implementation of this design called Reynard. Compared to the current state-of-the-art, we show that Reynard is efficient, requiring equal or fewer states in the search space, has minimal overhead, and can be integrated into various existing benchmark systems with a feasible engineering effort. Furthermore, we demonstrate the applicability of Reynard by integrating it into an industry system, highlighting that it can run practical experiments and can identify real bugs. In conclusion, Reynard can provide a starting point for lowering the engineering effort required to perform automated fault injection testing, while increasing the confidence in the resiliency of systems.

The decentralized nature of blockchain systems makes them prone to concurrency bugs, which are difficult to detect. There exist testing techniques to find these bugs, such as systematic exploration of the solution space, but these techniques are difficult to scale. Evolutionary algorithms have been proposed as an effective solution to find these bugs. In this research, we aim to discover the influence of evolutionary operators in the bug detection performance of evolutionary algorithms. We test this on the XRP Ledger Consensus Protocol (XRP LCP) using priority-based event representation. We present Groot, an evolutionary algorithm that is implemented using a modified version of the Rocket framework. We experimented with two combinations of operators: the Simulated Binary Crossover (SBX) operator with the Gaussian mutation operator and the Laplace Crossover (LX) operator with the Makinen, Periaux and Toivanen Mutation (MPTM) operator. We evaluated these setups using effectiveness and efficiency and compared them to a random baseline. We used a bug-seeded version of the XRP LCP to run the experiments of these setups. We discovered that all setups are capable of detecting bugs in the XRP LCP. The results indicate that the effectiveness and efficiency is not influenced by the choice of these operators in a significant way. We discuss that possible reasons for these discoveries include noise in the fitness function, event representation limitations and configuration choices that may have contributed to these results.

The XRP Ledger (XRPL) relies on a Byzantine fault-tolerant consensus algorithm to ensure global agreement on transactions across distributed nodes. Despite its critical financial role, the implementation remains under-tested. While prior work has shown the potential of evolutionary testing to uncover potential consensus violations in XRPL, the role of genetic operator selection in this process remains unexplored. We address this research gap by presenting a comparative evaluation of four evolutionary configurations that differ in their balance of exploration and exploitation. The system is tested by injecting network delays to simulate adverse conditions and trigger violations. Our results show that the balance of exploration and exploitation affects the performance of bug detection: configurations that favor exploitation, complemented by subtle exploration, yield the most favorable results. In addition, we contribute an extensible testing method tailored to XRPL but applicable to other distributed systems.

The XRP Ledger Consensus Protocol is a Byzantine fault-tolerant algorithm that enables the XRP Ledger to reach agreement on which transactions to apply, supporting millions of transactions daily. While the protocol is correct by design, its practical implementation is vulnerable to concurrency-related bugs triggered by nondeterministic message delivery between distributed validator nodes. These bugs are subtle and difficult to expose through conventional testing. In this paper, we investigate the use of evolutionary concurrency testing combined with a priority-based message scheduling strategy to explore different message interleavings. Specifically, we evaluate multiple fitness functions and assess their ability to guide the search toward buggy executions. Our results show that EvoPriority, which applies evolutionary testing to priority-based schedules, is difficult to guide toward buggy executions regardless of the fitness function used. Although it is capable of uncovering violations on a bug-seeded versions of the XRP Ledger Consensus Protocol, its performance is similar to randomized concurrency testing.

Distributed systems, such as blockchains, can have bugs around edge-cases that are hard to detect or trigger. Previous publications have introduced guided-search testing approaches that are able to find edge cases more efficiently than through conducting a systematic and exhaustive search. In this paper, we compare the effectiveness of fitness functions in evolutionary testing frameworks. For this we evaluate time and proposal fitness. While evolutionary testing frameworks are not new to the domain of concurrency testing consensus algorithms, the impact of the fitness functions that underpin them remains poorly understood. We use the XRPL consensus algorithm as a case study to evaluate the fitness functions using the Rocket testing framework. For this, we make use of seeded versions of XRPL. All evaluated fitness functions have been able to detect the bugs we seeded in the source code of the XRPL consensus algorithm. We show the validity of various fitness functions in trying to find the bug and analyze effects in the interplay between the time and proposal fitness functions we examine.

Blockchain systems rely on consensus protocols to ensure agreement among nodes even in the presence of malicious or faulty nodes. A consensus protocol that provides safety and liveness guarantees under such conditions is known as a Byzantine fault‑tolerant (BFT) protocol. Various whitepapers describe the design and implementation of BFT protocols, providing formal proofs of their safety and liveness properties. However, in practice such protocols are difficult to implement correctly and often contain subtle logic errors that cause consensus violations. Ensuring correctness is especially important for the XRP Ledger—a public, decentralized blockchain that processes transactions for the widely used cryptocurrency XRP. Thorough testing of consensus protocols is crucial, but systematic testing is challenging and time-consuming due to the large number of possible network and timing configurations.
In this paper, we present a replication package for evaluating randomized Byzantine fault tolerance testing on the XRP Ledger Consensus Protocol (LCP). We implement the ByzzFuzz search algorithm and compare it to naive random testing. Additionally, we investigate the impact of different hyperparameter configurations on the performance of the ByzzFuzz algorithm. Our experimental results demonstrate that both naive random testing and the ByzzFuzz algorithm detect seeded bugs in the XRP LCP, with ByzzFuzz algorithm uncovering more agreement violations. Finally, we identify the most effective hyperparameter configurations for the ByzzFuzz algorithm.

Byzantine Fault Tolerant (BFT) protocols are designed to achieve consensus even in the presence of Byzantine faults. Although BFT protocols provide strong theoretical guarantees, bugs in the implementation of the protocols can allow for malicious activity. While previous work, like Twins and Tyr, has focused on alternative methods to test BFT protocols, our work builds upon ByzzFuzz, an automated testing algorithm, which has previously identified bugs in protocols like Tendermint and Ripple. Despite its success, its effectiveness has not yet been tested on speculative BFT protocols like hBFT. This research evaluates the effectiveness of ByzzFuzz in assessing the correctness and safety of hBFT. To address this, we implemented hBFT in ByzzBench, a comprehensive framework where BFT protocols can be evaluated using ByzzFuzz and other testing algorithms. Through testing, ByzzFuzz successfully uncovered a potential violation in hBFT and detected an injected bug in the hBFT implementation. However, detecting the known violation of hBFT required a controlled environment, highlighting areas where ByzzFuzz could be improved. The findings show that ByzzFuzz is effective at identifying bugs in hBFT, while also suggesting the need for improvement to enhance its robustness and adaptability.

The reliability of Byzantine Fault Tolerant (BFT) consensus protocols is critical for the robustness of modern distributed systems, i.e., in blockchain technologies. Testing of BFT protocols is crucial, as consequences of faults in their implementation can lead to malicious users exploiting vulnerabilities, resulting in financial losses, data corruption, or system unavailability. Such incidents, as seen in real-world attacks on blockchain systems, underscore the need for rigorous testing methodologies to ensure protocol correctness and resilience under adverse conditions.

This paper evaluates the implementation of the Tendermint protocol in the ByzzBench framework using ByzzFuzz, a testing approach for BFT consensus protocols. ByzzFuzz introduces structured mutations to simulate real-world fault scenarios, enabling the identification of incorrect behavior. The main question addressed in this study is: Can ByzzFuzz detect subtle protocol faults more effectively than baseline testing methods, and how do mutation strategies influence fault detection performance?

Through extensive testing, ByzzFuzz successfully uncovered violations in the Tendermint implementation, demonstrating its capability to detect subtle protocol faults. A comparative analysis with baseline testing methods revealed that ByzzFuzz provides greater fault coverage, identifying nuanced issues that the baseline approach missed. Furthermore, the study evaluated the effectiveness of small-scope and any-scope message mutations, where they change a value incrementally and arbitrarily respectively. This study found that small-scope mutations perform better in finding faults.

Testing Byzantine Fault Tolerant (BFT) algorithms is crucial in uncovering potential liveness and safety violations for distributed systems. This pa- per focuses on testing Zyzzyva with ByzzFuzz and Twins and evaluating their performance with each other and a baseline testing strategy. We also inves- tigate if ByzzFuzz can uncover faults in Zyzzyva, and how small-scope mutations compare to any- scope mutations. We also discuss limitations with ByzzFuzz when it comes to testing BFT protocols. We find that ByzzFuzz is currently unable to find known safety violations in Zyzzyva, but can find injected violations and Twins does not find viola- tions given our small sample size.

Byzantine fault-tolerant protocols have been around for decades, offering the guarantee of agreement on a correct value even in the presence of arbitrary failures. These protocols have become a critical part of achieving consensus in distributed systems and are widely used nowadays. As such, we should aim to ensure the correct functioning of these systems and one essential step to take in this direction is by finding systematic and automatic ways to test BFT protocols. This paper evaluates the performance of ByzzFuzz, an automatic testing framework designed to find bugs in the implementation of Byzantine fault-tolerant protocols through randomized testing. In that sense, we evaluate ByzzFuzz’s ability to find bugs in our implementation, compare its method of injecting network and process faults to a baseline method that arbitrarily injects faults and compare the performance in bug detection of small-scope and any-scope message mutations. We implemented the ”Fast Byzantine Consensus” protocol and employed ByzzFuzz to evaluate the framework’s capability of finding implementation bugs. We materialized a liveness violation previously uncovered in a theoretical analysis research.

Although Byzantine Fault Tolerant (BFT) protocols such as HotStuff are nominally resistant to a number of faulty or unreliable participants, implementation or design errors can cause violations in their expected properties. Because of this, it is useful to have reliable automated testing frameworks that can simulate Byzantine behaviour to make bug detection easier. In this paper, we examine the performance of the ByzzFuzz BFT testing tool using our implementation of the HotStuff protocol. We describe the design choices necessary to create a working HotStuff implementation. Then we purposefully introduce implementation flaws to evaluate the behaviour of ByzzFuzz with different parameters and mutation scopes. We compare its performance to that of a baseline random fault injection scheduler. Our results show that it was able to detect the introduced bugs using either process or network faults. ByzzFuzz's partition-based network faults were more effective at detecting bugs than the 'Random' scheduler's network faults. For process faults, we were unable to register significant differences in performance possibly due to HotStuff's simplistic pipelined structure. In our tests, any-scope mutations performed better than their small-scope counterparts for the same configuration. This could be attributed to the nature of the selected faults and HotStuff's pipelined structure.

Fuzzing has been a popular approach in the domain of software testing due to its efficiency and capability to uncover unexpected bugs. Fuzz testing was originally developed in the days of sequential programs. With the rise of multi-core devices and increasing demand for computational efficiency, the prevalence of concurrent programming has led to a new wave of research applying fuzz testing techniques. In recent years, several fuzzers have been proposed for sequentially consistent multi-threading programs, a subset of concurrent programs, using thread interleaving semantics. However, exploration of fuzzing techniques for weak memory concurrency remains limited. This thesis presents a novel fuzzing approach for programs under weak memory models. It generates test cases as execution graphs instead of thread schedules, and performs mutations on the execution graphs to generate new test cases. We implement the fuzzer based on two state-of-the-art testing tools: C11Tester and GenMC. Different mutation strategies are explored for comparison. Benchmark results demonstrate that our fuzzer explores a broader range of execution graphs compared to naive random testing, resulting in improved bug detection.

Conflict-free replicated data types (CRDTs) offer high-availability low-latency updates to data without the need for central coordination. Despite the current vast collection of CRDTs, few works have been done on maintaining probabilistic membership information using CRDTs. In this thesis, we fill the gap by proposing conflict-free replicated probabilistic filters (CRPFs). The CRPFs provide probabilistic guarantees similar to that of the Bloom filter and the cuckoo filter, and allow for concurrent updates implementing grow-only and observed-remove semantics. We check their correctness by both paper proof and software verification. Our experiments demonstrate the performance of CRPFs in real-world settings regarding the empirical false positive rate and memory consumption.

Even though much research has been conducted on body worn sensors, little research has been performed on specialized (non-ear-worn) headworn sensors. These sensors could be used to perform a variety of health related research. Therefore, this thesis focusses on a new low-power specialized (non-ear-worn) headworn sensor platform and explores how it can be improved.

This thesis addresses the challenge of refactoring untyped actor systems into typed ones, particularly within the Scala ecosystem using Akka framework \cite{akkaTypedDocs/Online}. The actor model, with its message-passing architecture, offers a solution to concurrency and scalability issues in distributed systems, but transitioning from untyped Akka Classic to typed Akka actors is a complex and error-prone task. This work proposes a solution through the development of a communication flow graph that captures actor interactions and message exchanges, which is then used to automate the refactoring process while preserving system behavior and communication integrity.

Key contributions include the implementation of the communication flow graph and an automated refactoring tool that translates untyped actor systems to typed ones. The evaluation demonstrates that while the refactored systems maintain communication patterns and functionality, they may introduce a slight reduction in maintainability. Additionally, the resulting effectiveness of the refactored benchmarks varies depending on the complexity of the underlying system.

Lastly, this research sets the foundation for improving refactoring tooling aimed at actor systems, extending the usability of the communication flow graph for the automated documentation of actor systems, and highlights the need to revisit traditional software quality metrics to suit actor-based systems.

Asynchronous programming is often a difficult and non-trivial task. To make asynchronous programming more straightforward, languages are continuously introducing new syntax and patterns, making it easier to think about and develop solutions for concurrent problems.
JetBrains introduced coroutines for Kotlin in 2018. Although Kotlin coroutines promise safe execution and concise code, it is not immune to concurrency bugs such as deadlocks. Particular runBlocking deadlocks are common when working with Kotlin coroutines. While other languages have made various advancements in detecting deadlocks, Kotlin lags behind.

In this work, we present two static analysis techniques that help developers detect and prevent deadlocks. The first technique, focused on the runBlocking problem, successfully identified dangerous patterns in open source repositories, leading to their resolution. Additionally, this technique has been integrated into JetBrains flagship IDE: IntelliJ IDEA. The second technique, aimed at general deadlock detection, has been developed and tested as a prototype. By using existing modeling techniques combined with novel approaches we have been able to accurately predict deadlocks in a controlled environment. Overall, this study tackled a common problem in Kotlin coroutines and made the first steps toward general deadlock detection.

Serverless computing has allowed developers to write pieces of code comprising solely of the necessary functionality whilst not having to think about the underlying infrastructure. One prominent model is Function-as-a-Service (FaaS), where the code is structured into functions that run based on incoming events. This model was initially stateless, as new function calls can be instantiated at any location and there is no clear consensus on state whenever multiple instances are running simultaneously. Access to external persistent state is slow, making FaaS not suitable for low latency applications. Recent works have found different ways of incorporating state, resulting in Stateful FaaS (SFaaS). With the addition of state, these components are perfectly suited for distributed transactions. SFaaS frameworks try to outperform one another on metrics such as throughput and latency, but less work is performed on consistency.

In this thesis we look at the work on consistency of SFaaS transactions that has been done. We take Jepsen, a framework for testing transactions in distributed systems, and show that it can also be applied to SFaaS transactions. We then proceed to apply it to three SFaaS frameworks. We use Elle as a consistency checker to verify that the three frameworks comply with the consistency level they are advertised as. We have found that two of the tested frameworks do not have the consistency level promised. Facets of the SFaaS frameworks seem to have been overlooked, and diverging from the laid out benchmarking path quickly results in unintended behaviour.

The testing of consensus systems has received growing attention and recent testing tools generate many faulty executions. However, there is a lack of methods that automatically analyze these outputs to identify the root causes of the bugs they found.
This paper presents Isolation, a statistical bug isolation algorithm that uses message-based predicates to discriminate between different faults. We applied our method to executions of the XRP Ledger blockchain and evaluated its performance. Our comparison shows that Isolation correctly separates bugs by their root cause and consistently outperforms the state-of-the-art with higher F-scores.

Concurrency bugs are easy to introduce but dif- ficult to detect, especially in implementations of distributed algorithms where concurrency non- determinism is an inherent problem. These bugs may only be identified under very specific order- ings of execution events, making them challenging to reproduce. Controlled concurrency testing tech- niques have been proposed to address the testing challenge, by taking over the scheduling of events, and effectively searching the state space of sched- ules to identify the concurrency bugs.
In this paper, we investigate and compare the per- formance of two concurrency exploration algo- rithms, probabilistic concurrency testing (PCT) and delay bounding strategy on our implementation of the HotStuff consensus protocol, which has been quite popular and was adopted by Meta for its Diem blockchain project. Our results suggest that can in- deed find concurrency bugs more frequently in our HotStuff implementation than the baseline random strategy. However, using different bound parame- ters for PCT and delay bounding does not have sig- nificant effect on bug finding performance on our benchmarks.