OpenRaiser/Intern-Atlas huggingface dataset:
Analysis of 802.11b MAC: A QoS, Fairness, and Performance Perspective
Venue: arXiv cs.NI 2004
Year: 2004

Wireless LANs have achieved a tremendous amount of growth in recent years. Among various wireless LAN technologies, the IEEE 802.11b based wireless LAN technology can be cited as the most prominent technology today. Despite being widely deployed, 802.11b cannot be termed as a well matured technology. Although 802.11b is adequate for basic connectivity and packet switching, It is evident that there is ample scope for its improvement in areas like quality of service, fairness, performance, security, etc. In this survey report, we identify and argue that the Medium Access Controller for 802.11b networks is the prime area for these improvements. To enunciate our claims we highlight some of the quality of service, fairness, and performance issues related to 802.11b MAC. We also describe and analyze some of the current research aimed at addressing these issues. We then propose a novel scheme called the Intelligent Collision Avoidance, seeking to enhance the MAC to address some of the performance issues in 802.11b and similar networks.
Topological Navigation of Simulated Robots using Occupancy Grid
Venue: arXiv cs.RO 2004
Year: 2004

Formerly I presented a metric navigation method in the Webots mobile robot simulator. The navigating Khepera-like robot builds an occupancy grid of the environment and explores the square-shaped room around with a value iteration algorithm. Now I created a topological navigation procedure based on the occupancy grid process. The extension by a skeletonization algorithm results a graph of important places and the connecting routes among them. I also show the significant time profit gained during the process.
Security of public key cryptosystems based on Chebyshev Polynomials
Venue: arXiv cs.CR 2004
Year: 2004

Chebyshev polynomials have been recently proposed for designing public-key systems. Indeed, they enjoy some nice chaotic properties, which seem to be suitable for use in Cryptography. Moreover, they satisfy a semi-group property, which makes possible implementing a trapdoor mechanism. In this paper we study a public key cryptosystem based on such polynomials, which provides both encryption and digital signature. The cryptosystem works on real numbers and is quite efficient. Unfortunately, from our analysis it comes up that it is not secure. We describe an attack which permits to recover the corresponding plaintext from a given ciphertext. The same attack can be applied to produce forgeries if the cryptosystem is used for signing messages. Then, we point out that also other primitives, a Diffie-Hellman like key agreement scheme and an authentication scheme, designed along the same lines of the cryptosystem, are not secure due to the aforementioned attack. We close the paper by discussing the issues and the possibilities of constructing public key cryptosystems on real numbers.
Logic Column 10: Specifying Confidentiality
Venue: arXiv cs.LO 2004
Year: 2004

This article illustrates the use of a logical specification language to capture various forms of confidentiality properties used in the security literature.
Impact of IT on Higher education Through Continuing Education
Venue: arXiv cs.CY 2004
Year: 2004

Information Technology is emerging to be the technology of 21st century. The paradigm shift from industrial society to information society had already become a reality! It is indeed high time to think about integrating IT in all facets of education -- may it be in secondary level, or be it in reskilling the employed ones. This paper discusses various issues in incorporating IT in various levels of education, and the need to think about a task force to counter the so-called slow down and recession in IT industry. The opportunities for aspiring IT professionals were also discussed. The importance of reskilling as a continuing education programme to make the people aware of the changing trends in IT was also discussed.
Using LDAP Directories for Management of PKI Processes
Venue: arXiv cs.CR 2004
Year: 2004

We present a framework for extending the functionality of LDAP servers from their typical use as a public directory in public key infrastructures. In this framework the LDAP servers are used for administrating infrastructure processes. One application of this framework is a method for providing proof-of-possession, especially in the case of encryption keys. Another one is the secure delivery of software personal security environments.
Transparent Format Migration of Preserved Web Content
Venue: arXiv cs.DL 2004
Year: 2004

The LOCKSS digital preservation system collects content by crawling the web and preserves it in the format supplied by the publisher. Eventually, browsers will no longer understand that format. A process called format migration converts it to a newer format that the browsers do understand. The LOCKSS program has designed and tested an initial implementation of format migration for Web content that is transparent to readers, building on the content negotiation capabilities of HTTP.
Notes On The Design Of An Internet Adversary
Venue: arXiv cs.DL 2004
Year: 2004

The design of the defenses Internet systems can deploy against attack, especially adaptive and resilient defenses, must start from a realistic model of the threat. This requires an assessment of the capabilities of the adversary. The design typically evolves through a process of simulating both the system and the adversary. This requires the design and implementation of a simulated adversary based on the capability assessment. Consensus on the capabilities of a suitable adversary is not evident. Part of the recent redesign of the protocol used by peers in the LOCKSS digital preservation system included a conservative assessment of the adversary's capabilities. We present our assessment and the implications we drew from it as a step towards a reusable adversary specification.
Deploiement d'ordonnanceurs de processus specifiques dans un systeme d'exploitation generaliste
Venue: arXiv cs.NI 2004
Year: 2004

Bossa is a framework to develop new processes schedulers in commodity operating systems. Although Bossa enables fine-grained management of the processor through new scheduling policies, deploying an application with its own scheduler raises some problems. In this paper we study the problems caused when deploying an application and its scheduler and to adresse these, we propose to establish Quality of Service contracts and mechanisms to reconfigure the scheduler hierarchy.
A Software Architecture for Automatic Deployment of CORBA Components Using Grid Technologies
Venue: arXiv cs.NI 2004
Year: 2004

Software components turn out to be a convenient model to build complex applications for scientific computing and to run them on a computational grid. However, deploying complex, component-based applications in a grid environment is particularly arduous. To prevent the user from directly dealing with a large number of execution hosts and their heterogeneity within a grid, the application deployment phase must be as automatic as possible. This paper describes an architecture for automatic deployment of component-based applications on computational grids. In the context of the CORBA Component Model (CCM), this paper details all the steps to achieve an automatic deployment of components as well as the entities involved: a grid access middleware and its grid information service (like OGSI), a component deployment model, as specified by CCM, an enriched application description and a deployment planner in order to select resources and map components onto computers.
Forbidden Subgraphs in Connected Graphs
Venue: arXiv cs.DS 2004
Year: 2004

Given a set $ξ=\{H_1,H_2,...\}$ of connected non acyclic graphs, a $ξ$-free graph is one which does not contain any member of $% ξ$ as copy. Define the excess of a graph as the difference between its number of edges and its number of vertices. Let ${\gr{W}}_{k,ξ}$ be theexponential generating function (EGF for brief) of connected $ξ$-free graphs of excess equal to $k$ ($k \geq 1$). For each fixed $ξ$, a fundamental differential recurrence satisfied by the EGFs ${\gr{W}}_{k,ξ}$ is derived. We give methods on how to solve this nonlinear recurrence for the first few values of $k$ by means of graph surgery. We also show that for any finite collection $ξ$ of non-acyclic graphs, the EGFs ${\gr{W}}_{k,ξ}$ are always rational functions of the generating function, $T$, of Cayley's rooted (non-planar) labelled trees. From this, we prove that almost all connected graphs with $n$ nodes and $n+k$ edges are $ξ$-free, whenever $k=o(n^{1/3})$ and $|ξ| < \infty$ by means of Wright's inequalities and saddle point method. Limiting distributions are derived for sparse connected $ξ$-free components that are present when a random graph on $n$ nodes has approximately $\frac{n}{2}$ edges. In particular, the probability distribution that it consists of trees, unicyclic components, $...$, $(q+1)$-cyclic components all $ξ$-free is derived. Similar results are also obtained for multigraphs, which are graphs where self-loops and multiple-edges are allowed.
Inter-Package Dependency Networks in Open-Source Software
Venue: arXiv cs.SE 2004
Year: 2004

This research analyzes complex networks in open-source software at the inter-package level, where package dependencies often span across projects and between development groups. We review complex networks identified at ``lower'' levels of abstraction, and then formulate a description of interacting software components at the package level, a relatively ``high'' level of abstraction. By mining open-source software repositories from two sources, we empirically show that the coupling of modules at this granularity creates a small-world and scale-free network in both instances.
A Note on the PAC Bayesian Theorem
Venue: arXiv cs.LG 2004
Year: 2004

We prove general exponential moment inequalities for averages of [0,1]-valued iid random variables and use them to tighten the PAC Bayesian Theorem. The logarithmic dependence on the sample count in the enumerator of the PAC Bayesian bound is halved.
Ranking Pages by Topology and Popularity within Web Sites
Venue: arXiv cs.AI 2004
Year: 2004

We compare two link analysis ranking methods of web pages in a site. The first, called Site Rank, is an adaptation of PageRank to the granularity of a web site and the second, called Popularity Rank, is based on the frequencies of user clicks on the outlinks in a page that are captured by navigation sessions of users through the web site. We ran experiments on artificially created web sites of different sizes and on two real data sets, employing the relative entropy to compare the distributions of the two ranking methods. For the real data sets we also employ a nonparametric measure, called Spearman's footrule, which we use to compare the top-ten web pages ranked by the two methods. Our main result is that the distributions of the Popularity Rank and Site Rank are surprisingly close to each other, implying that the topology of a web site is very instrumental in guiding users through the site. Thus, in practice, the Site Rank provides a reasonable first order approximation of the aggregate behaviour of users within a web site given by the Popularity Rank.
The Accelerated Euclidean Algorithm
Venue: arXiv cs.DS 2004
Year: 2004

We present a new GCD algorithm of two integers or polynomials. The algorithm is iterative and its time complexity is still $O(n \\log^2 n ~ log \\log n)$ for $n$-bit inputs.
Exploring networks with traceroute-like probes: theory and simulations
Venue: arXiv cs.NI 2004
Year: 2004

Mapping the Internet generally consists in sampling the network from a limited set of sources by using traceroute-like probes. This methodology, akin to the merging of different spanning trees to a set of destination, has been argued to introduce uncontrolled sampling biases that might produce statistical properties of the sampled graph which sharply differ from the original ones. In this paper we explore these biases and provide a statistical analysis of their origin. We derive an analytical approximation for the probability of edge and vertex detection that exploits the role of the number of sources and targets and allows us to relate the global topological properties of the underlying network with the statistical accuracy of the sampled graph. In particular, we find that the edge and vertex detection probability depends on the betweenness centrality of each element. This allows us to show that shortest path routed sampling provides a better characterization of underlying graphs with broad distributions of connectivity. We complement the analytical discussion with a throughout numerical investigation of simulated mapping strategies in network models with different topologies. We show that sampled graphs provide a fair qualitative characterization of the statistical properties of the original networks in a fair range of different strategies and exploration parameters. Moreover, we characterize the level of redundancy and completeness of the exploration process as a function of the topological properties of the network. Finally, we study numerically how the fraction of vertices and edges discovered in the sampled graph depends on the particular deployements of probing sources. The results might hint the steps toward more efficient mapping strategies.
Removing Propagation Redundant Constraints in Redundant Modeling
Venue: arXiv cs.LO 2004
Year: 2004

A widely adopted approach to solving constraint satisfaction problems combines systematic tree search with various degrees of constraint propagation for pruning the search space. One common technique to improve the execution efficiency is to add redundant constraints, which are constraints logically implied by others in the problem model. However, some redundant constraints are propagation redundant and hence do not contribute additional propagation information to the constraint solver. Redundant constraints arise naturally in the process of redundant modeling where two models of the same problem are connected and combined through channeling constraints. In this paper, we give general theorems for proving propagation redundancy of one constraint with respect to channeling constraints and constraints in the other model. We illustrate, on problems from CSPlib (http://www.csplib.org/), how detecting and removing propagation redundant constraints in redundant modeling can significantly speed up constraint solving.
The modelling of the build constructions in a CAD of the renovation of the enterprises by means of units in the drawings
Venue: arXiv cs.CE 2004
Year: 2004

The parametric model of build constructions and features of design operations are described for making drawings, which are the common component of the different parts of the projects of renovation of enterprises. The key moment of the deep design automation is the using of so-called units in the drawings, which are joining a visible graphic part and invisible parameters. The model has passed check during designing of several hundreds of drawings
Data-stationary Architecture to Execute Quantum Algorithms Classically
Venue: arXiv cs.AR 2004
Year: 2004

This paper presents a data stationary architecture in which each word has an attached address field. Address fields massively update in parallel to record data interchanges. Words do not move until memory is read for post processing. A sea of such cells can test large-scale quantum algorithms, although other programming is possible.
Validating a Web Service Security Abstraction by Typing
Venue: arXiv cs.CR 2004
Year: 2004

An XML web service is, to a first approximation, an RPC service in which requests and responses are encoded in XML as SOAP envelopes, and transported over HTTP. We consider the problem of authenticating requests and responses at the SOAP-level, rather than relying on transport-level security. We propose a security abstraction, inspired by earlier work on secure RPC, in which the methods exported by a web service are annotated with one of three security levels: none, authenticated, or both authenticated and encrypted. We model our abstraction as an object calculus with primitives for defining and calling web services. We describe the semantics of our object calculus by translating to a lower-level language with primitives for message passing and cryptography. To validate our semantics, we embed correspondence assertions that specify the correct authentication of requests and responses. By appeal to the type theory for cryptographic protocols of Gordon and Jeffrey's Cryptyc, we verify the correspondence assertions simply by typing. Finally, we describe an implementation of our semantics via custom SOAP headers.
Quasiconvex Programming
Venue: arXiv cs.CG 2004
Year: 2004

We define quasiconvex programming, a form of generalized linear programming in which one seeks the point minimizing the pointwise maximum of a collection of quasiconvex functions. We survey algorithms for solving quasiconvex programs either numerically or via generalizations of the dual simplex method from linear programming, and describe varied applications of this geometric optimization technique in meshing, scientific computation, information visualization, automated algorithm analysis, and robust statistics.
From Feature Extraction to Classification: A multidisciplinary Approach applied to Portuguese Granites
Venue: arXiv cs.AI 2004
Year: 2004

The purpose of this paper is to present a complete methodology based on a multidisciplinary approach, that goes from the extraction of features till the classification of a set of different portuguese granites. The set of tools to extract the features that characterise polished surfaces of the granites is mainly based on mathematical morphology. The classification methodology is based on a genetic algorithm capable of search the input feature space used by the nearest neighbour rule classifier. Results show that is adequate to perform feature reduction and simultaneous improve the recognition rate. Moreover, the present methodology represents a robust strategy to understand the proper nature of the images treated, and their discriminant features. KEYWORDS: Portuguese grey granites, feature extraction, mathematical morphology, feature reduction, genetic algorithms, nearest neighbour rule classifiers (k-NNR).
Complete Characterization of the Equivalent MIMO Channel for Quasi-Orthogonal Space-Time Codes
Venue: arXiv cs.IT 2004
Year: 2004

Recently, a quasi-orthogonal space-time block code (QSTBC) capable of achieving a significant fraction of the outage mutual information of a multiple-input-multiple output (MIMO) wireless communication system for the case of four transmit and one receive antennas was proposed. We generalize these results to $n_T=2^n$ transmit and an arbitrary number of receive antennas $n_R$. Furthermore, we completely characterize the structure of the equivalent channel for the general case and show that for all $n_T=2^n$ and $n_R$ the eigenvectors of the equivalent channel are fixed and independent from the channel realization. Furthermore, the eigenvalues of the equivalent channel are independent identically distributed random variables each following a noncentral chi-square distribution with $4n_R$ degrees of freedom. Based on these important insights into the structure of the QSTBC, we derive an analytical lower bound for the fraction of outage probability achieved with QSTBC and show that this bound is tight for low signal-to-noise-ratios (SNR) values and also for increasing number of receive antennas. We also present an upper bound, which is tight for high SNR values and derive analytical expressions for the case of four transmit antennas. Finally, by utilizing the special structure of the QSTBC we propose a new transmit strategy, which decouples the signals transmitted from different antennas in order to detect the symbols separately with a linear ML-detector rather than joint detection, an up to now only known advantage of orthogonal space-time block codes (OSTBC).
Less is More - Genetic Optimisation of Nearest Neighbour Classifiers
Venue: arXiv cs.AI 2004
Year: 2004

The present paper deals with optimisation of Nearest Neighbour rule Classifiers via Genetic Algorithms. The methodology consists on implement a Genetic Algorithm capable of search the input feature space used by the NNR classifier. Results show that is adequate to perform feature reduction and simultaneous improve the Recognition Rate. Some practical examples prove that is possible to Recognise Portuguese Granites in 100%, with only 3 morphological features (from an original set of 117 features), which is well suited for real time applications. Moreover, the present method represents a robust strategy to understand the proper nature of the images treated, and their discriminant features. KEYWORDS: Feature Reduction, Genetic Algorithms, Nearest Neighbour Rule Classifiers (k-NNR).
The Biological Concept of Neoteny in Evolutionary Colour Image Segmentation - Simple Experiments in Simple Non-Memetic Genetic Algorithms
Venue: arXiv cs.AI 2004
Year: 2004

Neoteny, also spelled Paedomorphosis, can be defined in biological terms as the retention by an organism of juvenile or even larval traits into later life. In some species, all morphological development is retarded; the organism is juvenilized but sexually mature. Such shifts of reproductive capability would appear to have adaptive significance to organisms that exhibit it. In terms of evolutionary theory, the process of paedomorphosis suggests that larval stages and developmental phases of existing organisms may give rise, under certain circumstances, to wholly new organisms. Although the present work does not pretend to model or simulate the biological details of such a concept in any way, these ideas were incorporated by a rather simple abstract computational strategy, in order to allow (if possible) for faster convergence into simple non-memetic Genetic Algorithms, i.e. without using local improvement procedures (e.g. via Baldwin or Lamarckian learning). As a case-study, the Genetic Algorithm was used for colour image segmentation purposes by using K-mean unsupervised clustering methods, namely for guiding the evolutionary algorithm in his search for finding the optimal or sub-optimal data partition. Average results suggest that the use of neotonic strategies by employing juvenile genotypes into the later generations and the use of linear-dynamic mutation rates instead of constant, can increase fitness values by 58% comparing to classical Genetic Algorithms, independently from the starting population characteristics on the search space. KEYWORDS: Genetic Algorithms, Artificial Neoteny, Dynamic Mutation Rates, Faster Convergence, Colour Image Segmentation, Classification, Clustering.