nach oben

2018 | Buch

Kapitel lesen Erstes Kapitel lesen

New Frontiers in Quantitative Methods in Informatics

7th Workshop, InfQ 2017, Venice, Italy, December 4, 2017, Revised Selected Papers

herausgegeben von: Prof. Simonetta Balsamo, Andrea Marin, Enrico Vicario

Verlag: Springer International Publishing

Buchreihe : Communications in Computer and Information Science

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

This book constitutes the refereed proceedings of the 7th Workshop on New Frontiers in Quantitative Methods in Informatics, InfQ 2017, held in Venice, Italy, in December 2017.
The 11 revised full papers and the one revised short paper presented were carefully reviewed and selected from 22 submissions. The papers are organized in topical sections on networking and mobile applications; applications of quantitative modeling; big data processing and IoT; theory, methods and tools for quantitative analysis.

Inhaltsverzeichnis

Frontmatter

Networking and Mobile Applications

Frontmatter

Geofenced Broadcasts via Centralized Scheduling of Device-to-Device Communications in LTE-Advanced

Abstract

Point-to-multipoint device-to-device (P2MP D2D) communications have been standardized in LTE-Advanced (LTE-A) for proximity-based services, such as advertisement and public safety. They can be combined in a multi-hop fashion to achieve geofenced broadcasts in a fast and reliable way, over areas possibly covered by several cells [17]. This allows LTE-A networks to support critical services, like vehicular collision alerts or cyber-physical systems, at a modest cost in terms of consumed resources. In this paper, we argue that previous approaches, which rely on User Equipment (UE) applications to make distributed decisions about message relaying, incur in high per-hop overhead and make crossing cell border difficult. We then propose a novel approach that relies on centralized decisions made at the infrastructure eNodeBs (eNBs) to schedule unsolicited D2D grants to the optimal set of UEs that should forward a message at any time. The eNBs can also leverage inter-cell communications through the X2 interface to parallelize relaying over different cells, thus covering larger areas fast. We show that our infrastructure-based approach is computationally feasible and geographically scalable, and prove via simulation that it is faster, more reliable and efficient than UE-based multihop relaying.

Giovanni Nardini, Giovanni Stea, Antonio Virdis

Analysis of Performance in Depth Based Routing for Underwater Wireless Sensor Networks

Abstract

In the last decade, Underwater Wireless Sensor Networks (UWSNs) have been widely studied because of their peculiar aspects that distinguish them from common wireless terrestrial networks. In fact, most UWSNs use acoustic instead of radio-frequency based communications, and nodes are subject to high mobility caused by water currents. As a consequence, specialised routing algorithms have been developed to tackle this challenging scenario. Depth based Routing (DBR) is one of the first protocols that have been developed to this aim, and is still widely adopted in actual implementations of UWSNs. In this paper we propose a stochastic analysis that aims at evaluating the performance of UWSNs using DBR in terms of expected energy consumption and expected end-to-end delay. Under a set of assumptions, we give expressions for these performance indices that can be evaluated efficiently, and hence they can be adopted as the basis for optimizing the configuration parameters of the protocol.

Simonetta Balsamo, Dieter Fiems, Mohsin Jafri, Andrea Marin

Applications of Quantitative Modeling

Frontmatter

Performance Evaluation of a Secure and Scalable E-Voting Scheme Using PEPA

Abstract

In this paper we constructed a formal performance model for a secure and scalable e-voting scheme known as DRE-i voting scheme. The well-known formal stochastic performance evaluation process algebra (PEPA) language and PEPA Eclipse plug-in were used to represent the voting scheme and analyse its performance characteristics. Timely responses of remote electronic voting protocols are important to increase voters’ confidence in e-voting systems. Therefore we evaluated the average response time that voters may observe when they cast their votes using remote electronic voting systems, such as DRE-i, and we also evaluated the throughput and queue length of the DRE-i server’s actions for different number of voters inside the DRE-i e-voting system. The performance evaluation of the DRE-i scheme reveals that PEPA language is efficient in investigating the performance properties of large scale e-voting schemes.

Mohammed Alotaibi, Nigel Thomas

Modeling Crowd Behavior in a Theater

Abstract

To manage emergencies, it is useful to be able to understand how crowds behave in case of incidents. We modeled, by means of Markovian Agents, the behavior of a crowd in a theater to evaluate the effects of a potentially catastrophic situation in a constrained space. The chosen modeling technique showed to be well fit to help and evaluate, given the nature of a space with significant obstacles and densely occupied by people, what kind of actions should be taken in advance to mitigate the damage in case of problems.

Enrico Barbierato, Marco Gribaudo, Mauro Iacono, Alexander H. Levis

Big Data Processing and IoT

Frontmatter

Vs-Driven Big Data Process Development

Abstract

Big Data solutions aim to cope with the overwhelming amount of data generated by various domains, such as social networks and the Internet of Things, thereby enabling a new generation of data-intensive applications (DIAs) and services. At the same time, to facilitate DIA design and development processes and address (Big) data management requirements, proper techniques and tools are requested. To this purpose, this paper proposes an approach, which takes into account the established Big Data V-attributes, (i.e. Volume, Velocity, and Variety) to model and predict computational demands at design time. To do so, the approach relies on annotating Big Data process workflows (and their individual elements) with relevant V-attribute values, which are then mapped into resource requirements and used in a performance model.

Rustem Dautov, Salvatore Distefano

Capacity Planning of Fog Computing Infrastructures for Smart Monitoring

Abstract

Fog Computing (FC) systems represent a novel and promising generation of computing systems aiming at moving storage and computation close to end-devices so as to reduce latency, bandwidth and energy-efficiency. Despite their gaining importance, the literature about capacity planning studies for FC systems is very limited only considering very simplified technological cases. This paper considers a model for the capacity planning of a FC system for smart monitoring applications. More specifically, this paper considers a FC-based rock collapse forecasting system based on a hybrid wired-wireless architecture deployed in the Swiss-Italian Alps. The system is composed by sensing units deployed on rock faces to gather environmental data and FC-units providing high-performance computing for smart monitoring purposes.

Capacity planning studies will be designed for this FC-based system as well as for extensions of the original system (by varying the number of sensing units, sampling rates, the number of FC-units, the Radio Bandwidth and the Cloud capacity). The proposed multi-formalism model for capacity planning is based on the integrated use of Queuing Networks and Petri Nets. Some preliminary results concerning the potential use of the proposed model are described and commented.

Riccardo Pinciroli, Marco Gribaudo, Manuel Roveri, Giuseppe Serazzi

Performance Degradation and Cost Impact Evaluation of Privacy Preserving Mechanisms in Big Data Systems

Abstract

Big Data is an emerging area and concerns managing datasets whose size is beyond commonly used software tools ability to capture, process, and perform analyses in a timely way. The Big Data software market is growing at 32% compound annual rate, almost four times more than the whole ICT market, and the quantity of data to be analyzed is expected to double every two years.

Security and privacy are becoming very urgent Big Data aspects that need to be tackled. Indeed, users share more and more personal data and user generated content through their mobile devices and computers to social networks and cloud services, losing data and content control with a serious impact on their own privacy. Privacy is one area that had a serious debate recently, and many governments require data providers and companies to protect users’ sensitive data. To mitigate these problems, many solutions have been developed to provide data privacy but, unfortunately, they introduce some computational overhead when data is processed.

The goal of this paper is to quantitatively evaluate the performance and cost impact of multiple privacy protection mechanisms. A real industry case study concerning tax fraud detection has been considered. Many experiments have been performed to analyze the performance degradation and additional cost (required to provide a given service level) for running applications in a cloud system.

Safia Kalwar, Eugenio Gianniti, Joas Yannick Kinouani, Youssef Ridene, Danilo Ardagna

Auto-Scaling in Data Stream Processing Applications: A Model-Based Reinforcement Learning Approach

Abstract

By exploiting on-the-fly computation, Data Stream Processing (DSP) applications can process huge volumes of data in a near real-time fashion. Adapting the application parallelism at run-time is critical in order to guarantee a proper level of QoS in face of varying workloads. In this paper, we consider Reinforcement Learning based techniques in order to self-configure the number of parallel instances for a single DSP operator. Specifically, we propose two model-based approaches and compare them to the baseline Q-learning algorithm. Our numerical investigations show that the proposed solutions provide better performance and faster convergence than the baseline.

Valeria Cardellini, Francesco Lo Presti, Matteo Nardelli, Gabriele Russo Russo

Theory, Methods and Tools for Quantitative Analysis

Frontmatter

e: A Translation Framework from Quipper Programs to Quantum Markov Chains

Abstract

\(\mathtt {Entang}\mathtt {\lambda }{} \mathtt{e}\) is a framework for translating the quantum programming language Quipper to the QPMC model checker. It has been developed in order to formally verify Quipper-like programs. Quipper is a functional circuit description language, allowing an high-level approach for manipulating quantum circuits. Quipper uses the vector state formalism and provides high-level operations. QPMC is a model checker designed for quantum protocols specified as Quantum Markov Chains, and it is based on the density matrix formalism; QPMC supports the temporal logic QCTL. We have developed \(\mathtt {Entang{\lambda }e}\) to deal with the notion of tail recursive quantum programs in Quipper, and so we are able to verify QCTL properties over such programs. The tool implementation has been tested on several quantum protocols, including the BB84 protocol for quantum key distribution.

Linda Anticoli, Carla Piazza, Leonardo Taglialegne, Paolo Zuliani

Analysis of Non-Markovian Systems in GreatSPN

Abstract

Markov Regenerative Processes (MRgP) with enabling restriction allow to model stochastic processes where the firing distribution of some events may be specified by a non-Markovian Probability Distribution Function, provided that at most one of these events is enabled in any state of the process. The GreatSPN framework is a collection of tools for the modeling and analysis of systems specified as Stochastic Petri Nets. The paper describes the new features of the MRgP solver of GreatSPN to deal with MRgP processes. The solver supports a rich language for the specification of non-Markovian events, and different solution techniques (explicit, matrix-free, component-based) for the MRgP analysis. The potentiality of the tools are shown on a few examples.

Elvio Gilberto Amparore, Susanna Donatelli

Evaluation of Iterative Methods on Large Markov Chains Generated by GSPN Models

Abstract

GSPN models often generate high cardinality state spaces, whose analysis requires the solution of very large and sparse nonsymmetric linear systems for the associated Markov chain. In this paper we report the results of an empirical investigation of three well-known iterative methods for linear systems of equations: Gauss-Seidel, GMRES, and Bi-CGstab. We evaluate these methods on several large Markov chains generated by GSPN models proposed in the literature. Issues addressed include state space characterization, problem conditioning, numerical accuracy and stability, and computation time. Results show that increased attention should be paid to the numerical issues underlying performance and reliability analyses when dealing with large state spaces.

Stefano Caselli, Gianni Conte, Mauro Diligenti

Mean Field Analysis for Continuous Time Bayesian Networks

Abstract

In this paper we investigate the use of the mean field technique to analyze Continuous Time Bayesian Networks (CTBN). They model continuous time evolving variables with exponentially distributed transitions with the values of the rates dependent on the parent variables in the graph. CTBN inference consists of computing the probability distribution of a subset of variables, conditioned by the observation of other variables’ values (evidence). The computation of exact results is often unfeasible due to the complexity of the model. For such reason, the possibility to perform the CTBN inference through the equivalent Generalized Stochastic Petri Net (GSPN) was investigated in the past. In this paper instead, we explore the use of mean field approximation and apply it to a well-known epidemic case study. The CTBN model is converted in both a GSPN and in a mean field based model. The example is then analyzed with both solutions, in order to evaluate the accuracy of the mean field approximation for the computation of the posterior probability of the CTBN given an evidence. A summary of the lessons learned during this preliminary attempt concludes the paper.

Davide Cerotti, Daniele Codetta-Raiteri

Backmatter

Titel: New Frontiers in Quantitative Methods in Informatics
herausgegeben von: Prof. Simonetta Balsamo
Andrea Marin
Enrico Vicario
Verlag: Springer International Publishing
Electronic ISBN: 978-3-319-91632-3
Print ISBN: 978-3-319-91631-6
DOI: https://doi.org/10.1007/978-3-319-91632-3