OpenRaiser/Intern-Atlas huggingface dataset:
Power-Efficient Direct-Voting Assurance for Data Fusion in Wireless Sensor Networks
Venue: arXiv cs.CR 2007
Year: 2007

Wireless sensor networks place sensors into an area to collect data and send them back to a base station. Data fusion, which fuses the collected data before they are sent to the base station, is usually implemented over the network. Since the sensor is typically placed in locations accessible to malicious attackers, information assurance of the data fusion process is very important. A witness-based approach has been proposed to validate the fusion data. In this approach, the base station receives the fusion data and "votes" on the data from a randomly chosen sensor node. The vote comes from other sensor nodes, called "witnesses," to verify the correctness of the fusion data. Because the base station obtains the vote through the chosen node, the chosen node could forge the vote if it is compromised. Thus, the witness node must encrypt the vote to prevent this forgery. Compared with the vote, the encryption requires more bits, increasing transmission burden from the chosen node to the base station. The chosen node consumes more power. This work improves the witness-based approach using direct voting mechanism such that the proposed scheme has better performance in terms of assurance, overhead, and delay. The witness node transmits the vote directly to the base station. Forgery is not a problem in this scheme. Moreover, fewer bits are necessary to represent the vote, significantly reducing the power consumption. Performance analysis and simulation results indicate that the proposed approach can achieve a 40 times better overhead than the witness-based approach.
Secure Two-party Protocols for Point Inclusion Problem
Venue: arXiv cs.CR 2007
Year: 2007

It is well known that, in theory, the general secure multi-party computation problem is solvable using circuit evaluation protocols. However, the communication complexity of the resulting protocols depend on the size of the circuit that expresses the functionality to be computed and hence can be impractical. Hence special solutions are needed for specific problems for efficiency reasons. The point inclusion problem in computational geometry is a special multiparty computation and has got many applications. Previous protocols for the secure point inclusion problem are not adequate. In this paper we modify some known solutions to the point inclusion problem in computational geometry to the frame work of secure two-party computation.
Towards an exact adaptive algorithm for the determinant of a rational matrix
Venue: arXiv cs.SC 2007
Year: 2007

In this paper we propose several strategies for the exact computation of the determinant of a rational matrix. First, we use the Chinese Remaindering Theorem and the rational reconstruction to recover the rational determinant from its modular images. Then we show a preconditioning for the determinant which allows us to skip the rational reconstruction process and reconstruct an integer result. We compare those approaches with matrix preconditioning which allow us to treat integer instead of rational matrices. This allows us to introduce integer determinant algorithms to the rational determinant problem. In particular, we discuss the applicability of the adaptive determinant algorithm of [9] and compare it with the integer Chinese Remaindering scheme. We present an analysis of the complexity of the strategies and evaluate their experimental performance on numerous examples. This experience allows us to develop an adaptive strategy which would choose the best solution at the run time, depending on matrix properties. All strategies have been implemented in LinBox linear algebra library.
Challenges and Opportunities of Evolutionary Robotics
Venue: arXiv cs.NE 2007
Year: 2007

Robotic hardware designs are becoming more complex as the variety and number of on-board sensors increase and as greater computational power is provided in ever-smaller packages on-board robots. These advances in hardware, however, do not automatically translate into better software for controlling complex robots. Evolutionary techniques hold the potential to solve many difficult problems in robotics which defy simple conventional approaches, but present many challenges as well. Numerous disciplines including artificial life, cognitive science and neural networks, rule-based systems, behavior-based control, genetic algorithms and other forms of evolutionary computation have contributed to shaping the current state of evolutionary robotics. This paper provides an overview of developments in the emerging field of evolutionary robotics, and discusses some of the opportunities and challenges which currently face practitioners in the field.
WACA: A Hierarchical Weighted Clustering Algorithm optimized for Mobile Hybrid Networks
Venue: arXiv cs.DC 2007
Year: 2007

Clustering techniques create hierarchal network structures, called clusters, on an otherwise flat network. In a dynamic environment-in terms of node mobility as well as in terms of steadily changing device parameters-the clusterhead election process has to be re-invoked according to a suitable update policy. Cluster re-organization causes additional message exchanges and computational complexity and it execution has to be optimized. Our investigations focus on the problem of minimizing clusterhead re-elections by considering stability criteria. These criteria are based on topological characteristics as well as on device parameters. This paper presents a weighted clustering algorithm optimized to avoid needless clusterhead re-elections for stable clusters in mobile ad-hoc networks. The proposed localized algorithm deals with mobility, but does not require geographical, speed or distances information.
Sublinear Algorithms for Approximating String Compressibility
Venue: arXiv cs.DS 2007
Year: 2007

We raise the question of approximating the compressibility of a string with respect to a fixed compression scheme, in sublinear time. We study this question in detail for two popular lossless compression schemes: run-length encoding (RLE) and Lempel-Ziv (LZ), and present sublinear algorithms for approximating compressibility with respect to both schemes. We also give several lower bounds that show that our algorithms for both schemes cannot be improved significantly. Our investigation of LZ yields results whose interest goes beyond the initial questions we set out to study. In particular, we prove combinatorial structural lemmas that relate the compressibility of a string with respect to Lempel-Ziv to the number of distinct short substrings contained in it. In addition, we show that approximating the compressibility with respect to LZ is related to approximating the support size of a distribution.
Automatically Restructuring Practice Guidelines using the GEM DTD
Venue: arXiv cs.AI 2007
Year: 2007

This paper describes a system capable of semi-automatically filling an XML template from free texts in the clinical domain (practice guidelines). The XML template includes semantic information not explicitly encoded in the text (pairs of conditions and actions/recommendations). Therefore, there is a need to compute the exact scope of conditions over text sequences expressing the required actions. We present a system developed for this task. We show that it yields good performance when applied to the analysis of French practice guidelines.
Vector Precoding for Wireless MIMO Systems: A Replica Analysis
Venue: arXiv cs.IT 2007
Year: 2007

We apply the replica method to analyze vector precoding, a method to reduce transmit power in antenna array communications. The analysis applies to a very general class of channel matrices. The statistics of the channel matrix enter the transmitted energy per symbol via its R-transform. We find that vector precoding performs much better for complex than for real alphabets. As a byproduct, we find a nonlinear precoding method with polynomial complexity that outperforms NP-hard Tomlinson-Harashima precoding for binary modulation on complex channels if the number of transmit antennas is slightly larger than twice the number of receive antennas.
A Generic Model of Contracts for Embedded Systems
Venue: arXiv cs.SE 2007
Year: 2007

We present the mathematical foundations of the contract-based model developed in the framework of the SPEEDS project. SPEEDS aims at developing methods and tools to support "speculative design", a design methodology in which distributed designers develop different aspects of the overall system, in a concurrent but controlled way. Our generic mathematical model of contract supports this style of development. This is achieved by focusing on behaviors, by supporting the notion of "rich component" where diverse (functional and non-functional) aspects of the system can be considered and combined, by representing rich components via their set of associated contracts, and by formalizing the whole process of component composition.
Another Proof of Wright's Inequalities
Venue: arXiv cs.DM 2007
Year: 2007

We present a short way of proving the inequalities obtained by Wright in [Journal of Graph Theory, 4: 393 - 407 (1980)] concerning the number of connected graphs with $\ell$ edges more than vertices.
Towards understanding and modelling office daily life
Venue: arXiv cs.CV 2007
Year: 2007

Measuring and modeling human behavior is a very complex task. In this paper we present our initial thoughts on modeling and automatic recognition of some human activities in an office. We argue that to successfully model human activities, we need to consider both individual behavior and group dynamics. To demonstrate these theoretical approaches, we introduce an experimental system for analyzing everyday activity in our office.
Critique of Feinstein's Proof that P is not Equal to NP
Venue: arXiv cs.CC 2007
Year: 2007

We examine a proof by Craig Alan Feinstein that P is not equal to NP. We present counterexamples to claims made in his paper and expose a flaw in the methodology he uses to make his assertions. The fault in his argument is the incorrect use of reduction. Feinstein makes incorrect assumptions about the complexity of a problem based on the fact that there is a more complex problem that can be used to solve it. His paper introduces the terminology "imaginary processor" to describe how it is possible to beat the brute force reduction he offers to solve the Subset-Sum problem. The claims made in the paper would not be validly established even were imaginary processors to exist.
A Finite Semantics of Simply-Typed Lambda Terms for Infinite Runs of<br> Automata
Venue: arXiv cs.LO 2007
Year: 2007

Model checking properties are often described by means of finite automata. Any particular such automaton divides the set of infinite trees into finitely many classes, according to which state has an infinite run. Building the full type hierarchy upon this interpretation of the base type gives a finite semantics for simply-typed lambda-trees. A calculus based on this semantics is proven sound and complete. In particular, for regular infinite lambda-trees it is decidable whether a given automaton has a run or not. As regular lambda-trees are precisely recursion schemes, this decidability result holds for arbitrary recursion schemes of arbitrary level, without any syntactical restriction.
Progresses in the Analysis of Stochastic 2D Cellular Automata: a Study of Asynchronous 2D Minority
Venue: arXiv cs.DM 2007
Year: 2007

Cellular automata are often used to model systems in physics, social sciences, biology that are inherently asynchronous. Over the past 20 years, studies have demonstrated that the behavior of cellular automata drastically changed under asynchronous updates. Still, the few mathematical analyses of asynchronism focus on one-dimensional probabilistic cellular automata, either on single examples or on specific classes. As for other classic dynamical systems in physics, extending known methods from one- to two-dimensional systems is a long lasting challenging problem. In this paper, we address the problem of analysing an apparently simple 2D asynchronous cellular automaton: 2D Minority where each cell, when fired, updates to the minority state of its neighborhood. Our experiments reveal that in spite of its simplicity, the minority rule exhibits a quite complex response to asynchronism. By focusing on the fully asynchronous regime, we are however able to describe completely the asymptotic behavior of this dynamics as long as the initial configuration satisfies some natural constraints. Besides these technical results, we have strong reasons to believe that our techniques relying on defining an energy function from the transition table of the automaton may be extended to the wider class of threshold automata.
Analysis of Inter-Domain Traffic Correlations: Random Matrix Theory Approach
Venue: arXiv cs.NI 2007
Year: 2007

The traffic behavior of University of Louisville network with the interconnected backbone routers and the number of Virtual Local Area Network (VLAN) subnets is investigated using the Random Matrix Theory (RMT) approach. We employ the system of equal interval time series of traffic counts at all router to router and router to subnet connections as a representation of the inter-VLAN traffic. The cross-correlation matrix C of the traffic rate changes between different traffic time series is calculated and tested against null-hypothesis of random interactions. The majority of the eigenvalues λ_{i} of matrix C fall within the bounds predicted by the RMT for the eigenvalues of random correlation matrices. The distribution of eigenvalues and eigenvectors outside of the RMT bounds displays prominent and systematic deviations from the RMT predictions. Moreover, these deviations are stable in time. The method we use provides a unique possibility to accomplish three concurrent tasks of traffic analysis. The method verifies the uncongested state of the network, by establishing the profile of random interactions. It recognizes the system-specific large-scale interactions, by establishing the profile of stable in time non-random interactions. Finally, by looking into the eigenstatistics we are able to detect and allocate anomalies of network traffic interactions.
Dualheap Sort Algorithm: An Inherently Parallel Generalization of Heapsort
Venue: arXiv cs.DS 2007
Year: 2007

A generalization of the heapsort algorithm is proposed. At the expense of about 50% more comparison and move operations for typical cases, the dualheap sort algorithm offers several advantages over heapsort: improved cache performance, better performance if the input happens to be already sorted, and easier parallel implementations.
Remote laboratories: new technology and standard based architecture
Venue: arXiv cs.OH 2007
Year: 2007

E-Laboratories are important components of e- learning environments, especially in scientific and technical disciplines. First widespread E-Labs consisted in proposing simulations of real systems (virtual labs), as building remote labs (remote control of real systems) was difficult by lack of industrial standards and common protocols. Nowadays, robotics and automation technologies make easier the interfacing of systems with computers. In this frame, many researchers (such as those mentioned in [1]) focus on how to set up such a remote control. But, only a few of them deal with the educational point of view of the problem. This paper outlines our current research and reflection about remote laboratory modelling.
N-Body Simulations on GPUs
Venue: arXiv cs.CE 2007
Year: 2007

Commercial graphics processors (GPUs) have high compute capacity at very low cost, which makes them attractive for general purpose scientific computing. In this paper we show how graphics processors can be used for N-body simulations to obtain improvements in performance over current generation CPUs. We have developed a highly optimized algorithm for performing the O(N^2) force calculations that constitute the major part of stellar and molecular dynamics simulations. In some of the calculations, we achieve sustained performance of nearly 100 GFlops on an ATI X1900XTX. The performance on GPUs is comparable to specialized processors such as GRAPE-6A and MDGRAPE-3, but at a fraction of the cost. Furthermore, the wide availability of GPUs has significant implications for cluster computing and distributed computing efforts like Folding@Home.
Group Testing with Random Pools: optimal two-stage algorithms
Venue: arXiv cs.DS 2007
Year: 2007

We study Probabilistic Group Testing of a set of N items each of which is defective with probability p. We focus on the double limit of small defect probability, p<<1, and large number of variables, N>>1, taking either p->0 after $N\to\infty$ or $p=1/N^β$ with $β\in(0,1/2)$. In both settings the optimal number of tests which are required to identify with certainty the defectives via a two-stage procedure, $\bar T(N,p)$, is known to scale as $Np|\log p|$. Here we determine the sharp asymptotic value of $\bar T(N,p)/(Np|\log p|)$ and construct a class of two-stage algorithms over which this optimal value is attained. This is done by choosing a proper bipartite regular graph (of tests and variable nodes) for the first stage of the detection. Furthermore we prove that this optimal value is also attained on average over a random bipartite graph where all variables have the same degree, while the tests have Poisson-distributed degrees. Finally, we improve the existing upper and lower bound for the optimal number of tests in the case $p=1/N^β$ with $β\in[1/2,1)$.
A solution for actors' viewpoints representation with collaborative product development
Venue: arXiv cs.HC 2007
Year: 2007

As product complexity and marketing competition increase, a collaborative product development is necessary for companies which develop high quality products in short lead-times. To support product actors from different fields, disciplines, and locations, wishing to exchange and share information, the representation of the actors' viewpoints is the underlying requirement of the collaborative product development. The actors' viewpoints approach was designed to provide an organisational framework following the actors' perspectives in the collaboration, and their relationships, could be explicitly gathered and formatted. The approach acknowledges the inevitability of multiple integration of product information as different views, promotes gathering of actors' interests, and encourages retrieved adequate information while providing support for integration through PLM and/or SCM collaboration. In this paper, a solution for neutral viewpoints representation is proposed. The product, process, and organisation information models are seriatim discussed. A series of issues referring to the viewpoints representation are discussed in detail. Based on XML standard, taking cyclone vessel as an example, an application case of part of product information modelling is stated.
A Sequent Calculus for Modelling Interferences
Venue: arXiv cs.LO 2007
Year: 2007

A logic calculus is presented that is a conservative extension of linear logic. The motivation beneath this work concerns lazy evaluation, true concurrency and interferences in proof search. The calculus includes two new connectives to deal with multisequent structures and has the cut-elimination property. Extensions are proposed that give first results concerning our objectives.
Optimal Replica Placement in Tree Networks with QoS and Bandwidth Constraints and the Closest Allocation Policy
Venue: arXiv cs.DC 2007
Year: 2007

This paper deals with the replica placement problem on fully homogeneous tree networks known as the Replica Placement optimization problem. The client requests are known beforehand, while the number and location of the servers are to be determined. We investigate the latter problem using the Closest access policy when adding QoS and bandwidth constraints. We propose an optimal algorithm in two passes using dynamic programming.
Tight Bounds on the Average Length, Entropy, and Redundancy of Anti-Uniform Huffman Codes
Venue: arXiv cs.IT 2007
Year: 2007

In this paper we consider the class of anti-uniform Huffman codes and derive tight lower and upper bounds on the average length, entropy, and redundancy of such codes in terms of the alphabet size of the source. The Fibonacci distributions are introduced which play a fundamental role in AUH codes. It is shown that such distributions maximize the average length and the entropy of the code for a given alphabet size. Another previously known bound on the entropy for given average length follows immediately from our results.
stdchk: A Checkpoint Storage System for Desktop Grid Computing
Venue: arXiv cs.DC 2007
Year: 2007

Checkpointing is an indispensable technique to provide fault tolerance for long-running high-throughput applications like those running on desktop grids. This paper argues that a dedicated checkpoint storage system, optimized to operate in these environments, can offer multiple benefits: reduce the load on a traditional file system, offer high-performance through specialization, and, finally, optimize data management by taking into account checkpoint application semantics. Such a storage system can present a unifying abstraction to checkpoint operations, while hiding the fact that there are no dedicated resources to store the checkpoint data. We prototype stdchk, a checkpoint storage system that uses scavenged disk space from participating desktops to build a low-cost storage system, offering a traditional file system interface for easy integration with applications. This paper presents the stdchk architecture, key performance optimizations, support for incremental checkpointing, and increased data availability. Our evaluation confirms that the stdchk approach is viable in a desktop grid setting and offers a low cost storage system with desirable performance characteristics: high write throughput and reduced storage space and network effort to save checkpoint images.
Java Components Vulnerabilities - An Experimental Classification Targeted at the OSGi Platform
Venue: arXiv cs.CR 2007
Year: 2007

The OSGi Platform finds a growing interest in two different applications domains: embedded systems, and applications servers. However, the security properties of this platform are hardly studied, which is likely to hinder its use in production systems. This is all the more important that the dynamic aspect of OSGi-based applications, that can be extended at runtime, make them vulnerable to malicious code injection. We therefore perform a systematic audit of the OSGi platform so as to build a vulnerability catalog that intends to reference OSGi Vulnerabilities originating in the Core Specification, and in behaviors related to the use of the Java language. Standard Services are not considered. To support this audit, a Semi-formal Vulnerability Pattern is defined, that enables to uniquely characterize fundamental properties for each vulnerability, to include verbose description in the pattern, to reference known security protections, and to track the implementation status of the proof-of-concept OSGi Bundles that exploit the vulnerability. Based on the analysis of the catalog, a robust OSGi Platform is built, and recommendations are made to enhance the OSGi Specifications.
End-to-End Available Bandwidth Measurement Tools : A Comparative Evaluation of Performances
Venue: arXiv cs.NI 2007
Year: 2007

In recent years, there has been a strong interest in measuring the available bandwidth of network paths. Several methods and techniques have been proposed and various measurement tools have been developed and evaluated. However, there have been few comparative studies with regards to the actual performance of these tools. This paper presents a study of available bandwidth measurement techniques and undertakes a comparative analysis in terms of accuracy, intrusiveness and response time of active probing tools. Finally, measurement errors and the uncertainty of the tools are analysed and overall conclusions made.