Distributed Systems

Bachelor Projects

Software Verification for Data Processing Pipeline

Supervisor: Mostafa Hadadian.
Status: available.
Date: 10/01/2022.
Software verification ensures that specific software components or subsystems meet their design requirements. It is done at the design time. On the other hand, data processing pipelines are composed of several data processing elements that are connected together, i.e. an output of one element is an input for another one, to produce the expected result. This project aims to use software verification techniques to verify the design of a data processing pipeline.

Automated Planning of Data Processing Pipeline

Supervisor: Mostafa Hadadian.
Status: available.
Date: 10/01/2022.
Planning is the reasoning side of acting. It is an abstract, explicit deliberation process that chooses and organizes actions by anticipating their expected outcomes. This deliberation aims at achieving some pre-stated objectives. Automated planning is an area of artificial intelligence (AI) that studies this deliberation process computationally. This project aims to use these automated planning techniques to create a system that automatically designs data processing pipelines which are consisted of several building blocks working together to produce the expected result.

Applications of Trusted Execution Environments (TEE) in IoT

Supervisor: Majid Lotfian Delouee.
Status: available.
Date: 07/01/2022.
Employing a Trusted Execution Environment (TEE) is considered as a way of protecting the security and privacy of data. In fact, a trusted execution environment is a secure and isolated environment that prevents unauthorized access or modification of applications and data while they are in use. In this research project, students are asked to elaborate on the main features as well as the pros and cons of TEEs. In addition, it is expected to perform research on the applications of TEEs on the Internet of things environments and how can they provide an acceptable level of privacy for application users. Finally, students are expected to propose novel ideas to employ TEE in the Internet of Things environment (e.g., at the edge layer) in order to preserve privacy efficiently.

Finite state automata for TCAM packet classification

Supervisor: Saad Saleh.
Status: available.
Date: 13/12/2021.
Ternary content addressable memory is one of the crucial network memory with high power consumption and large space requirements. At the same time, it can perform network packet classification in a single clock cycle without any error. In this project, we aim to develop and analyze a finite state automata for TCAM to perform network packet classification. This project drives motivation from the use of Cognitive materials, i.e., memristors, inside TCAM. As memristors can provide a range of states with varying input-output response, so, this project focuses on the development of network packet classification technique using a range of states in a finite state automata.

Modeling and analysis of process models using Colored Petri nets

Supervisor: Heerko Groefsema.
Status: available.
Date: 26/10/2021.
Petri nets are mathematical models that can be used to model distributed systems. In our research, we use XML-based Place/Transition nets to obtain verifiable models of business processes. To increase expressivity, we are interested in support for Colored Petri nets. In this project, the student will investigate Colored Petri nets, design and implement Colored Petri nets using the Petri Net Markup Language, and implement its semantics.

Model checking st-t-t-tutter equivalent system models

Supervisor: Heerko Groefsema.
Status: available.
Date: 26/10/2021.
Verification entails proving or disproving the correctness of a system model with respect to its specification. One approach towards verification is model checking. In our research, we use model checking to verify process models against multiple sets of formal specifications based on atomic propositions. Often, however, within these different sets of specifications we are only interested in certain sub-sets of atomic propositions. Therefore, to optimize model checking performance, we are interested in obtaining multiple stutter equivalent sub-models of the given system model that only contain states with certain atomic propositions and minimal paths between those states. In this project the student will investigate system models and the concept of stutter equivalence, and design a data structure that contains the system model and its stutter equivalent sub-models, such that states are never duplicated while stutter equivalent paths in the sub-models easily map back to the respective states in the system model.

The BPMN token game

Supervisor: Heerko Groefsema.
Status: available.
Date: 26/10/2021.
The Business Process Model and Notation (BPMN) is the de facto industry standard for modeling and executing business processes. In research, however, it is common to model business processes using Petri nets, which use a token game for its execution semantics. In this project, the student is asked to bridge this gap by designing and implementing the BPMN standard and its semantics as such a token game.

Reducing Redundant Exploration of Parallel Search Algorithms

Supervisor: Michel Medema.
Status: in progress (unavailable).
Date: 25th of November 2021.
Finding the optimal solution to a Constraint Satisfaction Problem is an NP-complete problem, meaning that, in the worst case, the time complexity of a search algorithm grows exponentially with respect to the size of the problem. Many techniques have been developed to reduce the search space, including constraint propagation and pruning based on a bound on the cost. Besides that, parallel search algorithms can be used to explore multiple solutions in parallel, thereby potentially reducing the overall search time. Parallel search algorithms may potentially perform some redundant search, however, as it is not always possible to make the most effective use of pruning techniques. This redundant search may occur because, unlike sequential algorithms that can use the upper or lower bound on the cost to disregard subsequent solutions, a parallel algorithm may have already started to explore such solutions before the bound is known. The impact of this problem becomes considerably worse when the search is distributed and involves many local decisions without any global coordination, such as when the algorithm uses decomposition techniques. This project aims to explore the influence that this redundant search has on the overall execution time of the algorithm and possible techniques that can be used to avoid it, at least partially.

Decomposition Techniques for Optimisation Problems

Supervisor: Michel Medema.
Status: available.
Date: 25th of November 2021.
Decomposition techniques try to divide a Constraint Satisfaction Problem into independent subproblems based on the dependencies that exist between the variables. The decomposed problem often has a lower worst-case complexity than the original problem, and finding a solution to the problem is generally faster. One such algorithm is Backtracking with Tree-Decomposition, which applies standard backtracking search on the decomposed version of a problem. However, this algorithm was originally designed to solve satisfaction problems rather than optimisation problems, meaning performance results are not available for optimisation problems. The evaluation of Backtracking with Tree-Decomposition on optimisation problems is the focus of this project, as well as comparing these results to other constraint solvers and decomposition techniques.