title: INSPIRE: Evaluation of a Smart-Home System for Infotainment Management and Device Control

abstract: This paper gives an overview of the assessment and evaluation methods which have been used to determine the quality of the INSPIRE smart home system. The system allows different home appliances to be controlled via speech, and consists of speech and speaker recognition, speech understanding, dialogue management, and speech output components. The performance of these components is first assessed individually, and then the entire system is evaluated in an interaction experiment with test users. Initial results of the assessment and evaluation are given, in particular with respect to the transmission channel impact on speech and speaker recognition, and the assessment of speech output for different system metaphors.


title: Intelligent Computer Numerical Control unit for machine tools

abstract: The paper describes a new CNC control unit for machining centres with learning ability and automatic intelligent generating of NC programs on the bases of a neural network, which is built-in into a CNC unit as special device. The device performs intelligent and completely automatically the NC part programs only on the bases of 2D, 2,5D or 3D computer model of prismatic part. Intervention of the operator is not needed. The neural network for milling, drilling, reaming, threading and operations alike has learned to generate NC programs in the learning module, which is a part of intelligent CAD/CAM system.


title: A Categorical View on Algebraic Lattices in Formal Concept Analysis

abstract: Formal concept analysis has grown from a new branch of the mathematical field of lattice theory to a widely recognized tool in Computer Science and elsewhere. In order to fully benefit from this theory, we believe that it can be enriched with notions such as approximation by computation or representability. The latter are commonly studied in denotational semantics and domain theory and captured most prominently by the notion of algebraicity, e.g. of lattices. In this paper, we explore the notion of algebraicity in formal concept analysis from a category-theoretical perspective. To this end, we build on the the notion of approximable concept with a suitable category and show that the latter is equivalent to the category of algebraic lattices. At the same time, the paper provides a relatively comprehensive account of the representation theory of algebraic lattices in the framework of Stone duality, relating well-known structures such as Scott information systems with further formalisms from logic, topology, domains and lattice theory.


title: Fast Query Processing by Distributing an Index over CPU Caches

abstract: Data intensive applications on clusters often require requests quickly be sent to the node managing the desired data. In many applications, one must look through a sorted tree structure to determine the responsible node for accessing or storing the data. Examples include object tracking in sensor networks, packet routing over the internet, request processing in publish-subscribe middleware, and query processing in database systems. When the tree structure is larger than the CPU cache, the standard implementation potentially incurs many cache misses for each lookup; one cache miss at each successive level of the tree. As the CPU-RAM gap grows, this performance degradation will only become worse in the future. We propose a solution that takes advantage of the growing speed of local area networks for clusters. We split the sorted tree structure among the nodes of the cluster. We assume that the structure will fit inside the aggregation of the CPU caches of the entire cluster. We then send a word over the network (as part of a larger packet containing other words) in order to examine the tree structure in another node's CPU cache. We show that this is often faster than the standard solution, which locally incurs multiple cache misses while accessing each successive level of the tree.


title: Computational Unification: a Vision for Connecting Researchers

abstract: The extent to which the benefits of science can be fully realized depends critically upon the quality of the connection between researchers themselves and between researchers and members of the public. We believe that it is now possible to improve these connections on a community-wide and even world-wide basis through the use of an appropriate information management system. In this paper we explore the concepts and challenges, and propose an architecture for the implementation of such a system. "One of the greatest visions for science is a computational unification in which every researcher can interact with all other researchers through use of their own research system." "These features not only enable research collaboration on a scale never previously envisaged, they also enable sharing and dissemination of scientific knowledge to the public at large with a sophistication unparalleled in history."


title: Analyzing and Improving Performance of a Class of Anomaly-based Intrusion Detectors

abstract: Anomaly-based intrusion detection (AID) techniques are useful for detecting novel intrusions into computing resources. One of the most successful AID detectors proposed to date is stide, which is based on analysis of system call sequences. In this paper, we present a detailed formal framework to analyze, understand and improve the performance of stide and similar AID techniques. Several important properties of stide-like detectors are established through formal proofs, and validated by carefully conducted experiments using test datasets. Finally, the framework is utilized to design two applications to improve the cost and performance of stide-like detectors which are based on sequence analysis. The first application reduces the cost of developing AID detectors by identifying the critical sections in the training dataset, and the second application identifies the intrusion context in the intrusive dataset, that helps to fine-tune the detectors. Such fine-tuning in turn helps to improve detection rate and reduce false alarm rate, thereby increasing the effectiveness and efficiency of the intrusion detectors.


title: Selfish peering and routing in the Internet

abstract: The Internet is a loose amalgamation of independent service providers acting in their own self-interest. We examine the implications of this economic reality on peering relationships. Specifically, we consider how the incentives of the providers might determine where they choose to interconnect with each other. We consider a game where two selfish network providers must establish peering points between their respective network graphs, given knowledge of traffic conditions and a nearest-exit routing policy for out-going traffic, as well as costs based on congestion and peering connectivity. We focus on the pairwise stability equilibrium concept and use a stochastic procedure to solve for the stochastically pairwise stable configurations. Stochastically stable networks are selected for their robustness to deviations in strategy and are therefore posited as the more likely networks to emerge in a dynamic setting. We note a paucity of stochastically stable peering configurations under asymmetric conditions, particularly to unequal interdomain traffic flow, with adverse effects on system-wide efficiency. Under bilateral flow conditions, we find that as the cost associated with the establishment of peering links approaches zero, the variance in the number of peering links of stochastically pairwise stable equilibria increases dramatically.


title: Using image partitions in 4th Dimension

abstract: I have plotted an image by using mathematical functions in the Database "4th Dimension". I'm going to show an alternative method to: detect which sector has been clicked; highlight it and combine it with other sectors already highlighted; store the graph information in an efficient way; load and splat image layers to reconstruct the stored graph.


title: The Cyborg Astrobiologist: First Field Experience

abstract: We present results from the first geological field tests of the `Cyborg Astrobiologist', which is a wearable computer and video camcorder system that we are using to test and train a computer-vision system towards having some of the autonomous decision-making capabilities of a field-geologist and field-astrobiologist. The Cyborg Astrobiologist platform has thus far been used for testing and development of these algorithms and systems: robotic acquisition of quasi-mosaics of images, real-time image segmentation, and real-time determination of interesting points in the image mosaics. The hardware and software systems function reliably, and the computer-vision algorithms are adequate for the first field tests. In addition to the proof-of-concept aspect of these field tests, the main result of these field tests is the enumeration of those issues that we can improve in the future, including: first, detection and accounting for shadows caused by 3D jagged edges in the outcrop; second, reincorporation of more sophisticated texture-analysis algorithms into the system; third, creation of hardware and software capabilities to control the camera's zoom lens in an intelligent manner; and fourth, development of algorithms for interpretation of complex geological scenery. Nonetheless, despite these technical inadequacies, this Cyborg Astrobiologist system, consisting of a camera-equipped wearable-computer and its computer-vision algorithms, has demonstrated its ability of finding genuinely interesting points in real-time in the geological scenery, and then gathering more information about these interest points in an automated manner.

categories: cs.CV astro-ph cs.AI cs.CE cs.HC cs.RO cs.SE q-bio.NC


title: Temporal logic with predicate abstraction

abstract: A predicate linear temporal logic LTL_{\lambda,=} without quantifiers but with predicate abstraction mechanism and equality is considered. The models of LTL_{\lambda,=} can be naturally seen as the systems of pebbles (flexible constants) moving over the elements of some (possibly infinite) domain. This allows to use LTL_{\lambda,=} for the specification of dynamic systems using some resources, such as processes using memory locations, mobile agents occupying some sites, etc. On the other hand we show that LTL_{\lambda,=} is not recursively axiomatizable and, therefore, fully automated verification of LTL_{\lambda,=} specifications is not, in general, possible.


title: On Spatial Conjunction as Second-Order Logic

abstract: Spatial conjunction is a powerful construct for reasoning about dynamically allocated data structures, as well as concurrent, distributed and mobile computation. While researchers have identified many uses of spatial conjunction, its precise expressive power compared to traditional logical constructs was not previously known. In this paper we establish the expressive power of spatial conjunction. We construct an embedding from first-order logic with spatial conjunction into second-order logic, and more surprisingly, an embedding from full second order logic into first-order logic with spatial conjunction. These embeddings show that the satisfiability of formulas in first-order logic with spatial conjunction is equivalent to the satisfiability of formulas in second-order logic. These results explain the great expressive power of spatial conjunction and can be used to show that adding unrestricted spatial conjunction to a decidable logic leads to an undecidable logic. As one example, we show that adding unrestricted spatial conjunction to two-variable logic leads to undecidability. On the side of decidability, the embedding into second-order logic immediately implies the decidability of first-order logic with a form of spatial conjunction over trees. The embedding into spatial conjunction also has useful consequences: because a restricted form of spatial conjunction in two-variable logic preserves decidability, we obtain that a correspondingly restricted form of second-order quantification in two-variable logic is decidable. The resulting language generalizes the first-order theory of boolean algebra over sets and is useful in reasoning about the contents of data structures in object-oriented languages.


title: ReCord: A Distributed Hash Table with Recursive Structure

abstract: We propose a simple distributed hash table called ReCord, which is a generalized version of Randomized-Chord and offers improved tradeoffs in performance and topology maintenance over existing P2P systems. ReCord is scalable and can be easily implemented as an overlay network, and offers a good tradeoff between the node degree and query latency. For instance, an $n$-node ReCord with $O(\log n)$ node degree has an expected latency of $\Theta(\log n)$ hops. Alternatively, it can also offer $\Theta(\frac{\log n}{\log \log n})$ hops latency at a higher cost of $O(\frac{\log^2 n}{\log \log n})$ node degree. Meanwhile, simulations of the dynamic behaviors of ReCord are studied.


title: Some first thoughts on the stability of the asynchronous systems

abstract: The (non-initialized, non-deterministic) asynchronous systems (in the input-output sense) are multi-valued functions from m-dimensional signals to sets of n-dimensional signals, the concept being inspired by the modeling of the asynchronous circuits. Our purpose is to state the problem of the their stability.


title: Synchronization from a Categorical Perspective

abstract: We introduce a notion of synchronization for higher-dimensional automata, based on coskeletons of cubical sets. Categorification transports this notion to the setting of categorical transition systems. We apply the results to study the semantics of an imperative programming language with message-passing.


title: Fibonacci-Like Polynomials Produced by m-ary Huffman Codes for Absolutely Ordered Sequences

abstract: Fibonacci-like polynomials produced by m-ary Huffman codes for absolutely ordered sequences have been described.


title: Applications of LDPC Codes to the Wiretap Channel

abstract: With the advent of quantum key distribution (QKD) systems, perfect (i.e. information-theoretic) security can now be achieved for distribution of a cryptographic key. QKD systems and similar protocols use classical error-correcting codes for both error correction (for the honest parties to correct errors) and privacy amplification (to make an eavesdropper fully ignorant). From a coding perspective, a good model that corresponds to such a setting is the wire tap channel introduced by Wyner in 1975. In this paper, we study fundamental limits and coding methods for wire tap channels. We provide an alternative view of the proof for secrecy capacity of wire tap channels and show how capacity achieving codes can be used to achieve the secrecy capacity for any wiretap channel. We also consider binary erasure channel and binary symmetric channel special cases for the wiretap channel and propose specific practical codes. In some cases our designs achieve the secrecy capacity and in others the codes provide security at rates below secrecy capacity. For the special case of a noiseless main channel and binary erasure channel, we consider encoder and decoder design for codes achieving secrecy on the wiretap channel; we show that it is possible to construct linear-time decodable secrecy codes based on LDPC codes that achieve secrecy.


title: Computational Aspects of a Numerical Model for Combustion Flow

abstract: A computational method for numeric resolution of a PDEs system, based on a Finite Differences schema integrated by interpolations of partial results, and an estimate of the error of its solution respect to the normal FD solution.


title: A Directed Threshold - Signature Scheme

abstract: Directed signature is the solution of such problems when the signed message contains information sensitive to the signature receiver. Generally, in many application of directed signature, the signer is generally a single person. But when the message is on behalf of an organization, a valid sensitive message may require the approval of several people. Threshold signature schemes are used to solve these problems. This paper presents a threshold directed signature scheme.


title: Capacity Achieving Code Constructions for Two Classes of (d,k) Constraints

abstract: In this paper, we present two low complexity algorithms that achieve capacity for the noiseless (d,k) constrained channel when k=2d+1, or when k-d+1 is not prime. The first algorithm, called symbol sliding, is a generalized version of the bit flipping algorithm introduced by Aviran et al. [1]. In addition to achieving capacity for (d,2d+1) constraints, it comes close to capacity in other cases. The second algorithm is based on interleaving, and is a generalized version of the bit stuffing algorithm introduced by Bender and Wolf [2]. This method uses fewer than k-d biased bit streams to achieve capacity for (d,k) constraints with k-d+1 not prime. In particular, the encoder for (d,d+2^m-1) constraints, 1\le m<\infty, requires only m biased bit streams.


title: Basic properties for sand automata

abstract: We prove several results about the relations between injectivity and surjectivity for sand automata. Moreover, we begin the exploration of the dynamical behavior of sand automata proving that the property of nilpotency is undecidable. We believe that the proof technique used for this last result might reveal useful for many other results in this context.


title: Intuitionistic computability logic

abstract: Computability logic (CL) is a systematic formal theory of computational tasks and resources, which, in a sense, can be seen as a semantics-based alternative to (the syntactically introduced) linear logic. With its expressive and flexible language, where formulas represent computational problems and "truth" is understood as algorithmic solvability, CL potentially offers a comprehensive logical basis for constructive applied theories and computing systems inherently requiring constructive and computationally meaningful underlying logics. Among the best known constructivistic logics is Heyting's intuitionistic calculus INT, whose language can be seen as a special fragment of that of CL. The constructivistic philosophy of INT, however, has never really found an intuitively convincing and mathematically strict semantical justification. CL has good claims to provide such a justification and hence a materialization of Kolmogorov's known thesis "INT = logic of problems". The present paper contains a soundness proof for INT with respect to the CL semantics. A comprehensive online source on CL is available at http://www.cis.upenn.edu/~giorgi/cl.html


title: The equations of the ideal latches

abstract: The latches are simple circuits with feedback from the digital electrical engineering. We have included in our work the C element of Muller, the RS latch, the clocked RS latch, the D latch and also circuits containing two interconnected latches: the edge triggered RS flip-flop, the D flip-flop, the JK flip-flop, the T flip-flop. The purpose of this study is to model with equations the previous circuits, considered to be ideal, i.e. non-inertial. The technique of analysis is the pseudoboolean differential calculus.


title: A Trace Logic for Local Security Properties

abstract: We propose a new simple \emph{trace} logic that can be used to specify \emph{local security properties}, i.e. security properties that refer to a single participant of the protocol specification. Our technique allows a protocol designer to provide a formal specification of the desired security properties, and integrate it naturally into the design process of cryptographic protocols. Furthermore, the logic can be used for formal verification. We illustrate the utility of our technique by exposing new attacks on the well studied protocol TMN.


title: Capacity Analysis for Continuous Alphabet Channels with Side Information, Part I: A General Framework

abstract: Capacity analysis for channels with side information at the receiver has been an active area of interest. This problem is well investigated for the case of finite alphabet channels. However, the results are not easily generalizable to the case of continuous alphabet channels due to analytic difficulties inherent with continuous alphabets. In the first part of this two-part paper, we address an analytical framework for capacity analysis of continuous alphabet channels with side information at the receiver. For this purpose, we establish novel necessary and sufficient conditions for weak* continuity and strict concavity of the mutual information. These conditions are used in investigating the existence and uniqueness of the capacity-achieving measures. Furthermore, we derive necessary and sufficient conditions that characterize the capacity value and the capacity-achieving measure for continuous alphabet channels with side information at the receiver.


title: Capacity Analysis for Continuous Alphabet Channels with Side Information, Part II: MIMO Channels

abstract: In this part, we consider the capacity analysis for wireless mobile systems with multiple antenna architectures. We apply the results of the first part to a commonly known baseband, discrete-time multiple antenna system where both the transmitter and receiver know the channel's statistical law. We analyze the capacity for additive white Gaussian noise (AWGN) channels, fading channels with full channel state information (CSI) at the receiver, fading channels with no CSI, and fading channels with partial CSI at the receiver. For each type of channels, we study the capacity value as well as issues such as the existence, uniqueness, and characterization of the capacity-achieving measures for different types of moment constraints. The results are applicable to both Rayleigh and Rician fading channels in the presence of arbitrary line-of-sight and correlation profiles.


title: Efficient Algorithms for Large-Scale Topology Discovery

abstract: There is a growing interest in discovery of internet topology at the interface level. A new generation of highly distributed measurement systems is currently being deployed. Unfortunately, the research community has not examined the problem of how to perform such measurements efficiently and in a network-friendly manner. In this paper we make two contributions toward that end. First, we show that standard topology discovery methods (e.g., skitter) are quite inefficient, repeatedly probing the same interfaces. This is a concern, because when scaled up, such methods will generate so much traffic that they will begin to resemble DDoS attacks. We measure two kinds of redundancy in probing (intra- and inter-monitor) and show that both kinds are important. We show that straightforward approaches to addressing these two kinds of redundancy must take opposite tacks, and are thus fundamentally in conflict. Our second contribution is to propose and evaluate Doubletree, an algorithm that reduces both types of redundancy simultaneously on routers and end systems. The key ideas are to exploit the tree-like structure of routes to and from a single point in order to guide when to stop probing, and to probe each path by starting near its midpoint. Our results show that Doubletree can reduce both types of measurement load on the network dramatically, while permitting discovery of nearly the same set of nodes and links. We then show how to enable efficient communication between monitors through the use of Bloom filters.


title: Rate Distortion and Denoising of Individual Data Using Kolmogorov complexity

abstract: We examine the structure of families of distortion balls from the perspective of Kolmogorov complexity. Special attention is paid to the canonical rate-distortion function of a source word which returns the minimal Kolmogorov complexity of all distortion balls containing that word subject to a bound on their cardinality. This canonical rate-distortion function is related to the more standard algorithmic rate-distortion function for the given distortion measure. Examples are given of list distortion, Hamming distortion, and Euclidean distortion. The algorithmic rate-distortion function can behave differently from Shannon's rate-distortion function. To this end, we show that the canonical rate-distortion function can and does assume a wide class of shapes (unlike Shannon's); we relate low algorithmic mutual information to low Kolmogorov complexity (and consequently suggest that certain aspects of the mutual information formulation of Shannon's rate-distortion function behave differently than would an analogous formulation using algorithmic mutual information); we explore the notion that low Kolmogorov complexity distortion balls containing a given word capture the interesting properties of that word (which is hard to formalize in Shannon's theory) and this suggests an approach to denoising; and, finally, we show that the different behavior of the rate-distortion curves of individual source words to some extent disappears after averaging over the source words.


title: Bounded Input Bounded Predefined Control Bounded Output

abstract: The paper is an attempt to generalize a methodology, which is similar to the bounded-input bounded-output method currently widely used for the system stability studies. The presented earlier methodology allows decomposition of input space into bounded subspaces and defining for each subspace its bounding surface. It also defines a corresponding predefined control, which maps any point of a bounded input into a desired bounded output subspace. This methodology was improved by providing a mechanism for the fast defining a bounded surface. This paper presents enhanced bounded-input bounded-predefined-control bounded-output approach, which provides adaptability feature to the control and allows transferring of a controlled system along a suboptimal trajectory.


title: Intelligent search strategies based on adaptive Constraint Handling Rules

abstract: The most advanced implementation of adaptive constraint processing with Constraint Handling Rules (CHR) allows the application of intelligent search strategies to solve Constraint Satisfaction Problems (CSP). This presentation compares an improved version of conflict-directed backjumping and two variants of dynamic backtracking with respect to chronological backtracking on some of the AIM instances which are a benchmark set of random 3-SAT problems. A CHR implementation of a Boolean constraint solver combined with these different search strategies in Java is thus being compared with a CHR implementation of the same Boolean constraint solver combined with chronological backtracking in SICStus Prolog. This comparison shows that the addition of ``intelligence'' to the search process may reduce the number of search steps dramatically. Furthermore, the runtime of their Java implementations is in most cases faster than the implementations of chronological backtracking. More specifically, conflict-directed backjumping is even faster than the SICStus Prolog implementation of chronological backtracking, although our Java implementation of CHR lacks the optimisations made in the SICStus Prolog system. To appear in Theory and Practice of Logic Programming (TPLP).


title: Analysis of 802.11b MAC: A QoS, Fairness, and Performance Perspective

abstract: 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.


title: Artificial Intelligence and Systems Theory: Applied to Cooperative Robots

abstract: This paper describes an approach to the design of a population of cooperative robots based on concepts borrowed from Systems Theory and Artificial Intelligence. The research has been developed under the SocRob project, carried out by the Intelligent Systems Laboratory at the Institute for Systems and Robotics - Instituto Superior Tecnico (ISR/IST) in Lisbon. The acronym of the project stands both for "Society of Robots" and "Soccer Robots", the case study where we are testing our population of robots. Designing soccer robots is a very challenging problem, where the robots must act not only to shoot a ball towards the goal, but also to detect and avoid static (walls, stopped robots) and dynamic (moving robots) obstacles. Furthermore, they must cooperate to defeat an opposing team. Our past and current research in soccer robotics includes cooperative sensor fusion for world modeling, object recognition and tracking, robot navigation, multi-robot distributed task planning and coordination, including cooperative reinforcement learning in cooperative and adversarial environments, and behavior-based architectures for real time task execution of cooperating robot teams.


title: Programmable Ethernet Switches and Their Applications

abstract: Modern Ethernet switches support many advanced features beyond route learning and packet forwarding such as VLAN tagging, IGMP snooping, rate limiting, and status monitoring, which can be controlled through a programmatic interface. Traditionally, these features are mostly used to statically configure a network. This paper proposes to apply them as dynamic control mechanisms to maximize physical network link resources, to minimize failure recovery time, to enforce QoS requirements, and to support link-layer multicast without broadcasting. With these advanced programmable control mechanisms, standard Ethernet switches can be used as effective building blocks for metropolitan-area Ethernet networks (MEN), storage-area networks (SAN), and computation cluster interconnects. We demonstrate the usefulness of this new level of control over Ethernet switches with a MEN architecture that features multi-fold throughput gains and sub-second failure recovery time.


title: Dynamic Modelling and Adaptive Traction Control for Mobile Robots

abstract: Mobile robots have received a great deal of research in recent years. A significant amount of research has been published in many aspects related to mobile robots. Most of the research is devoted to design and develop some control techniques for robot motion and path planning. A large number of researchers have used kinematic models to develop motion control strategy for mobile robots. Their argument and assumption that these models are valid if the robot has low speed, low acceleration and light load. However, dynamic modelling of mobile robots is very important as they are designed to travel at higher speed and perform heavy duty work. This paper presents and discusses a new approach to develop a dynamic model and control strategy for wheeled mobile robot which I modelled as a rigid body that roles on two wheels and a castor. The motion control strategy consists of two levels. The first level is dealing with the dynamic of the system and denoted as Low level controller. The second level is developed to take care of path planning and trajectory generation.


title: Coevolution Based Adaptive Monte Carlo Localization (CEAMCL)

abstract: An adaptive Monte Carlo localization algorithm based on coevolution mechanism of ecological species is proposed. Samples are clustered into species, each of which represents a hypothesis of the robots pose. Since the coevolution between the species ensures that the multiple distinct hypotheses can be tracked stably, the problem of premature convergence when using MCL in highly symmetric environments can be solved. And the sample size can be adjusted adaptively over time according to the uncertainty of the robots pose by using the population growth model. In addition, by using the crossover and mutation operators in evolutionary computation, intra-species evolution can drive the samples move towards the regions where the desired posterior density is large. So a small size of samples can represent the desired density well enough to make precise localization. The new algorithm is termed coevolution based adaptive Monte Carlo localization (CEAMCL). Experiments have been carried out to prove the efficiency of the new localization algorithm.


title: Topological Navigation of Simulated Robots using Occupancy Grid

abstract: 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.


title: Design and Implementation of a General Decision-making Model in RoboCup Simulation

abstract: The study of the collaboration, coordination and negotiation among different agents in a multi-agent system (MAS) has always been the most challenging yet popular in the research of distributed artificial intelligence. In this paper, we will suggest for RoboCup simulation, a typical MAS, a general decision-making model, rather than define a different algorithm for each tactic (e.g. ball handling, pass, shoot and interception, etc.) in soccer games as most RoboCup simulation teams did. The general decision-making model is based on two critical factors in soccer games: the vertical distance to the goal line and the visual angle for the goalpost. We have used these two parameters to formalize the defensive and offensive decisions in RoboCup simulation and the results mentioned above had been applied in NOVAURO, original name is UJDB, a RoboCup simulation team of Jiangsu University, whose decision-making model, compared with that of Tsinghua University, the world champion team in 2001, is a universal model and easier to be implemented.


title: Space Robotics Part 2: Space-based Manipulators

abstract: In this second of three short papers, I introduce some of the basic concepts of space robotics with an emphasis on some specific challenging areas of research that are peculiar to the application of robotics to space infrastructure development. The style of these short papers is pedagogical and the concepts in this paper are developed from fundamental manipulator robotics. This second paper considers the application of space manipulators to on-orbit servicing (OOS), an application which has considerable commercial application. I provide some background to the notion of robotic on-orbit servicing and explore how manipulator control algorithms may be modified to accommodate space manipulators which operate in the micro-gravity of space.


title: Bionic Humans Using EAP as Artificial Muscles Reality and Challenges

abstract: For many years, the idea of a human with bionic muscles immediately conjures up science fiction images of a TV series superhuman character that was implanted with bionic muscles and portrayed with strength and speed far superior to any normal human. As fantastic as this idea may seem, recent developments in electroactive polymers (EAP) may one day make such bionics possible. Polymers that exhibit large displacement in response to stimulation that is other than electrical signal were known for many years. Initially, EAP received relatively little attention due to their limited actuation capability. However, in the recent years, the view of the EAP materials has changed due to the introduction of effective new materials that significantly surpassed the capability of the widely used piezoelectric polymer, PVDF. As this technology continues to evolve, novel mechanisms that are biologically inspired are expected to emerge. EAP materials can potentially provide actuation with lifelike response and more flexible configurations. While further improvements in performance and robustness are still needed, there already have been several reported successes. In recognition of the need for cooperation in this multidisciplinary field, the author initiated and organized a series of international forums that are leading to a growing number of research and development projects and to great advances in the field. In 1999, he challenged the worldwide science and engineering community of EAP experts to develop a robotic arm that is actuated by artificial muscles to win a wrestling match against a human opponent. In this paper, the field of EAP as artificial muscles will be reviewed covering the state of the art, the challenges and the vision for the progress in future years.


title: A Search Relevancy Tuning Method Using Expert Results Content Evaluation

abstract: The article presents an online relevancy tuning method using explicit user feedback. The author developed and tested a method of words' weights modification based on search result evaluation by user. User decides whether the result is useful or not after inspecting the full result content. The experiment proved that the constantly accumulated words weights base leads to better search quality in a specified data domain. The author also suggested future improvements of the method.


title: Extremal Properties of Three Dimensional Sensor Networks with Applications

abstract: In this paper, we analyze various critical transmitting/sensing ranges for connectivity and coverage in three-dimensional sensor networks. As in other large-scale complex systems, many global parameters of sensor networks undergo phase transitions: For a given property of the network, there is a critical threshold, corresponding to the minimum amount of the communication effort or power expenditure by individual nodes, above (resp. below) which the property exists with high (resp. a low) probability. For sensor networks, properties of interest include simple and multiple degrees of connectivity/coverage. First, we investigate the network topology according to the region of deployment, the number of deployed sensors and their transmitting/sensing ranges. More specifically, we consider the following problems: Assume that $n$ nodes, each capable of sensing events within a radius of $r$, are randomly and uniformly distributed in a 3-dimensional region $\mathcal{R}$ of volume $V$, how large must the sensing range be to ensure a given degree of coverage of the region to monitor? For a given transmission range, what is the minimum (resp. maximum) degree of the network? What is then the typical hop-diameter of the underlying network? Next, we show how these results affect algorithmic aspects of the network by designing specific distributed protocols for sensor networks.


title: A machine-independent port of the SR language run-time system to the NetBSD operating system

abstract: SR (synchronizing resources) is a PASCAL - style language enhanced with constructs for concurrent programming developed at the University of Arizona in the late 1980s. MPD (presented in Gregory Andrews' book about Foundations of Multithreaded, Parallel, and Distributed Programming) is its successor, providing the same language primitives with a different syntax. The run-time system (in theory, identical) of both languages provides the illusion of a multiprocessor machine on a single single- or multi- CPU Unix-like system or a (local area) network of Unix-like machines. Chair V of the Computer Science Department of the University of Bonn is operating a laboratory for a practical course in parallel programming consisting of computing nodes running NetBSD/arm, normally used via PVM, MPI etc. We are considering to offer SR and MPD for this, too. As the original language distributions are only targeted at a few commercial Unix systems, some porting effort is needed, outlined in the SR porting guide. The integrated POSIX threads support of NetBSD-2.0 should allow us to use library primitives provided for NetBSD's phtread system to implement the primitives needed by the SR run-time system, thus implementing 13 target CPUs at once and automatically making use of SMP on VAX, Alpha, PowerPC, Sparc, 32-bit Intel and 64 bit AMD CPUs. This paper describes work in progress.


title: Modules and Logic Programming

abstract: We study conditions for a concurrent construction of proof-nets in the framework developed by Andreoli in recent papers. We define specific correctness criteria for that purpose. We first study closed modules (i.e. validity of the execution of a logic program), then extend the criterion to open modules (i.e. validity during the execution) distinguishing criteria for acyclicity and connectability in order to allow incremental verification.


title: Security of public key cryptosystems based on Chebyshev Polynomials

abstract: 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.


title: Complexity of the Two-Variable Fragment with (Binary-Coded) Counting Quantifiers

abstract: We show that the satisfiability and finite satisfiability problems for the two-variable fragment of first-order logic with counting quantifiers are both in NEXPTIME, even when counting quantifiers are coded succinctly.


title: Logic Column 10: Specifying Confidentiality

abstract: This article illustrates the use of a logical specification language to capture various forms of confidentiality properties used in the security literature.


title: On Invariance and Convergence in Time Complexity theory

abstract: This article introduces three invariance principles under which P is different from NP. In the second part a theorem of convergence is proven. This theorem states that for any language L there exists an infinite sequence of languages from O(n) that converges to L.


title: Generating Conditional Probabilities for Bayesian Networks: Easing the Knowledge Acquisition Problem

abstract: The number of probability distributions required to populate a conditional probability table (CPT) in a Bayesian network, grows exponentially with the number of parent-nodes associated with that table. If the table is to be populated through knowledge elicited from a domain expert then the sheer magnitude of the task forms a considerable cognitive barrier. In this paper we devise an algorithm to populate the CPT while easing the extent of knowledge acquisition. The input to the algorithm consists of a set of weights that quantify the relative strengths of the influences of the parent-nodes on the child-node, and a set of probability distributions the number of which grows only linearly with the number of associated parent-nodes. These are elicited from the domain expert. The set of probabilities are obtained by taking into consideration the heuristics that experts use while arriving at probabilistic estimations. The algorithm is used to populate the CPT by computing appropriate weighted sums of the elicited distributions. We invoke the methods of information geometry to demonstrate how these weighted sums capture the expert's judgemental strategy.


title: A FP-Tree Based Approach for Mining All Strongly Correlated Pairs without Candidate Generation

abstract: Given a user-specified minimum correlation threshold and a transaction database, the problem of mining all-strong correlated pairs is to find all item pairs with Pearson's correlation coefficients above the threshold . Despite the use of upper bound based pruning technique in the Taper algorithm [1], when the number of items and transactions are very large, candidate pair generation and test is still costly. To avoid the costly test of a large number of candidate pairs, in this paper, we propose an efficient algorithm, called Tcp, based on the well-known FP-tree data structure, for mining the complete set of all-strong correlated item pairs. Our experimental results on both synthetic and real world datasets show that, Tcp's performance is significantly better than that of the previously developed Taper algorithm over practical ranges of correlation threshold specifications.


title: Feedback Capacity of the First-Order Moving Average Gaussian Channel

abstract: The feedback capacity of the stationary Gaussian additive noise channel has been open, except for the case where the noise is white. Here we find the feedback capacity of the stationary first-order moving average additive Gaussian noise channel in closed form. Specifically, the channel is given by $Y_i = X_i + Z_i,$ $i = 1, 2, ...,$ where the input $\{X_i\}$ satisfies a power constraint and the noise $\{Z_i\}$ is a first-order moving average Gaussian process defined by $Z_i = \alpha U_{i-1} + U_i,$ $|\alpha| \le 1,$ with white Gaussian innovations $U_i,$ $i = 0,1,....$ We show that the feedback capacity of this channel is $-\log x_0,$ where $x_0$ is the unique positive root of the equation $ \rho x^2 = (1-x^2) (1 - |\alpha|x)^2,$ and $\rho$ is the ratio of the average input power per transmission to the variance of the noise innovation $U_i$. The optimal coding scheme parallels the simple linear signalling scheme by Schalkwijk and Kailath for the additive white Gaussian noise channel -- the transmitter sends a real-valued information-bearing signal at the beginning of communication and subsequently refines the receiver's error by processing the feedback noise signal through a linear stationary first-order autoregressive filter. The resulting error probability of the maximum likelihood decoding decays doubly-exponentially in the duration of the communication. This feedback capacity of the first-order moving average Gaussian channel is very similar in form to the best known achievable rate for the first-order \emph{autoregressive} Gaussian noise channel studied by Butman, Wolfowitz, and Tiernan, although the optimality of the latter is yet to be established.


title: A Note on Bulk Quantum Turing Machine

abstract: Recently, among experiments for realization of quantum computers, NMR quantum computers have achieved the most impressive succession. There is a model of the NMR quantum computation,namely Atsumi and Nishino's bulk quantum Turing Machine. It assumes, however, an unnatural assumption with quantum mechanics. We, then, define a more natural and quantum mechanically realizable modified bulk quantum Turing Machine, and show its computational ability by comparing complexity classes with quantum Turing Machine's counter part.


title: Impact of IT on Higher education Through Continuing Education

abstract: 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.


title: Using Wireless Sensor Networks to Narrow the Gap between Low-Level Information and Context-Awareness

abstract: Wireless sensor networks are finally becoming a reality. In this paper, we present a scalable architecture for using wireless sensor networks in combination with wireless Ethernet networks to provide a complete end-to-end solution to narrow the gap between the low-level information and context awareness. We developed and implemented a complete proximity detector in order to give a wearable computer, such as a PDA, location context. Since location is only one element of contextawareness, we pursued utilizing photo sensors and temperature sensors in learning as much as possible about the environment. We used the TinyOS RF Motes as our test bed WSN (Wireless Sensor Network), 802.11 compatible hardware as our wireless Ethernet network, and conventional PCs and wired 802.3 networks to build the upper levels of the architecture.


title: Efficient Even Distribution of Power Consumption in Wireless Sensor Networks

abstract: One of the limitations of wireless sensor nodes is their inherent limited energy resource. Besides maximizing the lifetime of the sensor node, it is preferable to distribute the energy dissipated throughout the wireless sensor network in order to minimize maintenance and maximize overall system performance. We investigate a new routing algorithm that uses diffusion in order to achieve relatively even power dissipation throughout a wireless sensor network by making good local decisions. We leverage from concepts of peer-to-peer networks in which the system acts completely decentralized and all nodes in the network are equal peers. Our algorithm utilizes the node load, power levels, and spatial information in order to make the optimal routing decision. According to our preliminary experimental results, our proposed algorithm performs well according to its goals.


title: Content Based Image Retrieval with Mobile Agents and Steganography

abstract: In this paper we present an image retrieval system based on Gabor texture features, steganography, and mobile agents.. By employing the information hiding technique, the image attributes can be hidden in an image without degrading the image quality. Thus the image retrieval process becomes simple. Java based mobile agents manage the query phase of the system. Based on the simulation results, the proposed system not only shows the efficiency in hiding the attributes but also provides other advantages such as: (1) fast transmission of the retrieval image to the receiver, (2) searching made easy.


title: An Empirical Analysis of Internet Protocol Version 6 (IPv6)

abstract: Although the current Internet Protocol known as IPv4 has served its purpose for over 20 years, its days are numbered. With IPv6 reaching a mature enough level, there is a need to evaluate the performance benefits or drawbacks that the new IPv6 protocol will have in comparison to the well established IPv4 protocol. Theoretically, the overhead between the two different protocols should be directly proportional to the difference in the packet's header size, however according to our findings, the empirical performance difference between IPv4 and IPv6, especially when the transition mechanisms are taken into consideration, is much larger than anticipated. We first examine the performance of each protocol independently. We then examined two transition mechanisms which perform the encapsulation at various points in the network: host-to-host and router-to-router (tunneling). Our experiments were conducted using two dual stack (IPv4/IPv6) routers using end nodes running both Windows 2000 and Solaris 8.0 in order to compare two different IPv6 implementations side by side. Our tests were written in C++ and utilized metrics such as latency, throughput, CPU utilization, socket creation time, socket connection time, web server simulation, and a video client/server application for TCP/UDP in IPv4/IPv6 under both Windows 2000 and Solaris 8.0. Our empirical evaluation proved that IPv6 is not yet a mature enough technology and that it is still years away from having consistent and good enough implementations, as the performance of IPv6 in many cases proved to be significantly worse than IPv4.


title: e3D: An Energy-Efficient Routing Algorithm for Wireless Sensor Networks

abstract: One of the limitations of wireless sensor nodes is their inherent limited energy resource. Besides maximizing the lifetime of the sensor node, it is preferable to distribute the energy dissipated throughout the wireless sensor network in order to minimize maintenance and maximize overall system performance. Any communication protocol that involves synchronization of peer nodes incurs some overhead for setting up the communication. We introduce a new algorithm, e3D (energy-efficient Distributed Dynamic Diffusion routing algorithm), and compare it to two other algorithms, namely directed, and random clustering communication. We take into account the setup costs and analyze the energy-efficiency and the useful lifetime of the system. In order to better understand the characteristics of each algorithm and how well e3D really performs, we also compare e3D with its optimum counterpart and an optimum clustering algorithm. The benefit of introducing these ideal algorithms is to show the upper bound on performance at the cost of an astronomical prohibitive synchronization costs. We compare the algorithms in terms of system lifetime, power dissipation distribution, cost of synchronization, and simplicity of the algorithm. Our simulation results show that e3D performs comparable to its optimal counterpart while having significantly less overhead.


title: Routing Algorithms for Wireless Sensor Networks

abstract: Our contribution in this paper is e3D, a diffusion based routing protocol that prolongs the system lifetime, evenly distributes the power dissipation throughout the network, and incurs minimal overhead for synchronizing communication. We compare e3D with other algorithms in terms of system lifetime, power dissipation distribution, cost of synchronization, and simplicity of the algorithm.


title: Usage Policy-based CPU Sharing in VOs

abstract: Resource sharing within Grid collaborations usually implies specific sharing mechanisms at participating sites. Challenging policy issues can arise within virtual organizations (VOs) that integrate participants and resources spanning multiple physical institutions. Resource owners may wish to grant to one or more VOs the right to use certain resources subject to local policy and service level agreements, and each VO may then wish to use those resources subject to VO policy. Thus, we must address the question of what usage policies (UPs) should be considered for resource sharing in VOs. As a first step in addressing this question, we develop and evaluate different UP scenarios within a specialized context that mimics scientific Grids within which the resources to be shared are computers. We also present a UP architecture and define roles and functions for scheduling resources in such grid environments while satisfying resource owner policies.


title: Balanced Overlay Networks (BON): Decentralized Load Balancing via Self-Organized Random Networks

abstract: We present a novel framework, called balanced overlay networks (BON), that provides scalable, decentralized load balancing for distributed computing using large-scale pools of heterogeneous computers. Fundamentally, BON encodes the information about each node's available computational resources in the structure of the links connecting the nodes in the network. This distributed encoding is self-organized, with each node managing its in-degree and local connectivity via random-walk sampling. Assignment of incoming jobs to nodes with the most free resources is also accomplished by sampling the nodes via short random walks. Extensive simulations show that the resulting highly dynamic and self-organized graph structure can efficiently balance computational load throughout large-scale networks. These simulations cover a wide spectrum of cases, including significant heterogeneity in available computing resources and high burstiness in incoming load. We provide analytical results that prove BON's scalability for truly large-scale networks: in particular we show that under certain ideal conditions, the network structure converges to Erdos-Renyi (ER) random graphs; our simulation results, however, show that the algorithm does much better, and the structures seem to approach the ideal case of d-regular random graphs. We also make a connection between highly-loaded BONs and the well-known ball-bin randomized load balancing framework.


title: Numerical Solutions of 2-D Steady Incompressible Driven Cavity Flow at High Reynolds Numbers

abstract: Numerical calculations of the 2-D steady incompressible driven cavity flow are presented. The Navier-Stokes equations in streamfunction and vorticity formulation are solved numerically using a fine uniform grid mesh of 601x601. The steady driven cavity solutions are computed for Re<21,000 with a maximum absolute residuals of the governing equations that were less than 10-10. A new quaternary vortex at the bottom left corner and a new tertiary vortex at the top left corner of the cavity are observed in the flow field as the Reynolds number increases. Detailed results are presented and comparisons are made with benchmark solutions found in the literature.

categories: cs.NA math.NA physics.comp-ph physics.flu-dyn


title: Discussions on Driven Cavity Flow

abstract: The widely studied benchmark problem, 2-D driven cavity flow problem is discussed in details in terms of physical and mathematical and also numerical aspects. A very brief literature survey on studies on the driven cavity flow is given. Based on the several numerical and experimental studies, the fact of the matter is, above moderate Reynolds numbers physically the flow in a driven cavity is not two-dimensional. However there exist numerical solutions for 2-D driven cavity flow at high Reynolds numbers.


title: Fourth Order Compact Formulation of Navier-Stokes Equations and Driven Cavity Flow at High Reynolds Numbers

abstract: A new fourth order compact formulation for the steady 2-D incompressible Navier-Stokes equations is presented. The formulation is in the same form of the Navier-Stokes equations such that any numerical method that solve the Navier-Stokes equations can also be applied to this fourth order compact formulation. In particular in this work the formulation is solved with an efficient numerical method that requires the solution of tridiagonal systems using a fine grid mesh of 601x601. Using this formulation, the steady 2-D incompressible flow in a driven cavity is solved up to Reynolds number of 20,000 with fourth order spatial accuracy. Detailed solutions are presented.


title: Utilizing Reconfigurable Hardware Processors via Grid Services

abstract: Computational grids typically consist of nodes utilizing ordinary processors such as the Intel Pentium. Field Programmable Gate Arrays (FPGAs) are able to perform certain compute-intensive tasks very well due to their inherent parallel architecture, often resulting in orders of magnitude speedups. This paper explores how FPGAs can be transparently exposed for remote use via grid services, by integrating the Proteus Software Platform with the Globus Toolkit 3.0.


title: Describing and Simulating Internet Routes

abstract: This paper introduces relevant statistics for the description of routes in the internet, seen as a graph at the interface level. Based on the observed properties, we propose and evaluate methods for generating artificial routes suitable for simulation purposes. The work in this paper is based upon a study of over seven million route traces produced by CAIDA's skitter infrastructure.


title: Spontaneous Dynamics of Asymmetric Random Recurrent Spiking Neural Networks

abstract: We study in this paper the effect of an unique initial stimulation on random recurrent networks of leaky integrate and fire neurons. Indeed given a stochastic connectivity this so-called spontaneous mode exhibits various non trivial dynamics. This study brings forward a mathematical formalism that allows us to examine the variability of the afterward dynamics according to the parameters of the weight distribution. Provided independence hypothesis (e.g. in the case of very large networks) we are able to compute the average number of neurons that fire at a given time -- the spiking activity. In accordance with numerical simulations, we prove that this spiking activity reaches a steady-state, we characterize this steady-state and explore the transients.


title: Vers un environnement multi personnalites pour la configuration et le deploiement d'applications a base de composants logiciels

abstract: The multiplication of architecture description languages, component models and platforms implies a serious dilemma for component based software architects. On the one hand, they have to choose a language to describe concrete configurations which will be automatically deployed on execution platforms. On the other hand, they wish to capitalize their software architectures independently of any description languages or platforms. To solve this problem, we propose a multi personalities environment for the configuration and the deployment of component based applications. This environment is composed of a core capturing a canonical model of configuration and deployment, and a set of personalities tailored to languages and platforms. This paper details the architecture of such an environment and describes the personalities for the CORBA and Fractal component models.


title: J2EE Deployment: The JOnAS Case Study

abstract: La specification J2EE (Java 2 platform Enterprise Edition) definit une architecture de serveur d'application Java. Jusqu'a J2EE 1.3, seuls les aspects de deploiement concernant le developpeur d'applications etaient adresses. Avec J2EE 1.4, les interfaces et les etapes de deploiement ont ete plus precisement specifiees dans la specification "J2EE Deployment". JOnAS (Java Open Application Server) est une plate-forme J2EE developpee au sein du consortium ObjectWeb. Les aspects deploiement sont en cours de developpement. Cet article decrit les concepts lies au deploiement dans J2EE, ainsi que les problematiques levees lors de leur mise en oeuvre pour JOnAS. Il n'a pas pour but de presenter un travail abouti, mais illustre le deploiement par un cas concret et ebauche une liste de besoins non encore satisfaits dans le domaine. ----- The J2EE (Java 2 platform Enterprise Edition) specification defines an architecture for Java Application Servers. Until J2EE 1.3, the deployment aspect was addressed from the developer point of view only. Since J2EE 1.4, deployment APIs and steps have been more precisely specified within the "J2EE Deployment Specification". JOnAS (Java Open Application Server) is a J2EE platform implementation by ObjectWeb. The deployment aspects are under development. This article describes the J2EE Deployment concepts, and the issues raised when implementing deployment features within JOnAS. It does not provide a complete solution, but illustrates deployment through a concrete example and initiates a list of non fulfilled requirements.


title: SDS : Une infrastructure d'installation de logiciels libres pour des organisations multi-sites

abstract: Les developpements logiciels sur les systemes UNIX font de plus en plus appel aux logiciels libres. Nous proposons une solution de deploiement et de controle de ces logiciels libres au sein d'une grande organisation. Nous nous attachons particulierement a resoudre les problemes lies au deploiement multi-sites ainsi qu'a la gestion de configuration de ces deploiements. L'originalite de notre approche repose sur sa capacite a etre mise en oeuvre et controlee par les utilisateurs plutot que par les administrateurs, sans necessiter d'expertise particuliere, et par les possibilites de deploiement dans des environnements heterogenes. ----- Free and open source software is more and more used for software developments on UNIX systems. We are proposing a solution to control the deployment of free software in the context of a large corporation, focusing on multi-site deployment and configuration management. The originality of our approach rests on its ability to be implemented and controlled by users rather than administrators, without requiring any particular expertise, and on its facility to be deployed in heterogeneous environments.


title: Adaptation dynamique de services

abstract: This paper proposes a software architecture for dynamical service adaptation. The services are constituted by reusable software components. The adaptation's goal is to optimize the service function of their execution context. For a first step, the context will take into account just the user needs but other elements will be added. A particular feature in our proposition is the profiles that are used not only to describe the context's elements but also the components itself. An Adapter analyzes the compatibility between all these profiles and detects the points where the profiles are not compatibles. The same Adapter search and apply the possible adaptation solutions: component customization, insertion, extraction or replacement.


title: Runtime Reconfiguration of J2EE Applications

abstract: Runtime reconfiguration considered as "applying required changes to a running system" plays an important role for providing high availability not only of safety- and mission-critical systems, but also for commercial web-applications offering professional services. Hereby, the main concerns are maintaining the consistency of the running system during reconfiguration and minimizing its down-time caused by the reconfiguration. This paper focuses on the platform independent subsystem that realises deployment and redeployment of J2EE modules based on the new J2EE Deployment API as a part of the implementation of our proposed system architecture enabling runtime reconfiguration of component-based systems. Our "controlled runtime redeployment" comprises an extension of hot deployment and dynamic reloading, complemented by allowing for structural change


title: Deployment in dynamic environments

abstract: Information and communication technologies are moving towards a new stage where applications will be dynamically deployed, uninstalled, updated and (re)configured. Several approaches have been followed with the goal of creating a fully automated and context-aware deployment system. Ideally, this system should be capable of handling the dynamics of this new situation, without losing sight of other factors, such as performance, security, availability or scalability. We will take some of the technologies that follow the principles of Service Oriented Architectures, SOA, as a paradigm of dynamic environments. SOA promote the breaking down of applications into sets of loosely coupled elements, called services. Services can be dynamically bound, deployed, reconfigured, uninstalled and updated. First of all, we will try to offer a broad view on the specific deployment issues that arise in these environments. Later on, we will present our approach to the problem. One of the essential points that has to be tackled to develop an automated deployment engine will be to have enough information to carry out tasks without human intervention. In the article we will focus on the format and contents of deployment descriptors. Additionally, we will go into the details of the deployment framework for OSGi enabled gateways that has been developed by our research group. Finally we will give some concluding remarks and some ideas for future work


title: OpenCCM : une infrastructure a composants pour le deploiement d'applications a base de composants CORBA

abstract: Deployment of software components for building distributed applications consists of the coordination of a set of basic tasks like uploading component binaries to the execution sites, loading them in memory, instantiating components, interconnecting their ports, setting their business and technical attributes. The automation of the deployment process then requires the presence of a software infrastructure distributed itself on the different execution sites. This paper presents the characteristics of such an infrastructure for the deployment of CORBA component-based applications. This latter is designed and implemented in the context of our OpenCCM platform, an open source implementation of the CORBA Component Model. The main characteristic lays on the fact that this infrastructure is itself designed as a set of CORBA component assemblies. This allows its dynamic assembly during its deployment over the execution sites


title: Gestion du deploiement de composants sur reseau P2P

abstract: The deployment of component-based applications relies on a centralized directory to store the components. This paper describes an approach to distribute software components to be deployed on a set of peers of a peer to peer network in order to exploit some associated characteristics (load balancing, fault-tolerance, self-organisation). The proposed architecture is situated in the context of OSGI application deployment management. The software components (bundles) are distributed among a set of nodes participating in the execution of services. When a node wants to install a component which is not deployed locally, the component is looked for and installed using a p2p network. ----- Le deploiement d'applications a composants repose sur une approche d'annuaire centralise de stockage des composants. Cet article decrit une approche pour distribuer les composants logiciels a deployer sur un ensemble de noeuds d'un reseau pair-a-pair afin de pouvoir exploiter certaines caracteristiques associees (equilibrage de charge, tolerance de panne, auto-organisation). L'architecture proposee entre dans le cadre de la gestion du deploiement d'applications sur le modele OSGi. Les composants logiciels (ou bundles) sont repartis a travers un ensemble de noeuds participant a l'execution de services. Lorsqu'un noeud veut installer un composant et si celui-ci n'est pas encore deploye localement, il est recherche et installe en utilisant un reseau p2p


title: Un meta-modele pour l'automatisation du deploiement d'applications logicielles

abstract: Le deploiement est maintenant considere comme une activite a part entiere du cycle de vie du logiciel. Les grandes entreprises souhaitent pouvoir automatiser cette etape tout en prenant en compte les caracteristiques de chaque machine cible. Pour repondre a ces besoins, nous avons defini un environnement de deploiement : ORYA (Open enviRonment to deploY Applications). Cet environnement utilise un meta-modele de deploiement, decrit dans ce papier. Notre approche utilise aussi les technologies des federations et des procedes, fournissant un environnement flexible et extensible pour l'utilisateur. ----- The deployment is now a full activity of the software lifecycle. Large enterprises want to automate this step, taking into account characteristics of each target machine. To satisfy these needs, we have defined an environment for the deployment phase: ORYA (Open enviRonment to deploY Applications). This environment uses a deployment metamodel, described in this paper. Our approach is based also on federation and process federations, providing a flexible and extensible environment to the user


title: FROGi : Deploiement de composants Fractal sur OSGi

abstract: Cet article presente FROGi, une proposition visant a introduire le modele a composants Fractal a l'interieur de la plateforme de services OSGi. La motivation derriere ce travail est double. D'un cote, FROGi offre aux developpeurs de services OSGi un modele a composants extensibles qui facilite le developpement des bundles ; ces derniers restent toutefois compatibles avec les bundles "patrimoniaux". D'un autre cote, FROGi beneficie de l'infrastructure de deploiement que represente OSGi et qui facilite la realisation du conditionnement et du deploiement de composants Fractal. Dans FROGi, une application Fractal est conditionnee sous la forme d'un ou plusieurs bundles et elle peut etre deployee de facon partielle et les activites de deploiement peuvent avoir lieu de facon continue. -- This paper presents FROGi, a proposal to introduce the Fractal component model into the OSGi services platform. There are two motivations for this work. The first one is to offer a flexible component model to the OSGi developers to simplify bundle development. Bundles developed with FROGi are nevertheless compatible with standard bundles. The second motivation is to leverage OSGi's deployment capabilities to package and deploy Fractal components. In FROGi, a Fractal application is packaged and delivered as a set of OSGi bundles; such an application supports partial deployment and additionally, deployment activities can occur continuously.


title: From Tensor Equations to Numerical Code -- Computer Algebra Tools for Numerical Relativity

abstract: In this paper we present our recent work in developing a computer-algebra tool for systems of partial differential equations (PDEs), termed "Kranc". Our work is motivated by the problem of finding solutions of the Einstein equations through numerical simulations. Kranc consists of Mathematica based computer-algebra packages, that facilitate the task of dealing with symbolic tensorial calculations and realize the conversion of systems of partial differential evolution equations into parallelized C or Fortran code.


title: Lower-Stretch Spanning Trees

abstract: We prove that every weighted graph contains a spanning tree subgraph of average stretch O((log n log log n)^2). Moreover, we show how to construct such a tree in time O(m log^2 n).


title: An Evaluated Certification Services System for the German National Root CA - Legally Binding and Trustworthy Transactions in E-Business and E-Government

abstract: National Root CAs enable legally binding E-Business and E-Government transactions. This is a report about the development, the evaluation and the certification of the new certification services system for the German National Root CA. We illustrate why a new certification services system was necessary, and which requirements to the new system existed. Then we derive the tasks to be done from the mentioned requirements. After that we introduce the initial situation at the beginning of the project. We report about the very process and talk about some unfamiliar situations, special approaches and remarkable experiences. Finally we present the ready IT system and its impact to E-Business and E-Government.


title: Using LDAP Directories for Management of PKI Processes

abstract: 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.


title: Towards a Flexible Intra-Trustcenter Management Protocol

abstract: This paper proposes the Intra Trustcenter Protocol (ITP), a flexible and secure management protocol for communication between arbitrary trustcenter components. Unlike other existing protocols (like PKCS#7, CMP or XKMS) ITP focuses on the communication within a trustcenter. It is powerful enough for transferring complex messages which are machine and human readable and easy to understand. In addition it includes an extension mechanism to be prepared for future developments.


title: Planning for Directory Services in Public Key Infrastructures

abstract: In this paper we provide a guide for public key infrastructure designers and administrators when planning for directory services. We concentrate on the LDAP directories and how they can be used to successfully publish PKI information. We analyse their available mechanisms and propose a best practice guide for use in PKI. We then take a look into the German Signature Act and Ordinance and discuss their part as far as directories concerning. Finally, we translate those to the LDAP directories practices.


title: CDN: Content Distribution Network

abstract: Internet evolves and operates largely without a central coordination, the lack of which was and is critically important to the rapid growth and evolution of Internet. However, the lack of management in turn makes it very difficult to guarantee proper performance and to deal systematically with performance problems. Meanwhile, the available network bandwidth and server capacity continue to be overwhelmed by the skyrocketing Internet utilization and the accelerating growth of bandwidth intensive content. As a result, Internet service quality perceived by customers is largely unpredictable and unsatisfactory. Content Distribution Network (CDN) is an effective approach to improve Internet service quality. CDN replicates the content from the place of origin to the replica servers scattered over the Internet and serves a request from a replica server close to where the request originates. In this paper, we first give an overview about CDN. We then present the critical issues involved in designing and implementing an effective CDN and survey the approaches proposed in literature to address these problems. An example of CDN is described to show how a real commercial CDN operates. After this, we present a scheme that provides fast service location for peer-to-peer systems, a special type of CDN with no infrastructure support. We conclude with a brief projection about CDN.


title: Data Path Processing in Fast Programmable Routers

abstract: Internet is growing at a fast pace. The link speeds are surging toward 40 Gbps with the emergence of faster link technologies. New applications are coming up which require intelligent processing at the intermediate routers. Switches and routers are becoming the bottlenecks in fast communication. On one hand faster links deliver more packets every second and on the other hand intelligent processing consumes more CPU cycles at the router. The conflicting goals of providing faster but computationally expensive processing call for new approaches in designing routers. This survey takes a look at the core functionalities, like packet classification, buffer memory management, switch scheduling and output link scheduling performed by a router in its data path processing and discusses the algorithms that aim to reduce the performance bound for these operations. An important requirement for the routers is to provide Quality of Service guarantees. We propose an algorithm to guarantee QoS in Input Queued Routers. The hardware solution to speed up router operation was Application Specific Integrated Circuits (ASICs). But the inherent inflexibility of the method is a demerit as network standards and application requirements are constantly evolving, which seek a faster turnaround time to keep up with the changes. The promise of Network Processors (NP) is the flexibility of general-purpose processors together with the speed of ASICs. We will study the architectural choices for the design of Network Processors and focus on some of the commercially available NPs. There is a plethora of NP vendors in the market. The discussion on the NP benchmarks sets the normalizing platform to evaluate these NPs.


title: Comparing Multi-Target Trackers on Different Force Unit Levels

abstract: Consider the problem of tracking a set of moving targets. Apart from the tracking result, it is often important to know where the tracking fails, either to steer sensors to that part of the state-space, or to inform a human operator about the status and quality of the obtained information. An intuitive quality measure is the correlation between two tracking results based on uncorrelated observations. In the case of Bayesian trackers such a correlation measure could be the Kullback-Leibler difference. We focus on a scenario with a large number of military units moving in some terrain. The units are observed by several types of sensors and "meta-sensors" with force aggregation capabilities. The sensors register units of different size. Two separate multi-target probability hypothesis density (PHD) particle filters are used to track some type of units (e.g., companies) and their sub-units (e.g., platoons), respectively, based on observations of units of those sizes. Each observation is used in one filter only. Although the state-space may well be the same in both filters, the posterior PHD distributions are not directly comparable -- one unit might correspond to three or four spatially distributed sub-units. Therefore, we introduce a mapping function between distributions for different unit size, based on doctrine knowledge of unit configuration. The mapped distributions can now be compared -- locally or globally -- using some measure, which gives the correlation between two PHD distributions in a bounded volume of the state-space. To locate areas where the tracking fails, a discretized quality map of the state-space can be generated by applying the measure locally to different parts of the space.


title: Extremal optimization for sensor report pre-processing

abstract: We describe the recently introduced extremal optimization algorithm and apply it to target detection and association problems arising in pre-processing for multi-target tracking. Here we consider the problem of pre-processing for multiple target tracking when the number of sensor reports received is very large and arrives in large bursts. In this case, it is sometimes necessary to pre-process reports before sending them to tracking modules in the fusion system. The pre-processing step associates reports to known tracks (or initializes new tracks for reports on objects that have not been seen before). It could also be used as a pre-process step before clustering, e.g., in order to test how many clusters to use. The pre-processing is done by solving an approximate version of the original problem. In this approximation, not all pair-wise conflicts are calculated. The approximation relies on knowing how many such pair-wise conflicts that are necessary to compute. To determine this, results on phase-transitions occurring when coloring (or clustering) large random instances of a particular graph ensemble are used.


title: Geographic Routing with Limited Information in Sensor Networks

abstract: Geographic routing with greedy relaying strategies have been widely studied as a routing scheme in sensor networks. These schemes assume that the nodes have perfect information about the location of the destination. When the distance between the source and destination is normalized to unity, the asymptotic routing delays in these schemes are $\Theta(\frac{1}{M(n)}),$ where M(n) is the maximum distance traveled in a single hop (transmission range of a radio). In this paper, we consider routing scenarios where nodes have location errors (imprecise GPS), or where only coarse geographic information about the destination is available, and only a fraction of the nodes have routing information. We show that even with such imprecise or limited destination-location information, the routing delays are $\Theta(\frac{1}{M(n)})$. We also consider the throughput-capacity of networks with progressive routing strategies that take packets closer to the destination in every step, but not necessarily along a straight-line. We show that the throughput-capacity with progressive routing is order-wise the same as the maximum achievable throughput-capacity.


title: Building Chinese Lexicons from Scratch by Unsupervised Short Document Self-Segmentation

abstract: Chinese text segmentation is a well-known and difficult problem. On one side, there is not a simple notion of "word" in Chinese language making really hard to implement rule-based systems to segment written texts, thus lexicons and statistical information are usually employed to achieve such a task. On the other side, any piece of Chinese text usually includes segments present neither in the lexicons nor in the training data. Even worse, such unseen sequences can be segmented into a number of totally unrelated words making later processing phases difficult. For instance, using a lexicon-based system the sequence ???(Baluozuo, Barroso, current president-designate of the European Commission) can be segmented into ?(ba, to hope, to wish) and ??(luozuo, an undefined word) changing completely the meaning of the sentence. A new and extremely simple algorithm specially suited to work over short Chinese documents is introduced. This new algorithm performs text "self-segmentation" producing results comparable to those achieved by native speakers without using either lexicons or any statistical information beyond the obtained from the input text. Furthermore, it is really robust for finding new "words", especially proper nouns, and it is well suited to build lexicons from scratch. Some preliminary results are provided in addition to examples of its employment.


title: A Self-Reconfigurable Computing Platform Hardware Architecture

abstract: Field Programmable Gate Arrays (FPGAs) have recently been increasingly used for highly-parallel processing of compute intensive tasks. This paper introduces an FPGA hardware platform architecture that is PC-based, allows for fast reconfiguration over the PCI bus, and retains a simple physical hardware design. The design considerations are first discussed, then the resulting system architecture designed is illustrated. Finally, experimental results on the FPGA resources utilized for this design are presented.


title: Lower bounds on the Deterministic and Quantum Communication Complexity of Hamming Distance

abstract: Alice and Bob want to know if two strings of length n are almost equal. That is, do they differ on \textit{at most} a bits? Let 0\leq a\leq n-1. We show that any deterministic protocol, as well as any error-free quantum protocol (C* version), for this problem requires at least n-2 bits of communication. We show the same bounds for the problem of determining if two strings differ in exactly a bits. We also prove a lower bound of n/2-1 for error-free Q* quantum protocols. Our results are obtained by lower-bounding the ranks of the appropriate matrices.


title: Transparent Format Migration of Preserved Web Content

abstract: 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.


title: Notes On The Design Of An Internet Adversary

abstract: 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.


title: Supporting Bandwidth Guarantee and Mobility for Real-Time Applications on Wireless LANs

abstract: The proliferation of IEEE 802.11-based wireless LANs opens up avenues for creation of several tetherless and mobility oriented services. Most of these services, like voice over WLAN, media streaming etc., generate delay and bandwidth sensitive traffic. These traffic flows require undisrupted network connectivity with some QoS guarantees. Unfortunately, there is no adequate support built into these wireless LANs towards QoS provisioning. Further, the network layer handoff latency incurred by mobile nodes in these wireless LANs is too high for real-time applications to function properly. In this paper, we describe a QoS mechanism, called Rether, to effectively support bandwidth guarantee on wireless LANs. Rether is designed to support the current wireless LAN technologies like 802.11b and 802.11a with a specific capability of being tailored for QoS oriented technology like 802.11e. We also describe a low-latency handoff mechanism which expedites network level handoff to provide real-time applications with an added advantage of seamless mobility.


title: Modeling the input history of programs for improved instruction-memory performance

abstract: When a program is loaded into memory for execution, the relative position of its basic blocks is crucial, since loading basic blocks that are unlikely to be executed first places them high in the instruction-memory hierarchy only to be dislodged as the execution goes on. In this paper we study the use of Bayesian networks as models of the input history of a program. The main point is the creation of a probabilistic model that persists as the program is run on different inputs and at each new input refines its own parameters in order to reflect the program's input history more accurately. As the model is thus tuned, it causes basic blocks to be reordered so that, upon arrival of the next input for execution, loading the basic blocks into memory automatically takes into account the input history of the program. We report on extensive experiments, whose results demonstrate the efficacy of the overall approach in progressively lowering the execution times of a program on identical inputs placed randomly in a sequence of varied inputs. We provide results on selected SPEC CINT2000 programs and also evaluate our approach as compared to the gcc level-3 optimization and to Pettis-Hansen reordering.


title: Reconfigurations dynamiques de services dans un intergiciel a composants CORBA CCM

abstract: Today, component oriented middlewares are used to design, develop and deploy easily distributed applications, by ensuring the heterogeneity, interoperability, and reuse of the software modules, and the separation between the business code encapsulated in the components and the system code managed by the containers. Several standards answer this definition such as: CCM (CORBA Component Model), EJB (Enterprise Java Beans) and .Net. However these standards offer a limited and fixed number of system services, removing any possibility to add system services or to reconfigure dynamically the middleware. Our works propose mechanisms to add and to adapt dynamically the system services, based on a reconfiguration language which is dynamically adaptable to the need of the reconfiguration, and on a tool of dynamic reconfiguration, a prototype was achieved for the OpenCCM platform, that is an implementation of the CCM specification. This work was partially financed by the european project IST-COACH (2001-34445).


title: Support pour la reconfiguration d'implantation dans les applications a composants Java

abstract: Nowadays, numerous component models are used for various purposes: to build applications, middleware or even operating systems. Those models commonly support structure reconfiguration, that is modification of application's architecture at runtime. On the other hand, very few allow implementation reconfiguration, that is runtime modification of the code of components building the application. In this article we present the work we performed on JULIA, a Java-based implementation of the FRACTAL component model, in order for it to support implementation reconfigurations. We show how we overcame the limitations of Java class loading mechanism to allow runtime modifications of components' implementation and interfaces. We also describe the integration of our solution with the JULIA ADL.


title: Contractualisation des ressources pour le deploiement des composants logiciels

abstract: Software deployment can turn into a baffling problem when the components being deployed exhibit non-functional requirements. If the platform on which such components are deployed cannot satisfy their non-functional requirements, then they may in turn fail to perform satisfactorily. In this paper, we present a contract-based approach to take a specific category of non-functional properties specified by components into account, that is those that pertain to the resources that are necessary for their execution.


title: Gestion transactionnelle de la reprise sur erreurs dans le deploiement

abstract: With the development of the networks and the Internet, the problems of automated deployment on broad scale became increasingly crucial. Software deployment is a complex process covering several activities going from the configuration to the retirement of a software product. During the execution of a deployment process, exceptions can be met which put the site in an incoherent state. To solve them, we propose an approach based on transactional concepts which describes the actions to be undertaken when an exceptional situation is met during the deployment process. The approach guaranties the respect of the site's consistency by preserving part of the work already carried out by the process. This article presents our approach and an experimentation made in an academic deployment system.


title: Deploiement d'ordonnanceurs de processus specifiques dans un systeme d'exploitation generaliste

abstract: 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.


title: A Software Architecture for Automatic Deployment of CORBA Components Using Grid Technologies

abstract: 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.


title: Pandora : une plate-forme efficace pour la construction d'applications autonomes

abstract: Autonomic computing has been proposed recently as a way to address the difficult management of applications whose complexity is constantly increasing. Autonomous applications will have to be especially flexible and be able to monitor themselves permanently. This work presents a framework, Pandora, which eases the construction of applications that satisfy this double goal. Pandora relies on an original application programming pattern - based on stackable layers and message passing - to obtain minimalist model and architecture that allows to control the overhead imposed by the full reflexivity of the framework. Besides, a prototype of the framework has been implemented in C++. A detailed performance study, together with examples of use, complement this presentation


title: Des correctifs de securite a la mise a jour

abstract: The ever growing software complexity suggests that they will never be bugfree and therefore secure. Software compagnies regulary publish updates. But maybe because of lack of time or care or maybe because stopping application is annoying, such updates are rarely if ever deployed on users' machines. We propose an integrated tool allowing system administrators to deploy critical security updates on the fly on applications running remotly without end-user intervention. Our approach is based on an aspect weaving system, Arachne, that dynamicaly rewrites binary code. Hence updated applications are still running while they are updated. Our second tool Minerve integrates Arachne within the standart updating process: Minerve takes a patch produced by dif and eventually builds a dynamic patch that can later be woven to update the application on the fly. In addition, Minerve allows to consult patches translated in a dedicated language and hence eases auditing tasks.