Technical reports


List of technical reports of year 2006

Albano, Michele and Chessa, Stefano and Nidito, Francesco and Pelagatti, Susanna
Q-NiGHT: Adding QoS to Data Centric Storage in Non-Uniform Sensor Networks
December 9, 2014
UnipiEprints view

Storage of sensed data in wireless sensor networks is essential when the sink node is unavailable due to failure and/or disconnections, but it can also provide efficient access to sensed data to multiple sink nodes. Recent approaches to data storage rely on Geographic Hash Tables for efficient data storage and retrieval. These approaches however do not support different QoS levels for different classes of data as the programmer has no control on the level of redundancy of data (and thus on data dependability). Moreover, they result in a great unbalance in the storage usage in each sensor, even when sensors are uniformly distributed. This may cause serious data losses, waste energy and shorten the overall lifetime of the sensornet. In this paper, we propose a novel protocol, Q-NiGHT, which (1) provides a direct control on the level of QoS in the data dependability, and (2) uses a strategy similar to the rejection method to build a hash function which scatters data approximately with the same distribution as sensors. The benefits of QNiGHT are assessed through a detailed simulation experiment, also discussed in the paper. Results show its good performance on different sensors distributions on terms of both protocol costs and load balance between sensors.

Pisanti, Nadia and Soldano, Henry and Carpentier, Mathilde and Pothier, Joel
Inference of Approximated Motifs with Conserved Relations
December 9, 2014
UnipiEprints view

In this paper we define a new class of problems that generalizes that of finding repeated motifs. The novelty lies in the addition of constraints on the motifs in terms of relations that must hold between pairs of positions of the motifs. We will hence denote them as "relational motifs". For this class of problems we give an algorithm that is a suitable extension of the KMR paradigm and, in particular, of the KMRC as it uses a degenerate alphabet. The algorithm contains several improvements with respect to KMRC that result especially useful when---as it is required for relational motifs---the inference is made by partially overlapping shorter motifs, rather than concatenating them like in KMR. The efficiency, correctness and completeness of the algorithm is assured by several non-trivial properties that we prove in this paper. Finally, we list some possible applications and we focus on one of them: the study of 3D structures of proteins.

Bonchi, Filippo and Montanari, Ugo
A Coalgebraic Theory of Reactive Systems
December 9, 2014
UnipiEprints view

In this report we study the connection between two well known models for interactive systems. Reactive Systems à la Leifer and Milner allow to derive an interactive semantics from a reduction semantics guaranteeing, under rather restrictive conditions, thecompositionality of the abstract semantics (bisimilarity). Universal Coalgebra provides a categorical framework where bisimilarity can be characterized as final semantics, i.e., as the unique morphism to the final coalgebra. Moreover, if lifting a coalgebra to a structured setting is possible, then bisimilarity is compositional with respect to the lifted structure. Here we show that for every reactive system we can build a coalgebra. Further, if bisimilarity is compositional in the reactive system, then we can lift this coalgebra to a structured coalgebra.

Brogi, Antonio and Popescu, Razvan
BPEL2YAWL: Transalating BPEL processes into YAWL workflows
December 9, 2014
UnipiEprints view

The availability of several languages for the description of Web service behaviour (viz., protocols) hinders (automated) Web service aggregation, discovery, and adaptation as currently there are no tools for the (automated) translation of service protocols. In this paper we motivate the choice of YAWL as lingua-franca to express the behaviour of Web services. Furthermore, we describe a methodology for translating BPEL processes into YAWL workflows,thus paving the way for the formal analysis, aggregation, discovery, and adaptation of BPEL processes. Roughly, our methodology defines a YAWL pattern for each BPEL activity. The translation of a BPEL process reduces then to suitably instantiating and interconnecting the patterns of its activities.

Brogi, Antonio and Popescu, Razvan
Contract-based Service Aggregation
December 9, 2014
UnipiEprints view

We present a methodology for the automated selection and aggregation of (Web) services with the purpose of satisfying client queries. A key ingredient of our approach is the notion of service contract, which consists of signature (WSDL), ontology information (OWL), and behaviour specification (YAWL). The methodology inputs a registry of service contracts and a client service contract, and it automatically generates aggregated contracts that fulfil the request. By trace inspection we first individuate candidate sets of contracts that could satisfy the query collectively. For each candidate set, we generate the contract of the aggregate by suitably building its control- and data-flow, and we verify whether it actually complies with the request.

Aldinucci, Marco and Bertolli, Carlo and Campa, Sonia and Coppola, Massimo and Vanneschi, Marco and Veraldi, Luca and Zoccolo, Corrado
Self-Configuring and Self-Optimising Grid Components in the GCM model and their ASSIST Implementation
December 9, 2014
UnipiEprints view

We present the concept of adaptive super-component as a hierarchy of components to which a well-known parallel behavior is associated. The proposal of a super-component feature is part of the experience we gained in the implementation of the ASSIST environment, which allows to develop self-configuring and optimising, component-based applications following a structured and hierarchical approach. We discuss how such approach to Grid programming influenced the design of the GCM component model.

Bellia, Marco and Occhiuto, Maria Eugena
Methods Passed as Parameters in Java: A Pre-processing Approach
December 9, 2014
UnipiEprints view

In this paper we investigate the possibility of adding higher order functionalities to Java, that is passing methods as parameters to other methods. The approach is based on a mechanism which offers a restricted, disciplined, form of function abstraction but suitable to the integration of high order and Object Oriented programming. We discuss how the expressive power of the language is increased. A new syntax is introduced for formal and actual parameters, hence the paper shows an implementation of the extentions based on a preprocessing technique tha maps programs of the extended language into programs of ordinary Java.

Ferragina, Paolo and Venturini, Rossano
On a simple storage scheme for strings achieving entropy bounds
December 9, 2014
UnipiEprints view

In this note we propose a storage scheme for a string S[1,n], drawn from an alphabet A, that requires space close to the k-th order empirical entropy of S and allows to retrieve any L-long substring of S in optimal O(1 + L log A/log n) time. This matches the best known bounds via the only use of binary encodings and tables.

Bernasconi, Anna and Ciriani, Valentina and Cordone, Roberto
EXOR Projected Sum of Products
December 9, 2014
UnipiEprints view

In this paper we introduce a new algebraic form for Boolean function representation, called \emph{EXOR-Projected Sum of Products} (\emph{EP-SOP}), resulting in a four level network that can be easily implemented in practice. We prove that deriving an optimal EP-SOP from an optimal SOP form is a hard problem ($NP^{NP}$-hard); nevertheless we propose a very efficient approximation algorithm, which returns in polynomial time an EP-SOP form whose cost is guaranteed to be near the optimum. Experimental evidence shows that for about $35\%$ of the classical synthesis benchmarks the EP-SOP networks have a smaller area and delay with respect to the optimal SOPs (sometimes gaining even $40$-$50\%$ of the area). Since the computational times required are extremely short, we recommend the use of the proposed approach as a post-processing step after SOP minimization.

Peterlongo, Pierre and Pisanti, Nadia and Pereira do Lago, Alair and Sagot, Marie-France
Lossless Filter for Long Multiple Repetitions with Edit Distance
December 9, 2014
UnipiEprints view

Identifying local similarity between two or more sequences, or identifying repetitions occurring at least twice in a sequence, is an essential part in the analysis of biological sequences and of their phylogenetic relationship. Finding fragments that are conserved among several given sequences, or inside a unique sequence, while allowing for a certain number of insertions, deletions, and substitutions, is however known to be a computationally expensive task, and consequently exact methods can usually not be applied in practice. The filter we introduce in this paper, called Ed'Nimbus, provides a possible solution to this problem. It can be used as a preprocessing step to any multiple alignment method, eliminating an important fraction of the input that is guaranteed not to contain any approximate repetition. It consists in the verification of a strong necessary condition. This condition concerns the number and order of exactly repeated words shared by the approximate repetitions. The efficiency of the filter is due to this condition, that we show how to check in a fast way. The speed of the method is achieved thanks also to the use of a simple and efficient data structure, that we describe in this paper, as well as its linear time and space construction. Our results show that using Ed'Nimbus allows us to sensibly reduce the time spent in a local multiple alignment.The Ed'Nimbus software is freely available on the web:http://igm.univ-mlv.fr/$\sim$peterlon/officiel/ednimbus/

Bellia, Marco and Occhiuto, Maria Eugena
From Object Calculus to Java with Passing and Extraction of Methods
December 9, 2014
UnipiEprints view

Higher order programming is considered a good methodology for program design and specification, furthermore it is fundamental for rapid prototyping. The paper is devoted to higher order programming in Java and, more in general, in the OO programming paradigm. It extends \cite{high2} and discusses introspection to support higher order programming and compares this technique with other different, interesting approaches, including function emulation and function integration. Finally, it addresses the problem of embedding, in the OO paradigm, suitable mechanisms for method passing and method extraction: It exemplifies the use in OO programming and discusses language definition techniques.

Bonchi, Filippo and Gadducci, Fabio and Koenig, Barbara
Process Bisimulation via a Graphical Encoding
December 9, 2014
UnipiEprints view

The paper presents a case study on the synthesis of labelled transition systems (LTSs) for process calculi, choosing as testbed Milner's Calculus of Communicating System (CCS). The proposal is based on a graphical encoding: each CCS process is mapped into a graph equipped with suitable, such that the denotation is fully abstract with respect to the usual structural congruence. Graphs with interfaces are amenable to the synthesis mechanism based on borrowed contexts (BCs), proposed by Ehrig and Koenig (which are an instance of relative pushouts, originally introduced by Milner and Leifer). The BC mechanism allows the effective construction of an LTS that has graphs with interfaces as both states and labels, and such that the associated bisimilarity is automatically a congruence. Our paper focuses on the analysis of the LTS distilled by exploiting the encoding of CCS processes: besides offering some technical contributions towards the simplification of the BC mechanism, the key result of our work is the proof that the bisimilarity on processes obtained via BCs coincides with the standard strong bisimilarity for CCS.

Brogi, Antonio and Corfini, Sara
Behaviour-aware discovery of Web service compositions
December 9, 2014
UnipiEprints view

A major challenge for Service-oriented Computing is how to discover and compose (Web) services to build complex applications. We present a matchmaking system that exploits both semantics and behavioural information to discover service compositions capable of satisfying a client request.

Aldinucci, Marco and Danelutto, Marco
The cost of security in skeletal systems
December 9, 2014
UnipiEprints view

Skeletal systems exploit algorithmical skeletons technology to provide the user very high level, efficient parallel programming environments. They have been recently demonstrated to be suitable for highly distributed architectures, such as workstation clusters, networks and grids. However, when using skeletal system for grid programming care must be taken to secure data and code transfers across non-dedicated, non-secure network links. In this work we take into account the cost of security introduction in muskel, a full Java skeletal system exploiting macro data flow implementation technology. We consider the adoption of mechanisms that allow securing all the communications happening between remote, unreliable nodes and we evaluate the cost of such mechanisms. In particular, we consider the implications on the computational grains needed to scale secure and insecure skeletal computations.

Vanneschi, Marco
La Ricerca su Grid di prossima generazione
December 9, 2014
UnipiEprints view

In questo rapporto viene fatto il punto della situazione ed analizzate le tendenze scientifiche più interessanti nel campo delle piattaforme Grid. Queste vengono studiate nella loro generalità, dando enfasi agli aspetti più caratterizzanti in termini di dinamicità, adattività, eterogeneità e capacità di supportare paradigmi cooperativi scalabili. Come emerso chiaramente dagli ultimi progetti di ricerca cui il gruppo del Dipartimento ha partecipato (Grid.it, CoreGrid), è fondamentale la definizione e realizzazione di un insieme di strumenti ad alto livello per la progettazione di applicazioni e servizi, che rendano la piattaforma sostanzialmente invisibile al progettista di applicazioni (“Invisible Grid”). Gli obiettivi di tali strumenti sono il controllo della Qualità del Servizio (performance, affidabilità, sicurezza), da esprimere ad alto livello e da implementare a livello dinamico, e la capacità di supportare varie versioni del software applicativo, portabili attraverso l’evoluzione della tecnologia sottostante, e caratterizzate da prestazioni diverse. Sono discusse a fondo le convergenze tra settori di ricerca riguardanti parallel processing, knowledge discovery, security, intelligent networking.

Bernasconi, Anna and Ciriani, Valentina
DRedSOP: Synthesis of a new class of regular functions
December 9, 2014
UnipiEprints view

In this paper we characterize and study a new class of regular Boolean functions called D-reducible.A D-reducible function, depending on all its $n$ input variables, can be studied and synthesized in a space of dimension strictly smaller than $n$. A D-reducible function can be efficiently decomposed, giving rise to a new logic form, that we have called DRedSOP. This form is shown here to be generally smaller than the corresponding minimum SOP form. Experimental evidence shows that such functions are rather common and D-reducibility can be tested very quickly.

Frangioni, Antonio and Gentile, Claudio
SDP Diagonalizations and Perspective Cuts for a Class of Nonseparable MIQP
December 9, 2014
UnipiEprints view

Perspective cuts are a computationally effective family of valid inequalities, belonging to the general family of disjunctive cuts, for Mixed-Integer Convex NonLinear Programming problems with a specific structure. The required structure can be forced upon models that would not originally display it by decomposing the Hessian of the problem into the sum of two positive semidefinite matrices, a generic and a diagonal one, so that the latter is ''as large as possible''. We compare two ways for computing the diagonal matrix: an inexpensive approach requiring a minimum eigenvalue computation and a more costly procedure which require the solution of a SemiDefinite Programming problem. The latter dramatically outperforms the former at least upon instances of the Mean-Variance problem in portfolio optimization.

Ciuffoletti, Augusto
Scalable accessibility of a recoverable database using wandering tokens
December 9, 2014
UnipiEprints view

In a large distributed system there is usually the need to keep a record of the state of the components: one example is the database of the resources available in a Grid. The design of such database should take into account that the size of the system is not constant, and may vary of orders of magnitude: manual intervention to reconfigure the system in order to meet accessibility requirements may be problematic,and a source of unreliability.We present a scheme that provides scalable accessibility to such a database, focussing on the performance of update operations. The scalable implementation of update operations enables ubiquitous replication of the database, thus bringing at reach the scalability of read operations. Each component of the system regulates automatically the relevant operational parameters with a kind of feedback, which is based on probabilistic considerations. Many aspect of the scheme are in fact probabilistic, and we introduce a simple model that describes the performance of the system. The overall approach as well as certain performance figures that cannot be forecast analitically, are explored with simulation.

Brogi, Antonio and Popescu, Razvan and Tanca, Matteo
Design and implementation of SATOR: a Web service aggregator
December 5, 2014
UnipiEprints view

The aggregation methodology we propose in this paper automatically generates the service contract of a composite service from a set of contracts to be ggregated together with a data-flow mapping linking service parameters. Service contracts consist of (WSDL) signature, (OWL) ontology information, and (YAWL) behaviour specification. The aggregation process generates the workflow of the composite from the initial workflows by suitably adding control-flow constraints among their tasks due to data-flow dependencies among task parameters. After describing the whole methodology, we will also give an insight on our proof-of-concept Java prototype implementation of the aggregation process.



NOTE. Starting January 2015 Technical reports can be inserted in the Open Access repository UnipiEprints.
Once published, they will be visible also in these pages. The old TR service is no longer maintained.

Data imported from UnipiEprints