OpenRaiser/Intern-Atlas huggingface dataset:
Managing Separation of Concerns in Grid Applications Through Architectural Model Transformations
Venue: arXiv cs.SE 2007
Year: 2007

Grids enable the aggregation, virtualization and sharing of massive heterogeneous and geographically dispersed resources, using files, applications and storage devices, to solve computation and data intensive problems, across institutions and countries via temporary collaborations called virtual organizations (VO). Most implementations result in complex superposition of software layers, often delivering low quality of service and quality of applications. As a consequence, Grid-based applications design and development is increasingly complex, and the use of most classical engineering practices is unsuccessful. Not only is the development of such applications a time-consuming, error prone and expensive task, but also the resulting applications are often hard-coded for specific Grid configurations, platforms and infra-structures. Having neither guidelines nor rules in the design of a Grid-based application is a paradox since there are many existing architectural approaches for distributed computing, which could ease and promote rigorous engineering methods based on the re-use of software components. It is our belief that ad-hoc and semi-formal engineer-ing approaches, in current use, are insufficient to tackle tomorrows Grid develop-ments requirements. Because Grid-based applications address multi-disciplinary and complex domains (health, military, scientific computation), their engineering requires rigor and control. This paper therefore advocates a formal model-driven engineering process and corresponding design framework and tools for building the next generation of Grids.
PhantomOS: A Next Generation Grid Operating System
Venue: arXiv cs.DC 2007
Year: 2007

Grid Computing has made substantial advances in the past decade; these are primarily due to the adoption of standardized Grid middleware. However Grid computing has not yet become pervasive because of some barriers that we believe have been caused by the adoption of middleware centric approaches. These barriers include: scant support for major types of applications such as interactive applications; lack of flexible, autonomic and scalable Grid architectures; lack of plug-and-play Grid computing and, most importantly, no straightforward way to setup and administer Grids. PhantomOS is a project which aims to address many of these barriers. Its goal is the creation of a user friendly pervasive Grid computing platform that facilitates the rapid deployment and easy maintenance of Grids whilst providing support for major types of applications on Grids of almost any topology. In this paper we present the detailed system architecture and an overview of its implementation.
A New Family of Unitary Space-Time Codes with a Fast Parallel Sphere Decoder Algorithm
Venue: arXiv cs.IT 2007
Year: 2007

In this paper we propose a new design criterion and a new class of unitary signal constellations for differential space-time modulation for multiple-antenna systems over Rayleigh flat-fading channels with unknown fading coefficients. Extensive simulations show that the new codes have significantly better performance than existing codes. We have compared the performance of our codes with differential detection schemes using orthogonal design, Cayley differential codes, fixed-point-free group codes and product of groups and for the same bit error rate, our codes allow smaller signal to noise ratio by as much as 10 dB. The design of the new codes is accomplished in a systematic way through the optimization of a performance index that closely describes the bit error rate as a function of the signal to noise ratio. The new performance index is computationally simple and we have derived analytical expressions for its gradient with respect to constellation parameters. Decoding of the proposed constellations is reduced to a set of one-dimensional closest point problems that we solve using parallel sphere decoder algorithms. This decoding strategy can also improve efficiency of existing codes.
Scheduling in Data Intensive and Network Aware (DIANA) Grid Environments
Venue: arXiv cs.DC 2007
Year: 2007

In Grids scheduling decisions are often made on the basis of jobs being either data or computation intensive: in data intensive situations jobs may be pushed to the data and in computation intensive situations data may be pulled to the jobs. This kind of scheduling, in which there is no consideration of network characteristics, can lead to performance degradation in a Grid environment and may result in large processing queues and job execution delays due to site overloads. In this paper we describe a Data Intensive and Network Aware (DIANA) meta-scheduling approach, which takes into account data, processing power and network characteristics when making scheduling decisions across multiple sites. Through a practical implementation on a Grid testbed, we demonstrate that queue and execution times of data-intensive jobs can be significantly improved when we introduce our proposed DIANA scheduler. The basic scheduling decisions are dictated by a weighting factor for each potential target location which is a calculated function of network characteristics, processing cycles and data location and size. The job scheduler provides a global ranking of the computing resources and then selects an optimal one on the basis of this overall access and execution cost. The DIANA approach considers the Grid as a combination of active network elements and takes network characteristics as a first class criterion in the scheduling decision matrix along with computation and data. The scheduler can then make informed decisions by taking into account the changing state of the network, locality and size of the data and the pool of available processing cycles.
Better Algorithms and Bounds for Directed Maximum Leaf Problems
Venue: arXiv cs.DS 2007
Year: 2007

The {\sc Directed Maximum Leaf Out-Branching} problem is to find an out-branching (i.e. a rooted oriented spanning tree) in a given digraph with the maximum number of leaves. In this paper, we improve known parameterized algorithms and combinatorial bounds on the number of leaves in out-branchings. We show that \begin{itemize} \item every strongly connected digraph $D$ of order $n$ with minimum in-degree at least 3 has an out-branching with at least $(n/4)^{1/3}-1$ leaves; \item if a strongly connected digraph $D$ does not contain an out-branching with $k$ leaves, then the pathwidth of its underlying graph is $O(k\log k)$; \item it can be decided in time $2^{O(k\log^2 k)}\cdot n^{O(1)}$ whether a strongly connected digraph on $n$ vertices has an out-branching with at least $k$ leaves. \end{itemize} All improvements use properties of extremal structures obtained after applying local search and of some out-branching decompositions.
Espaces de représentation multidimensionnels dédiés à la visualisation
Venue: arXiv cs.DB 2007
Year: 2007

In decision-support systems, the visual component is important for On Line Analysis Processing (OLAP). In this paper, we propose a new approach that faces the visualization problem due to data sparsity. We use the results of a Multiple Correspondence Analysis (MCA) to reduce the negative effect of sparsity by organizing differently data cube cells. Our approach does not reduce sparsity, however it tries to build relevant representation spaces where facts are efficiently gathered. In order to evaluate our approach, we propose an homogeneity criterion based on geometric neighborhood of cells. The obtained experimental results have shown the efficiency of our method.
Un index de jointure pour les entrepôts de données XML
Venue: arXiv cs.DB 2007
Year: 2007

XML data warehouses form an interesting basis for decision-support applications that exploit heterogeneous data from multiple sources. However, XML-native database systems currently bear limited performances and it is necessary to research ways to optimize them. In this paper, we propose a new index that is specifically adapted to the multidimensional architecture of XML warehouses and eliminates join operations, while preserving the information contained in the original warehouse. A theoretical study and experimental results demonstrate the efficiency of our index, even when queries are complex.
Report on Generic Case Complexity
Venue: arXiv cs.CC 2007
Year: 2007

This article is a short introduction to generic case complexity, which is a recently developed way of measuring the difficulty of a computational problem while ignoring atypical behavior on a small set of inputs. Generic case complexity applies to both recursively solvable and recursively unsolvable problems.
Computability Closure: Ten Years Later
Venue: arXiv cs.LO 2007
Year: 2007

The notion of computability closure has been introduced for proving the termination of higher-order rewriting with first-order matching by Jean-Pierre Jouannaud and Mitsuhiro Okada in a 1997 draft which later served as a basis for the author's PhD. In this paper, we show how this notion can also be used for dealing with beta-normalized rewriting with matching modulo beta-eta (on patterns à la Miller), rewriting with matching modulo some equational theory, and higher-order data types (types with constructors having functional recursive arguments). Finally, we show how the computability closure can easily be turned into a reduction ordering which, in the higher-order case, contains Jean-Pierre Jouannaud and Albert Rubio's higher-order recursive path ordering and, in the first-order case, is equal to the usual first-order recursive path ordering.
IRVO: an Interaction Model for designing Collaborative Mixed Reality systems
Venue: arXiv cs.HC 2007
Year: 2007

This paper presents an interaction model adapted to mixed reality environments known as IRVO (Interacting with Real and Virtual Objects). IRVO aims at modeling the interaction between one or more users and the Mixed Reality system by representing explicitly the objects and tools involved and their relationship. IRVO covers the design phase of the life cycle and models the intended use of the system. In a first part, we present a brief review of related HCI models. The second part is devoted to the IRVO model, its notation and some examples. In the third part, we present how IRVO is used for designing applications and in particular we show how this model can be integrated in a Model-Based Approach (CoCSys) which is currently designed at our lab.
An Architecture Framework for Complex Data Warehouses
Venue: arXiv cs.DB 2007
Year: 2007

Nowadays, many decision support applications need to exploit data that are not only numerical or symbolic, but also multimedia, multistructure, multisource, multimodal, and/or multiversion. We term such data complex data. Managing and analyzing complex data involves a lot of different issues regarding their structure, storage and processing, and metadata are a key element in all these processes. Such problems have been addressed by classical data warehousing (i.e., applied to "simple" data). However, data warehousing approaches need to be adapted for complex data. In this paper, we first propose a precise, though open, definition of complex data. Then we present a general architecture framework for warehousing complex data. This architecture heavily relies on metadata and domain-related knowledge, and rests on the XML language, which helps storing data, metadata and domain-specific knowledge altogether, and facilitates communication between the various warehousing processes.
Autonomy with regard to an Attribute
Venue: arXiv cs.MA 2007
Year: 2007

This paper presents a model of autonomy called autonomy with regard to an attribute applicable to cognitive and not cognitive artificial agents. Three criteria (global / partial, social / nonsocial, absolute / relative) are defined and used to describe the main characteristics of this type of autonomy. A software agent autonomous with regard to the mobility illustrates a possible implementation of this model.
A Tight Lower Bound to the Outage Probability of Discrete-Input Block-Fading Channels
Venue: arXiv cs.IT 2007
Year: 2007

In this correspondence, we propose a tight lower bound to the outage probability of discrete-input Nakagami-m block-fading channels. The approach permits an efficient method for numerical evaluation of the bound, providing an additional tool for system design. The optimal rate-diversity trade-off for the Nakagami-m block-fading channel is also derived and a tight upper bound is obtained for the optimal coding gain constant.
Cactus Framework: Black Holes to Gamma Ray Bursts
Venue: arXiv cs.DC 2007
Year: 2007

Gamma Ray Bursts (GRBs) are intense narrowly-beamed flashes of gamma-rays of cosmological origin. They are among the most scientifically interesting astrophysical systems, and the riddle concerning their central engines and emission mechanisms is one of the most complex and challenging problems of astrophysics today. In this article we outline our petascale approach to the GRB problem and discuss the computational toolkits and numerical codes that are currently in use and that will be scaled up to run on emerging petaflop scale computing platforms in the near future. Petascale computing will require additional ingredients over conventional parallelism. We consider some of the challenges which will be caused by future petascale architectures, and discuss our plans for the future development of the Cactus framework and its applications to meet these challenges in order to profit from these new architectures.
On slow-fading non-separable correlation MIMO systems
Venue: arXiv cs.IT 2007
Year: 2007

In a frequency selective slow-fading channel in a MIMO system, the channel matrix is of the form of a block matrix. We propose a method to calculate the limit of the eigenvalue distribution of block matrices if the size of the blocks tends to infinity. We will also calculate the asymptotic eigenvalue distribution of $HH^*$, where the entries of $H$ are jointly Gaussian, with a correlation of the form $E[h_{pj}\bar h_{qk}]= \sum_{s=1}^t Ψ^{(s)}_{jk}\hatΨ^{(s)}_{pq}$ (where $t$ is fixed and does not increase with the size of the matrix). We will use an operator-valued free probability approach to achieve this goal. Using this method, we derive a system of equations, which can be solved numerically to compute the desired eigenvalue distribution.
On trees with a maximum proper partial 0-1 coloring containing a maximum matching
Venue: arXiv cs.DM 2007
Year: 2007

I prove that in a tree in which the distance between any two endpoints is even, there is a maximum proper partial 0-1 coloring such that the edges colored by 0 form a maximum matching.
Bandlimited Field Reconstruction for Wireless Sensor Networks
Venue: arXiv cs.OH 2007
Year: 2007

Wireless sensor networks are often used for environmental monitoring applications. In this context sampling and reconstruction of a physical field is one of the most important problems to solve. We focus on a bandlimited field and find under which conditions on the network topology the reconstruction of the field is successful, with a given probability. We review irregular sampling theory, and analyze the problem using random matrix theory. We show that even a very irregular spatial distribution of sensors may lead to a successful signal reconstruction, provided that the number of collected samples is large enough with respect to the field bandwidth. Furthermore, we give the basis to analytically determine the probability of successful field reconstruction.
Splay Trees, Davenport-Schinzel Sequences, and the Deque Conjecture
Venue: arXiv cs.DS 2007
Year: 2007

We introduce a new technique to bound the asymptotic performance of splay trees. The basic idea is to transcribe, in an indirect fashion, the rotations performed by the splay tree as a Davenport-Schinzel sequence S, none of whose subsequences are isomorphic to fixed forbidden subsequence. We direct this technique towards Tarjan's deque conjecture and prove that n deque operations require O(n alpha^*(n)) time, where alpha^*(n) is the minimum number of applications of the inverse-Ackermann function mapping n to a constant. We are optimistic that this approach could be directed towards other open conjectures on splay trees such as the traversal and split conjectures.
Design of Multistage Decimation Filters Using Cyclotomic Polynomials: Optimization and Design Issues
Venue: arXiv cs.OH 2007
Year: 2007

This paper focuses on the design of multiplier-less decimation filters suitable for oversampled digital signals. The aim is twofold. On one hand, it proposes an optimization framework for the design of constituent decimation filters in a general multistage decimation architecture. The basic building blocks embedded in the proposed filters belong, for a simple reason, to the class of cyclotomic polynomials (CPs): the first 104 CPs have a z-transfer function whose coefficients are simply {-1,0,+1}. On the other hand, the paper provides a bunch of useful techniques, most of which stemming from some key properties of CPs, for designing the proposed filters in a variety of architectures. Both recursive and non-recursive architectures are discussed by focusing on a specific decimation filter obtained as a result of the optimization algorithm. Design guidelines are provided with the aim to simplify the design of the constituent decimation filters in the multistage chain.
Word statistics in Blogs and RSS feeds: Towards empirical universal evidence
Venue: arXiv cs.IT 2007
Year: 2007

We focus on the statistics of word occurrences and of the waiting times between such occurrences in Blogs. Due to the heterogeneity of words' frequencies, the empirical analysis is performed by studying classes of "frequently-equivalent" words, i.e. by grouping words depending on their frequencies. Two limiting cases are considered: the dilute limit, i.e. for those words that are used less than once a day, and the dense limit for frequent words. In both cases, extreme events occur more frequently than expected from the Poisson hypothesis. These deviations from Poisson statistics reveal non-trivial time correlations between events that are associated with bursts of activities. The distribution of waiting times is shown to behave like a stretched exponential and to have the same shape for different sets of words sharing a common frequency, thereby revealing universal features.
The Computation of All 4R Serial Spherical Wrists With an Isotropic Architecture
Venue: arXiv cs.RO 2007
Year: 2007

A spherical wrist of the serial type with n revolute (R) joints is said to be isotropic if it can attain a posture whereby the singular values of its Jacobian matrix are all equal to sqrt(n/3). What isotropy brings about is robustness to manufacturing, assembly, and measurement errors, thereby guaranteeing a maximum orientation accuracy. In this paper we investigate the existence of redundant isotropic architectures, which should add to the dexterity of the wrist under design by virtue of its extra degree of freedom. The problem formulation, for, leads to a system of eight quadratic equations with eight unknowns. The Bezout number of this system is thus 2^8=256, its BKK bound being 192. However, the actual number of solutions is shown to be 32. We list all solutions of the foregoing algebraic problem. All these solutions are real, but distinct solutions do not necessarily lead to distinct manipulators. Upon discarding those algebraic solutions that yield no new wrists, we end up with exactly eight distinct architectures, the eight corresponding manipulators being displayed at their isotropic postures.
Separable convex optimization problems with linear ascending constraints
Venue: arXiv cs.IT 2007
Year: 2007

Separable convex optimization problems with linear ascending inequality and equality constraints are addressed in this paper. Under an ordering condition on the slopes of the functions at the origin, an algorithm that determines the optimum point in a finite number of steps is described. The optimum value is shown to be monotone with respect to a partial order on the constraint parameters. Moreover, the optimum value is convex with respect to these parameters. Examples motivated by optimizations for communication systems are used to illustrate the algorithm.
A Characterisation of First-Order Constraint Satisfaction Problems
Venue: arXiv cs.LO 2007
Year: 2007

We describe simple algebraic and combinatorial characterisations of finite relational core structures admitting finitely many obstructions. As a consequence, we show that it is decidable to determine whether a constraint satisfaction problem is first-order definable: we show the general problem to be NP-complete, and give a polynomial-time algorithm in the case of cores. A slight modification of this algorithm provides, for first-order definable CSP's, a simple poly-time algorithm to produce a solution when one exists. As an application of our algebraic characterisation of first order CSP's, we describe a large family of L-complete CSP's.
A Framework to Illustrate Kinematic Behavior of Mechanisms by Haptic Feedback
Venue: arXiv cs.RO 2007
Year: 2007

The kinematic properties of mechanisms are well known by the researchers and teachers. The theory based on the study of Jacobian matrices allows us to explain, for example, the singular configuration. However, in many cases, the physical sense of such properties is difficult to explain to students. The aim of this article is to use haptic feedback to render to the user the signification of different kinematic indices. The framework uses a Phantom Omni and a serial and parallel mechanism with two degrees of freedom. The end-effector of both mechanisms can be moved either by classical mouse, or Phantom Omni with or without feedback.
On the ergodic sum-rate performance of CDD in multi-user systems
Venue: arXiv cs.IT 2007
Year: 2007

The main focus of space-time coding design and analysis for MIMO systems has been so far focused on single-user systems. For single-user systems, transmit diversity schemes suffer a loss in spectral efficiency if the receiver is equipped with more than one antenna, making them unsuitable for high rate transmission. One such transmit diversity scheme is the cyclic delay diversity code (CDD). The advantage of CDD over other diversity schemes such as orthogonal space-time block codes (OSTBC) is that a code rate of one and delay optimality are achieved independent of the number of transmit antennas. In this work we analyze the ergodic rate of a multi-user multiple access channel (MAC) with each user applying such a cyclic delay diversity (CDD) code. We derive closed form expressions for the ergodic sum-rate of multi-user CDD and compare it with the sum-capacity. We study the ergodic rate region and show that in contrast to what is conventionally known regarding the single-user case, transmit diversity schemes are viable candidates for high rate transmission in multi-user systems. Finally, our theoretical findings are illustrated by numerical simulation results.
Building a Cooperative Communications System
Venue: arXiv cs.IT 2007
Year: 2007

In this paper, we present the results from over-the-air experiments of a complete implementation of an amplify and forward cooperative communications system. Our custom OFDM-based physical layer uses a distributed version of the Alamouti block code, where the relay sends one branch of Alamouti encoded symbols. First we show analytically and experimentally that amplify and forward protocols are unaffected by carrier frequency offsets at the relay. This result allows us to use a conventional Alamouti receiver without change for the distributed relay system. Our full system implementation shows gains up to 5.5dB in peak power constrained networks. Thus, we can conclusively state that even the simplest form of relaying can lead to significant gains in practical implementations.