Technical reports

The paper presents a heuristic algorithm for the minimization of 2-SPP networks, i.e., three-level XOR-AND-OR forms with XOR gates restricted to fan-in 2. Previous works had presented exact algorithms for the minimization of unrestricted SPP networks and of 2-SPP networks. The exact minimization procedures were formulated as covering problems as in the minimization of SOP forms and had worst-case exponential complexity. Extending the expand-irredundant-reduce paradigm of ESPRESSO heuristic, we propose a minimization algorithm for 2-SPP networks that iterates local minimization and reshape of a solution until further improvement. We introduce also the notion of EXOR-irredundant to prove that OR-AND-EXOR irredundant networks are fully testable and guarantee that our algorithm yields OR-AND-EXOR irredundant solutions. We report a large set of experiments showing impressive high-quality results with affordable run times, handling also examples whose exact solutions could not be computed.

The ASSIST environment provides a high-level programming toolkit for the grid. ASSIST applications are described by means of a coordination language, which can express arbitrary graphs of modules. These modules (or a graph of them) may be enclosed in components specifically designed for the grid (GRID.it components). In this paper we describe how ASSIST modules can be wired through standard Web Services, and how GRID.it components may be made available as standard Web Services.

Detecting repeated 3D protein substructures has become a new crucial frontier in motifs inference. In \cite{cpm} we have suggested a possible solution to this problem by means of a new framework in which the repeated pattern is required to be conserved also in terms of relations between its position pairs. In our application these relations are the distances between $\alpha$-carbons of amino acids in 3D proteins structures, thus leading to a \emph{structural consensus} as well. In this paper we motivate some complexity issues claimed (and assumed, but not proved) in \cite{cpm} concerning inclusion tests between occurrences of repeated motifs. These inclusion tests are performed during the motifs inference in \emph{KMRoverlapR} (presented in \cite{cpm}), but also within other motifs inference tools such as \emph{KMRC} (\cite{kmrc}). These involve alternative representations of motifs, for which we also prove here some interesting properties concerning pattern matching issues. We conclude this contribution with a few tests on cytochrome P450 protein structures.

PageRank algorithm plays a very important role in search engine technology and consists in the computation of the eigenvector corresponding to the eigenvalue one of a matrix whose size is now in the billions. The problem incorporates a parameter $\alpha$ that determines the difficulty of the problem. In this paper, the effectiveness of stationary and non stationary methods are compared on some portion of real web matrices for different choices of $\alpha$. We see that stationary methods are very reliable and more competitive when the problem is well conditioned, that is for small values of $\alpha$. However, for large value of the parameter $\alpha$ the problem becomes more difficult and methods such as preconditioned BiCGStab or restarted preconditioned GMRES become competitive with stationary methods in terms of Mflops count as well as in number of iterations necessary to reach convergence.

AdHoc (Adaptive Distributed Herd of Ob ject Caches) is a Grid-enabled, fast, scalable ob ject repository providing programmers with a general storage module. We present three different software tools based on AdHoc: A parallel cache for Apache, a DSM, a main-memory parallel file system. We also show that these tool exhibit a considerable performance and speedup both in absolute figures and w.r.t. other software tools exploiting the same features.

The workshop is organised by the Network of Excellence CoreGRID funded by the European Commission under the sixth framework programme IST-2003-2.3.2.8 starting September 1st, 2004. CoreGRID aims at strengthening and advancing scientific and technological excellence in the area of Grid and Peer-to-Peer technologies. To achieve this objective, the network brings together a critical mass of well-established researchers (119 permanent researchers and 165 PhD students) from forty-two institutions who have constructed an ambitious joint programme of activities. The goal of the workshop is to promote the integration of the CoreGRID network and of the European research community in the area of Grid technologies, in order to overcome the current fragmentation and duplication of efforts in this area. The list of topics of Grid research covered at the workshop includes but is not limited to: knowledge & data management; programming models; system architecture; Grid information, resource and workflow monitoring services; resource management and scheduling;systems, tools and environments;trust and security issues on the Grid.

This paper illustrates a technique to characterize one-way packet delays. Such technique does not depend on external clock synchronization facilities: instead, it computes the relative skew of the two clocks, and uses this information to characterize one-way packet delays. We focus on the applicability of such technique to a network monitoring environment, and perform an extensive test that includes second order clock frequency variations. We conclude that the approach is especially suited to estimate jitter, and other characteristics of one-way delay variation. It can be helpful also to evaluate second order parameters of one-way delay, like standard deviation, when second order variations of clock frequency, usually due to temperature variations, are compensated by hardware. This result makes one-way delay variations measurement widely accessible to Internet hosts, at a cost which is overall comparable with that of a ping.

We propose a compositional coalgebraic semantics of the Fusion calculus of Parrow and Victor in the version with explicit fusions by Gardner and Wischik. We follow a recent approach developed by the same authors and previously applied to the pi-calculus for lifting calculi with structural axioms to bialgebraic models. In our model, the unique morphism to the final bialgebra induces a bisimilarity relation which coincides with hyperequivalence and which is a congruence with respect to the operations. Interesting enough, the explicit fusion approach allows to exploit for the Fusion calculus essentially the same algebraic structure used for the pi-calculus.

Recently introduced, three-level logic Sum of Pseudoproducts (SPP) forms allow the representation of Boolean functions with much shorter expressions than standard two-level Sum of Products (SOP) forms, or other three-level logic forms. In this paper the testability of circuits derived from SPPs is analyzed. We study testability under static Fault Models (FMs),i.e., the Stuck-At Fault Model (SAFM) and the Cellular Fault Model(CFM). For SPP networks several minimal forms can be considered. While full testability can be proved in the SAFM for some forms, SPP networks in the CFM are shown to contain redundancies. Finally, we propose a method for transforming non-testable networks into testable ones. Experimental results are given to demonstrate the efficiency of the approach.

In a distributed system where scalability is an issue, like in a GRID, the problem of enforcing mutual exclusion often arises in a soft form: the infrequent failure of the mutual exclusion predicate is tolerated, without compromising the consistent operation of the overall system. For instance this occurs when the operation subject to mutual exclusion requires massive use of a shared resource. We introduce a scalable soft mutual exclusion algorithm, based on token passing: one distinguished feature of our algorithm is that instead of introducing an overlay topology we adopt a random walk approach. The consistency of our proposal is evaluated by simulation, and we exemplify its use in the coordination of large data transfers in a backbone based network.

ASSIST is a structured parallel programming environment targeting networks/clusters of workstations and grids. It introduced the parmod parallel construct, supporting a variety of parallelism exploitation patterns, including classical ones. The original implementation of parmod relies on static assignment of parallel activities to the processing elements at hand. In this work we discuss an alternative implementation of the parmod construct that implements completely dynamic assignment of parallel activities to the processing elements. We show that the new implementation introduces very limited overhead in case of regular computations, whereas it performs much better than the original one in case of irregular applications. The whole implementation of parmod is available as a C++/MPI library.

The availability of the outcome of network monitoring activities, while valuable for the operation of Grid applications, poses serious scalability problems: in principle, in a Grid composed of resources, we need to keep record of end-to-end paths. We introduce a scalable approach to network monitoring, that consists in partitioning the Grid into limiting monitoring activity to the measurement of domain-to-domain connectivity. Partitions must be consistent with network performance, since we expect that an observed network performance between domains is representative of the performance between the Grid Services included into such domains. We argue that partition design is a critical step: a consequence of an inconsistent partitioning is the production of invalid characteristics. The paper discusses such approach, also exploring its limits. We describe a fully functional prototype which is currently under test in the frame of the DATATAG project.

We describe rank structures in generalized inverses of possibly rectangular banded matrices. In particular, we show that various kind of generalized inverses of rectangular banded matrices have submatrices whose rank depends on the bandwidth and on the nullity of the matrix. Moreover, we give an explicit representation formula for some generalized inverses of strictly banded matrices.

The conceptual separation between computation and coordination in distributed computing systems motivates the use of peculiar entities commonly called connectors, whose task is managing the interaction among distributed components. Different kinds of connectors exist in the literature at different levels of abstraction. We focus on a basic algebra of connectors which is expressive enough to model e.g. all the architectural connectors of CommUnity. We first define the operational, observational and denotational semantics of connectors, then we show that the observational and denotational semantics coincide and finally we give a complete normal-form axiomatization.

Security is one particular global challenge that has recently come to the fore due to world events and societal changes. Within this context, one of the areas in which Operations Research can give an important contribution is the area of early warning and crisis prevention. This is a challenging research area requiring a multidisciplinary approach, which has enjoyed an increased interest in recent years. Here, we will highlight some of the problems arising in this area in which O.R. techniques can find useful applications.

In the context of abstract interpretation based static analysis, we cope with the problem of correctness and optimality for logic program analysis. We propose a new framework equipped with a denotational, goal-dependent semantics which refines many goal-driven frameworks appeared in the literature. The key point is the introduction of two specialized concrete operators for forward and backward unification. We prove that our goal-dependent semantics is correct w.r.t. computed answers and we provide the best correct approximations of all the operators involved in the semantics for set-sharing analysis. We show that the precision of the overall analysis is strictly improved and that, in some cases, we gain precision w.r.t. more complex domains involving linearity and freeness information.

To identify coding regions in genomic sequences represents the first step toward further analysis of the biological function carried on by the different functional elements in a genome. The present paper presents a novel method for the classification of coding and non-coding regions in prokaryotic genomes, based on a suitable defined compression index of a DNA sequence. The proposed approach has been applied on some prokaryotic complete genomes, obtaining optimal scores of correctly recognized coding and non-coding regions. Several false-positive and false-negative cases have been investigated in detail, discovering that this approach can fail in the presence of highly-structured coding regions (e.g., genes coding for modular proteins) or quasi-random non-coding regions (regions hosting non-functional fragments of copies of functional genes; regions hosting promoters or other protein-binding sequences, etc.).

Current GRID technology provides users/programmers with extended and comprehensive middleware tools covering all the basic aspects a programmer must deal with when writing GRID aware applications. Programmers of GRID aware applications use such middleware systems to gather the needed resources, stage code and data to the selected computing resources, schedule computations on them and so on. Overall, a huge programming effort is required in order to come to a working, efficient GRID aware application code. Here we propose a different approach. By recognizing that most GRID applications share a common parallel/distributed structure, we propose to use application managers that take care of all the details involved in the implementation of well known GRID aware application schemas. Such application managers use the functionalities of a RISC GRID core run time system (RGC). The RGC may be built on top of existing GRID middleware. Programmers of GRID aware applications, therefore, do not directly use GRID middleware. Rather, they structure the application using the available application managers. The application managers, in turn, invoke the basic GRID services provided by RGC to accomplish both functional and performance user requirements.

The restricted rotation distance d_{R}(S,T) between two binary trees S, T of n vertices is the minimum number of rotations by which S can be transformed into T, where rotations can only take place at the root of the tree, or at the right child of the root. A sharp upper bound d_{R}(S,T) \leq 4n-8 is known, based on the word metric of Thompson's group. We refine this bound to a sharp d_{R}(S,T) \leq 4n-8-\rho_{S}-\rho_{T}, where \rho_{S} and \rho_{T} are the numbers of vertices in the rightmost vertex chains of the two trees, by means of a very simple transformation algorithm based on elementary properties of trees. We then generalize the concept of restricted rotation to k-restricted rotation, by allowing rotations to take place at all the vertices of the highest k levels of the tree. For k=2 we show that not much is gained in the worst case, although the classical problem of rebalancing an AVL tree can be solved efficiently, in particular rebalancing after vertex deletion requires O(log n) rotations as in the standard algorithm. Finding significant bounds and applications for k \geq 3 is open.

Current Grid-aware applications are developed on top of lowlevel libraries by developers who are experts on Grid software implementation. Although some applications have been produced this way, this approach can hardly support the additional complexity to QoS control in real applications. We describe the ASSIST programming environment, showing that it is a suitable basis to capture and cope with many of the desired features for QoS control for the Grid. Grid applications, built as compositions of ASSIST modules, are supported by a hierarchical Application Manager targeting application QoS control.

We propose a formal method to validate the reliability of a web application, by modeling interactions among its constituent objects. Modeling exploits the recent "Multiple Levels of Integrity" mechanism which allows objects with dynamically changing reliability to cooperate within the application. The novelty of the method is the ability to describe systems where objects can modify their own integrity level, and react to such changes in other objects. The model is formalized with a process algebra, properties are expressed using the ACTL temporal logic, and can be verified by means of a model checker. Any instance of the above model inherits both the established properties and the proof techniques. To substantiate our proposal we consider several case-studies of web applications, showing how to express specific useful properties, and their validation schemata. Examples range from on-line travel agencies, inverted Turing test to detect malicious web-bots, to content cross-validation in peer to peer systems.

We consider the problem of fast IP address lookup in the forwarding engines of Internet routers. Many hardware and software solutions available in the literature solve a more general problem on strings, the longest prefix match. These solutions are then specialized on real IPv4/IPv6 addresses to work well on the specific IP lookup problem. We propose to go the other way around. We first analyze over 2400 public snapshots of routing tables collected over five years, discovering what we call the "middle-class effect" of those routes. We then exploit this effect for tailoring a simple solution to the IP lookup scheme, taking advantage of the skewed distribution of Internet addresses in routing tables. Our algorithmic solution is easy to implement in hardware or software as it is tantamount to performing an indirect memory access. Its performance can be bounded tightly in the worst case and has very low memory dependence (e.g., just one memory access to off-chip memory in the hardware implementation). It can quickly handle route announcements and withdrawals on the fly, with a small cost which scales well with the number of routes. Concurrent access is permitted during these updates. Our ideas may be helpful for attaining state-of-art link speed and may contribute to setting up a general framework for designing lookup methods by data analysis.

We face the problem of devising optimal unification operators for domains of abstract substitutions. In particular, we are interested in abstract domains for sharing and linerity properties, which are widely used in logic program analysis. We propose a new (infinite) domain ShLin which can be thought of as a general framework from which other domains can be easily derived by abstraction. The advantage is that abstract unification in ShLin is simple and elegant, and it is based on a new concept of sharing graph which plays the same role of alternating paths for pair sharing analysis. We also provide an alternative, purely algebraic description of sharing graphs. Starting from the results for ShLin, we derive optimal abstract operators for two well-known domains which combine sharing and linearity: a domain proposed by Andy King and the classic Sharing X Lin.

In 1959 Edgar Asplund presented a geometric lemma that largely anticipated many results on the structure of inverses of band matrices. In this note we discuss an extension of Asplund's lemma that addresses the concept of generalized inverse,in particular the Moore-Penrose inverse.