OpenRaiser/Intern-Atlas huggingface dataset:
Resource Usage Analysis for the Pi-Calculus
Venue: arXiv cs.PL 2006
Year: 2006

We propose a type-based resource usage analysis for the π-calculus extended with resource creation/access primitives. The goal of the resource usage analysis is to statically check that a program accesses resources such as files and memory in a valid manner. Our type system is an extension of previous behavioral type systems for the π-calculus, and can guarantee the safety property that no invalid access is performed, as well as the property that necessary accesses (such as the close operation for a file) are eventually performed unless the program diverges. A sound type inference algorithm for the type system is also developed to free the programmer from the burden of writing complex type annotations. Based on the algorithm, we have implemented a prototype resource usage analyzer for the π-calculus. To the authors' knowledge, ours is the first type-based resource usage analysis that deals with an expressive concurrent language like the pi-calculus.
Morphisms of Coloured Petri Nets
Venue: arXiv cs.SE 2006
Year: 2006

We introduce the concept of a morphism between coloured nets. Our definition generalizes Petris definition for ordinary nets. A morphism of coloured nets maps the topological space of the underlying undirected net as well as the kernel and cokernel of the incidence map. The kernel are flows along the transition-bordered fibres of the morphism, the cokernel are classes of markings of the place-bordered fibres. The attachment of bindings, colours, flows and marking classes to a subnet is formalized by using concepts from sheaf theory. A coloured net is a sheaf-cosheaf pair over a Petri space and a morphism between coloured nets is a morphism between such pairs. Coloured nets and their morphisms form a category. We prove the existence of a product in the subcategory of sort-respecting morphisms. After introducing markings our concepts generalize to coloured Petri nets.
Using Users' Expectations to Adapt Business Intelligence Systems
Venue: arXiv cs.IR 2006
Year: 2006

This paper takes a look at the general characteristics of business or economic intelligence system. The role of the user within this type of system is emphasized. We propose two models which we consider important in order to adapt this system to the user. The first model is based on the definition of decisional problem and the second on the four cognitive phases of human learning. We also describe the application domain we are using to test these models in this type of system.
From Grid Middleware to a Grid Operating System
Venue: arXiv cs.DC 2006
Year: 2006

Grid computing has made substantial advances during the last decade. Grid middleware such as Globus has contributed greatly in making this possible. There are, however, significant barriers to the adoption of Grid computing in other fields, most notably day-to-day user computing environments. We will demonstrate in this paper that this is primarily due to the limitations of the existing Grid middleware which does not take into account the needs of everyday scientific and business users. In this paper we will formally advocate a Grid Operating System and propose an architecture to migrate Grid computing into a Grid operating system which we believe would help remove most of the technical barriers to the adoption of Grid computing and make it relevant to the day-to-day user. We believe this proposed transition to a Grid operating system will drive more pervasive Grid computing research and application development and deployment in future.
Bulk Scheduling with the DIANA Scheduler
Venue: arXiv cs.DC 2006
Year: 2006

Results from the research and development of a Data Intensive and Network Aware (DIANA) scheduling engine, to be used primarily for data intensive sciences such as physics analysis, are described. In Grid analyses, tasks can involve thousands of computing, data handling, and network resources. The central problem in the scheduling of these resources is the coordinated management of computation and data at multiple locations and not just data replication or movement. However, this can prove to be a rather costly operation and efficient sing can be a challenge if compute and data resources are mapped without considering network costs. We have implemented an adaptive algorithm within the so-called DIANA Scheduler which takes into account data location and size, network performance and computation capability in order to enable efficient global scheduling. DIANA is a performance-aware and economy-guided Meta Scheduler. It iteratively allocates each job to the site that is most likely to produce the best performance as well as optimizing the global queue for any remaining jobs. Therefore it is equally suitable whether a single job is being submitted or bulk scheduling is being performed. Results indicate that considerable performance improvements can be gained by adopting the DIANA scheduling approach.
Searching for Globally Optimal Functional Forms for Inter-Atomic Potentials Using Parallel Tempering and Genetic Programming
Venue: arXiv cs.NE 2006
Year: 2006

We develop a Genetic Programming-based methodology that enables discovery of novel functional forms for classical inter-atomic force-fields, used in molecular dynamics simulations. Unlike previous efforts in the field, that fit only the parameters to the fixed functional forms, we instead use a novel algorithm to search the space of many possible functional forms. While a follow-on practical procedure will use experimental and {\it ab inito} data to find an optimal functional form for a forcefield, we first validate the approach using a manufactured solution. This validation has the advantage of a well-defined metric of success. We manufactured a training set of atomic coordinate data with an associated set of global energies using the well-known Lennard-Jones inter-atomic potential. We performed an automatic functional form fitting procedure starting with a population of random functions, using a genetic programming functional formulation, and a parallel tempering Metropolis-based optimization algorithm. Our massively-parallel method independently discovered the Lennard-Jones function after searching for several hours on 100 processors and covering a miniscule portion of the configuration space. We find that the method is suitable for unsupervised discovery of functional forms for inter-atomic potentials/force-fields. We also find that our parallel tempering Metropolis-based approach significantly improves the optimization convergence time, and takes good advantage of the parallel cluster architecture.
Competition and Request Routing Policies in Content Delivery Networks
Venue: arXiv cs.NI 2006
Year: 2006

The role of competition and monetary benefits in the design of Content Delivery Networks (CDNs) is largely an unexplored area. In this paper, we investigate the effect of competition among the competitive web based CDNs and show that little difference in their performance may cause significant financial gain/loss. It turns out that the economy of scale effect is very significant for the success of a CDN in a competitive market. So CDN peering might be a good idea. Since performance and conforming to the service level agreement (SLA) with content providers is very important, we then focus on designing CDN from this perspective. We provide an asymptotically optimal static request routing policy for a CDN under a model where a CDN company guarantees a certain level of user latency to the content providers in the SLA.
Wireless ad-hoc networks: Strategies and Scaling laws for the fixed SNR regime
Venue: arXiv cs.IT 2006
Year: 2006

This paper deals with throughput scaling laws for random ad-hoc wireless networks in a rich scattering environment. We develop schemes to optimize the ratio, $ρ(n)$ of achievable network sum capacity to the sum of the point-to-point capacities of source-destinations pairs operating in isolation. For fixed SNR networks, i.e., where the worst case SNR over the source-destination pairs is fixed independent of $n$, we show that collaborative strategies yield a scaling law of $ρ(n) = {\cal O}(\frac{1}{n^{1/3}})$ in contrast to multi-hop strategies which yield a scaling law of $ρ(n) = {\cal O}(\frac{1}{\sqrt{n}})$. While, networks where worst case SNR goes to zero, do not preclude the possibility of collaboration, multi-hop strategies achieve optimal throughput. The plausible reason is that the gains due to collaboration cannot offset the effect of vanishing receive SNR. This suggests that for fixed SNR networks, a network designer should look for network protocols that exploit collaboration. The fact that most current networks operate in a fixed SNR interference limited environment provides further motivation for considering this regime.
Improved Content Based Image Watermarking
Venue: arXiv cs.CR 2006
Year: 2006

This paper presents a robust and transparent scheme of watermarking that exploits the human visual systems' sensitivity to frequency, along with local image characteristics obtained from the spatial domain. The underlying idea is generating a visual mask based on the visual systems' perception of image content. This mask is used to embed a decimal sequence while keeping its amplitude below the distortion sensitivity of the image pixel. We consider texture, luminance, corner and the edge information in the image to generate a mask that makes the addition of the watermark imperceptible to the human eye.
Analysis of a Reputation System for Mobile Ad-Hoc Networks with Liars
Venue: arXiv cs.PF 2006
Year: 2006

The application of decentralized reputation systems is a promising approach to ensure cooperation and fairness, as well as to address random failures and malicious attacks in Mobile Ad-Hoc Networks. However, they are potentially vulnerable to liars. With our work, we provide a first step to analyzing robustness of a reputation system based on a deviation test. Using a mean-field approach to our stochastic process model, we show that liars have no impact unless their number exceeds a certain threshold (phase transition). We give precise formulae for the critical values and thus provide guidelines for an optimal choice of parameters.
Application Layer Definition and Analyses of Controller Area Network Bus for Wire Harness Assembly Machine
Venue: arXiv cs.RO 2006
Year: 2006

With the feature of multi-master bus access, nondestructive contention-based arbitration and flexible configuration, Controller Area Network (CAN) bus is applied into the control system of Wire Harness Assembly Machine (WHAM). To accomplish desired goal, the specific features of the CAN bus is analyzed by compared with other field buses and the functional performances in the CAN bus system of WHAM is discussed. Then the application layer planning of CAN bus for dynamic priority is presented. The critical issue for the use of CAN bus system in WHAM is the data transfer rate between different nodes. So processing efficient model is introduced to assist analyzing data transfer procedure. Through the model, it is convenient to verify the real time feature of the CAN bus system in WHAM.
Realistic Boundary Conditions for Ad Hoc Network Node Mobility Models and a New Approach to the Random Waypoint Model
Venue: arXiv cs.NI 2006
Year: 2006

In this paper, we examine the cause of the border effect observed in many mobility models used to construct simulations of ad hoc networking protocol performance. We specify conditions under which a node mobility model must produce spatial mobile node distribution functions that obey the diffusion equation. In particular demonstrate that these conditions are satisfied by the random direction (RD) model. We show that it is possible to construct mobility models that attain uniform steady-state distributions without resorting to reflection or ``wrapping'' of nodes at the border of a test region. Finally, we show that the random waypoint (RWP) model may be reproduced by the application of a ``volume rule'' to an RD model. This volume rule violates the assumptions that lead to the diffusion equation. We suggest a generalization of the RWP model that can provide more uniform mobile node distributions.
Reliable multicast fault tolerant MPI in the Grid environment
Venue: arXiv cs.DC 2006
Year: 2006

Grid environments have recently been developed with low stretch and overheads that increase with the logarithm of the number of nodes in the system. Getting and sending data to/from a large numbers of nodes is gaining importance due to an increasing number of independent data providers and the heterogeneity of the network/Grid. One of the key challenges is to achieve a balance between low bandwidth consumption and good reliability. In this paper we present an implementation of a reliable multicast protocol over a fault tolerant MPI: MPICHV2. It can provide one way to solve the problem of transferring large chunks of data between applications running on a grid with limited network links. We first show that we can achieve similar performance as the MPICH-P4 implementation by using multicast with data compression in a cluster. Next, we provide a theoretical cluster organization and GRID network architecture to harness the performance provided by using multicast. Finally, we present the conclusion and future work.
TreeP: A Tree-Based P2P Network Architecture
Venue: arXiv cs.DC 2006
Year: 2006

In this paper we proposed a hierarchical P2P network based on a dynamic partitioning on a 1-D space. This hierarchy is created and maintained dynamically and provides a gridmiddleware (like DGET) a P2P basic functionality for resource discovery and load-balancing.This network architecture is called TreeP (Tree based P2P network architecture) and is based on atessellation of a 1-D space. We show that this topology exploits in an efficient way theheterogeneity feature of the network while limiting the overhead introduced by the overlaymaintenance. Experimental results show that this topology is highly resilient to a large number ofnetwork failures.
Decidability of Type-checking in the Calculus of Algebraic Constructions with Size Annotations
Venue: arXiv cs.LO 2006
Year: 2006

Since Val Tannen's pioneer work on the combination of simply-typed lambda-calculus and first-order rewriting (LICS'88), many authors have contributed to this subject by extending it to richer typed lambda-calculi and rewriting paradigms, culminating in calculi like the Calculus of Algebraic Constructions. These works provide theoretical foundations for type-theoretic proof assistants where functions and predicates are defined by oriented higher-order equations. This kind of definitions subsumes induction-based definitions, is easier to write and provides more automation. On the other hand, checking that user-defined rewrite rules are strongly normalizing and confluent, and preserve the decidability of type-checking when combined with beta-reduction, is more difficult. Most termination criteria rely on the term structure. In a previous work, we extended to dependent types and higher-order rewriting, the notion of ``sized types'' studied by several authors in the simpler framework of ML-like languages, and proved that it preserves strong normalization. The main contribution of the present paper is twofold. First, we prove that, in the Calculus of Algebraic Constructions with size annotations, the problems of type inference and type-checking are decidable, provided that the sets of constraints generated by size annotations are satisfiable and admit most general solutions. Second, we prove the later properties for a size algebra rich enough for capturing usual induction-based definitions and much more.
An effective edge--directed frequency filter for removal of aliasing in upsampled images
Venue: arXiv cs.CV 2006
Year: 2006

Raster images can have a range of various distortions connected to their raster structure. Upsampling them might in effect substantially yield the raster structure of the original image, known as aliasing. The upsampling itself may introduce aliasing into the upsampled image as well. The presented method attempts to remove the aliasing using frequency filters based on the discrete fast Fourier transform, and applied directionally in certain regions placed along the edges in the image. As opposed to some anisotropic smoothing methods, the presented algorithm aims to selectively reduce only the aliasing, preserving the sharpness of image details. The method can be used as a post--processing filter along with various upsampling algorithms. It was experimentally shown that the method can improve the visual quality of the upsampled images.
Residual Finite Tree Automata
Venue: arXiv cs.CC 2006
Year: 2006

Tree automata based algorithms are essential in many fields in computer science such as verification, specification, program analysis. They become also essential for databases with the development of standards such as XML. In this paper, we define new classes of non deterministic tree automata, namely residual finite tree automata (RFTA). In the bottom-up case, we obtain a new characterization of regular tree languages. In the top-down case, we obtain a subclass of regular tree languages which contains the class of languages recognized by deterministic top-down tree automata. RFTA also come with the property of existence of canonical non deterministic tree automata.
Rarest First and Choke Algorithms Are Enough
Venue: arXiv cs.NI 2006
Year: 2006

The performance of peer-to-peer file replication comes from its piece and peer selection strategies. Two such strategies have been introduced by the BitTorrent protocol: the rarest first and choke algorithms. Whereas it is commonly admitted that BitTorrent performs well, recent studies have proposed the replacement of the rarest first and choke algorithms in order to improve efficiency and fairness. In this paper, we use results from real experiments to advocate that the replacement of the rarest first and choke algorithms cannot be justified in the context of peer-to-peer file replication in the Internet. We instrumented a BitTorrent client and ran experiments on real torrents with different characteristics. Our experimental evaluation is peer oriented, instead of tracker oriented, which allows us to get detailed information on all exchanged messages and protocol events. We go beyond the mere observation of the good efficiency of both algorithms. We show that the rarest first algorithm guarantees close to ideal diversity of the pieces among peers. In particular, on our experiments, replacing the rarest first algorithm with source or network coding solutions cannot be justified. We also show that the choke algorithm in its latest version fosters reciprocation and is robust to free riders. In particular, the choke algorithm is fair and its replacement with a bit level tit-for-tat solution is not appropriate. Finally, we identify new areas of improvements for efficient peer-to-peer file replication protocols.
Reversible Programmable Logic Array (RPLA) using Fredkin & Feynman Gates for Industrial Electronics and Applications
Venue: arXiv cs.AR 2006
Year: 2006

In recent years, reversible logic has emerged as a promising computing paradigm having application in low power CMOS, quantum computing, nanotechnology, and optical computing. The classical set of gates such as AND, OR, and EXOR are not reversible. In this paper, the authors have proposed reversible programmable logic array (RPLA) architecture using reversible Fredkin and Feynman gates. The proposed RPLA has n inputs and m outputs and can realize m functions of n variables. In order to demonstrate the design of RPLA, a 3 input RPLA is designed which can perform any 28 functions using the combination of 8 min terms (23). Furthermore, the application of the designed 3 input RPLA is shown by implementing the full adder and full subtractor functions through it.
CR-precis: A deterministic summary structure for update data streams
Venue: arXiv cs.DS 2006
Year: 2006

We present the \crprecis structure, that is a general-purpose, deterministic and sub-linear data structure for summarizing \emph{update} data streams. The \crprecis structure yields the \emph{first deterministic sub-linear space/time algorithms for update streams} for answering a variety of fundamental stream queries, such as, (a) point queries, (b) range queries, (c) finding approximate frequent items, (d) finding approximate quantiles, (e) finding approximate hierarchical heavy hitters, (f) estimating inner-products, (g) near-optimal $B$-bucket histograms, etc..
Elgot Algebras
Venue: arXiv cs.LO 2006
Year: 2006

Denotational semantics can be based on algebras with additional structure (order, metric, etc.) which makes it possible to interpret recursive specifications. It was the idea of Elgot to base denotational semantics on iterative theories instead, i.e., theories in which abstract recursive specifications are required to have unique solutions. Later Bloom and Esik studied iteration theories and iteration algebras in which a specified solution has to obey certain axioms. We propose so-called Elgot algebras as a convenient structure for semantics in the present paper. An Elgot algebra is an algebra with a specified solution for every system of flat recursive equations. That specification satisfies two simple and well motivated axioms: functoriality (stating that solutions are stable under renaming of recursion variables) and compositionality (stating how to perform simultaneous recursion). These two axioms stem canonically from Elgot's iterative theories: We prove that the category of Elgot algebras is the Eilenberg-Moore category of the monad given by a free iterative theory.
Metric entropy in competitive on-line prediction
Venue: arXiv cs.LG 2006
Year: 2006

Competitive on-line prediction (also known as universal prediction of individual sequences) is a strand of learning theory avoiding making any stochastic assumptions about the way the observations are generated. The predictor's goal is to compete with a benchmark class of prediction rules, which is often a proper Banach function space. Metric entropy provides a unifying framework for competitive on-line prediction: the numerous known upper bounds on the metric entropy of various compact sets in function spaces readily imply bounds on the performance of on-line prediction strategies. This paper discusses strengths and limitations of the direct approach to competitive on-line prediction via metric entropy, including comparisons to other approaches.
Coding for Additive White Noise Channels with Feedback Corrupted by Uniform Quantization or Bounded Noise
Venue: arXiv cs.IT 2006
Year: 2006

We present simple coding strategies, which are variants of the Schalkwijk-Kailath scheme, for communicating reliably over additive white noise channels in the presence of corrupted feedback. More specifically, we consider a framework comprising an additive white forward channel and a backward link which is used for feedback. We consider two types of corruption mechanisms in the backward link. The first is quantization noise, i.e., the encoder receives the quantized values of the past outputs of the forward channel. The quantization is uniform, memoryless and time invariant (that is, symbol-by-symbol scalar quantization), with bounded quantization error. The second corruption mechanism is an arbitrarily distributed additive bounded noise in the backward link. Here we allow symbol-by-symbol encoding at the input to the backward channel. We propose simple explicit schemes that guarantee positive information rate, in bits per channel use, with positive error exponent. If the forward channel is additive white Gaussian then our schemes achieve capacity, in the limit of diminishing amplitude of the noise components at the backward link, while guaranteeing that the probability of error converges to zero as a doubly exponential function of the block length. Furthermore, if the forward channel is additive white Gaussian and the backward link consists of an additive bounded noise channel, with signal-to-noise ratio (SNR) constrained symbol-by-symbol encoding, then our schemes are also capacity-achieving in the limit of high SNR.