Master thesis proposal

PEPA-K and definition of block-regular stochastic models

PEPA-K is the language used in Moebius to model computer systems. Moebius is a popular tool that allows for the performance and reliability analysis of software, hardware and telecommunication systems. Moebius allows the exact analysis of product-form models, that are models which can be decomposed into simpler components and whose properties are computed efficiently. In [1] an algorithm for computing the product form solution for models whose transition diagram has a regular structure is defined. This thesis aims at defining an algorithm to check if a model definition in PEPA-K satisfies the conditions required by the models considered in [1]. Furthermore, an implementation of that algorithms and a transformation of a PEPA-K model into a format computable by the tool shown in [1] is required.

1. Andrea Marin, Samuel Rota Bulò, Simonetta Balsamo: A Numerical Algorithm for theDecomposition of Cooperating Structured Markov Processes. MASCOTS 2012: 401-410

contacts: marin@dais.unive.it srossi@dais.unive.it balsamo@dais.unive.it

Analysis of stochastic models via approximate lumping

Performance evaluation of computer systems is often based on Markov chains analysis. Several high-level formalisms have been defined to model software and hardware architectures whose underlying stochastic process is a Continuous Time Markov Chain. Nevertheless, the application of this approach for practical purposes is sometimes limited by the exponential growth of the state space. One approach to tackle this problem is known a lumping, i.e., performing an aggregation of chain’s state based on symmetries and hence one obtains a reduction of the computational complexity required to compute the system’s performance indices. The goal of this thesis is studying new ways to carry out approximate lumping of Markov chains and evaluation their precision. If the results are promising, there is the possibility of integrating the proposed algorithms in existing tools for the performance evaluation of computer systems.

For information contact: marin@dais.unive.it srossi@dais.unive.it

Evaluation of the impact of garbage collection policies in the QoS and energy consumption (assigned)

Many modern programming languages allow the programmer to allocate the memory in a simple and transparent way without the need of the explicit deallocation when it is not necessary anymore. This is achieved by means of the Garbage Collectors, i.e., special threads that use some algorithm to mark the memory blocks that are not being used by a the running processes as available. However, the drawback of this approach is twofold. First, the response time of an application using the garbage collection is generally worse than that of an equivalent that explicitly allocates and deallocates the memory because of the process time required by the garbace collection itself. Second, the algorithms used by the collectors are usually CPU-intensive and hence cause a high consumption of CPU-cycles and a consequent waste of energy. This can be an issue for mobile devices relying on batteries.

The goal of thesis is to characterise statistically the memory allocation requirements of some types of applications and provide a numerically tractable model to predict the performances of a garbage collection policy in terms of throughput, average response time and expected CPU energy consumption.

Prerequisites: basic notions of statistics, probability and Markovian modelling.

For information contact: marin@dais.unive.it

Solution of algorithmic problems with mobile agents in dangerous environments – supervisor Flaminia Luccio

In the literature many problems have been solved in distributed settings by the cooperation of mobile agents. However, very little is still know in dangerous environments in which either some network nodes behave maliciously (see, e.g., the black hole problem), or in which one or more agents behave maliciously.

The goal of this thesis is to study the solution of various algorithmic problems in dangerous environments.

For information contact: luccio@unive.it

From theory to practice: how to develop theoretically interesting algorithms using real robots – supervisor Flaminia Luccio

The goal of this thesis is first to study if/how real theoretical protocols with mobile robots can be re-adapted in real case scenarios. Then, new interesting real protocols will be proposed and analysed, both from theoretical and from performance point of view. Experiments will be run using Lego Mindstorms EV3 robots.

For information contact: luccio@unive.it

 

Formal study and development of an Augmentative and Alternative Communication application – supervisors Flaminia Luccio and Antonina Dattolo

The goal of this thesis is first to extend the formal model of an Augmentative and Alternative Communication application, called Volo, for users with Autism Spectrum Disorders (see [1]). Then, the student will have to engineer the application, starting from the actual prototype. This thesis will be done in collaboration with the SASWEB Lab of the University of Udine at  Gorizia.

[1] A. Dattolo and  F. L. Luccio, Modelling Volo, an Augmentative and Alternative Communication application, In the proceedings of the Eighth International Conference on Advances in Computer-Human Interactions (ACHI 2015), pp. 14-19, February 22 – 27, 2015, Lisbon, Portugal, http://www.thinkmind.org/index.php?view=article&articleid=achi_2015_1_30_20170

For information contact: luccio@unive.it