OpenRaiser/Intern-Atlas huggingface dataset:
Relational Grid Monitoring Architecture (R-GMA)
Venue: arXiv cs.DC 2003
Year: 2003

We describe R-GMA (Relational Grid Monitoring Architecture) which has been developed within the European DataGrid Project as a Grid Information and Monitoring System. Is is based on the GMA from GGF, which is a simple Consumer-Producer model. The special strength of this implementation comes from the power of the relational model. We offer a global view of the information as if each Virtual Organisation had one large relational database. We provide a number of different Producer types with different characteristics; for example some support streaming of information. We also provide combined Consumer/Producers, which are able to combine information and republish it. At the heart of the system is the mediator, which for any query is able to find and connect to the best Producers for the job. We have developed components to allow a measure of inter-working between MDS and R-GMA. We have used it both for information about the grid (primarily to find out about what services are available at any one time) and for application monitoring. R-GMA has been deployed in various testbeds; we describe some preliminary results and experiences of this deployment.
Learning in Multiagent Systems: An Introduction from a Game-Theoretic Perspective
Venue: arXiv cs.MA 2003
Year: 2003

We introduce the topic of learning in multiagent systems. We first provide a quick introduction to the field of game theory, focusing on the equilibrium concepts of iterated dominance, and Nash equilibrium. We show some of the most relevant findings in the theory of learning in games, including theorems on fictitious play, replicator dynamics, and evolutionary stable strategies. The CLRI theory and n-level learning agents are introduced as attempts to apply some of these findings to the problem of engineering multiagent systems with learning agents. Finally, we summarize some of the remaining challenges in the field of learning in multiagent systems.
Centralized reward system gives rise to fast and efficient work sharing for intelligent Internet agents lacking direct communication
Venue: arXiv cs.IR 2003
Year: 2003

WWW has a scale-free structure where novel information is often difficult to locate. Moreover, Intelligent agents easily get trapped in this structure. Here a novel method is put forth, which turns these traps into information repositories, supplies: We populated an Internet environment with intelligent news foragers. Foraging has its associated cost whereas foragers are rewarded if they detect not yet discovered novel information. The intelligent news foragers crawl by using the estimated long-term cumulated reward, and also have a finite sized memory: the list of most promising supplies. Foragers form an artificial life community: the most successful ones are allowed to multiply, while unsuccessful ones die out. The specific property of this community is that there is no direct communication amongst foragers but the centralized rewarding system. Still, fast division of work is achieved.
El informe NERA analizado
Venue: arXiv cs.CY 2003
Year: 2003

This is a review of the article "Government Preferences for Promoting Open-Source Software: A Solution in Search of A Problem" by David Evans and Bernard J. Reddy. This report was paid for by Microsoft and put together at its request. Now Microsoft is using it as part of their lobbying campaign in Europe against governments' promotion of Open Source Software. As expected, this article is strongly biased and most of the conclusions are based upon false hypotheses and evidence.
Digital Version of Green`s Theorem and its Application to The Coverage Problem in Formal Verification
Venue: arXiv cs.SC 2003
Year: 2003

We present a novel scheme to the coverage problem, introducing a quantitative way to estimate the interaction between a block and its enviroment.This is achieved by setting a discrete version of Green`s theorem, specially adapted for Model Checking based verification of integrated circuits.This method is best suited for the coverage problem since it enables one to quantify the incompleteness or, on the other hand, the redundancy of a set of rules, describing the model under verification.Moreover this can be done continuously throughout the verification process, thus enabling the user to pinpoint the stages at which incompleteness/redundancy occurs. Although the method is presented locally on a small hardware example, we additionally show its possibility to provide precise coverage estimation also for large scale systems. We compare this method to others by checking it on the same test-cases.
What Is Working Memory and Mental Imagery? A Robot that Learns to Perform Mental Computations
Venue: arXiv cs.AI 2003
Year: 2003

This paper goes back to Turing (1936) and treats his machine as a cognitive model (W,D,B), where W is an "external world" represented by memory device (the tape divided into squares), and (D,B) is a simple robot that consists of the sensory-motor devices, D, and the brain, B. The robot's sensory-motor devices (the "eye", the "hand", and the "organ of speech") allow the robot to simulate the work of any Turing machine. The robot simulates the internal states of a Turing machine by "talking to itself." At the stage of training, the teacher forces the robot (by acting directly on its motor centers) to perform several examples of an algorithm with different input data presented on tape. Two effects are achieved: 1) The robot learns to perform the shown algorithm with any input data using the tape. 2) The robot learns to perform the algorithm "mentally" using an "imaginary tape." The model illustrates the simplest concept of a universal learning neurocomputer, demonstrates universality of associative learning as the mechanism of programming, and provides a simplified, but nontrivial neurobiologically plausible explanation of the phenomena of working memory and mental imagery. The model is implemented as a user-friendly program for Windows called EROBOT. The program is available at www.brain0.com/software.html.
Efficient Algorithms for Citation Network Analysis
Venue: arXiv cs.DL 2003
Year: 2003

In the paper very efficient, linear in number of arcs, algorithms for determining Hummon and Doreian's arc weights SPLC and SPNP in citation network are proposed, and some theoretical properties of these weights are presented. The nonacyclicity problem in citation networks is discussed. An approach to identify on the basis of arc weights an important small subnetwork is proposed and illustrated on the citation networks of SOM (self organizing maps) literature and US patents.
Evidential Force Aggregation
Venue: arXiv cs.AI 2003
Year: 2003

In this paper we develop an evidential force aggregation method intended for classification of evidential intelligence into recognized force structures. We assume that the intelligence has already been partitioned into clusters and use the classification method individually in each cluster. The classification is based on a measure of fitness between template and fused intelligence that makes it possible to handle intelligence reports with multiple nonspecific and uncertain propositions. With this measure we can aggregate on a level-by-level basis, starting from general intelligence to achieve a complete force structure with recognized units on all hierarchical levels.
Instrumenting self-modifying code
Venue: arXiv cs.SE 2003
Year: 2003

Adding small code snippets at key points to existing code fragments is called instrumentation. It is an established technique to debug certain otherwise hard to solve faults, such as memory management issues and data races. Dynamic instrumentation can already be used to analyse code which is loaded or even generated at run time.With the advent of environments such as the Java Virtual Machine with optimizing Just-In-Time compilers, a new obstacle arises: self-modifying code. In order to instrument this kind of code correctly, one must be able to detect modifications and adapt the instrumentation code accordingly, preferably without incurring a high penalty speedwise. In this paper we propose an innovative technique that uses the hardware page protection mechanism of modern processors to detect such modifications. We also show how an instrumentor can adapt the instrumented version depending on the kind of modificiations as well as an experimental evaluation of said techniques.
Towards declarative diagnosis of constraint programs over finite domains
Venue: arXiv cs.SE 2003
Year: 2003

The paper proposes a theoretical approach of the debugging of constraint programs based on a notion of explanation tree. The proposed approach is an attempt to adapt algorithmic debugging to constraint programming. In this theoretical framework for domain reduction, explanations are proof trees explaining value removals. These proof trees are defined by inductive definitions which express the removals of values as consequences of other value removals. Explanations may be considered as the essence of constraint programming. They are a declarative view of the computation trace. The diagnosis consists in locating an error in an explanation rooted by a symptom.
Postmortem Object Type Identification
Venue: arXiv cs.SE 2003
Year: 2003

This paper presents a novel technique for the automatic type identification of arbitrary memory objects from a memory dump. Our motivating application is debugging memory corruption problems in optimized, production systems -- a problem domain largely unserved by extant methodologies. We describe our algorithm as applicable to any typed language, and we discuss it with respect to the formidable obstacles posed by C. We describe the heuristics that we have developed to overcome these difficulties and achieve effective type identification on C-based systems. We further describe the implementation of our heuristics on one C-based system -- the Solaris operating system kernel -- and describe the extensions that we have added to the Solaris postmortem debugger to allow for postmortem type identification. We show that our implementation yields a sufficiently high rate of type identification to be useful for debugging memory corruption problems. Finally, we discuss some of the novel automated debugging mechanisms that can be layered upon postmortem type identification.
Fast Verification of Convexity of Piecewise-linear Surfaces
Venue: arXiv cs.CG 2003
Year: 2003

We show that a realization of a closed connected PL-manifold of dimension n-1 in n-dimensional Euclidean space (n>2) is the boundary of a convex polyhedron (finite or infinite) if and only if the interior of each (n-3)-face has a point, which has a neighborhood lying on the boundary of an n-dimensional convex body. No initial assumptions about the topology or orientability of the input surface are made. The theorem is derived from a refinement and generalization of Van Heijenoort's theorem on locally convex manifolds to spherical spaces. Our convexity criterion for PL-manifolds implies an easy polynomial-time algorithm for checking convexity of a given PL-surface in n-dimensional Euclidean or spherical space, n>2. The algorithm is worst case optimal with respect to both the number of operations and the algebraic degree. The algorithm works under significantly weaker assumptions and is easier to implement than convexity verification algorithms suggested by Mehlhorn et al (1996-1999), and Devillers et al.(1998). A paradigm of approximate convexity is suggested and a simplified algorithm of smaller degree and complexity is suggested for approximate floating point convexity verification.
A hierarchical Algorithm to Solve the Shortest Path Problem in Valued Graphs
Venue: arXiv cs.DS 2003
Year: 2003

This paper details a new algorithm to solve the shortest path problem in valued graphs. Its complexity is $O(D \log v)$ where $D$ is the graph diameter and $v$ its number of vertices. This complexity has to be compared to the one of the Dijkstra's algorithm, which is $O(e\log v)$ where $e$ is the number of edges of the graph. This new algorithm lies on a hierarchical representation of the graph, using radix trees. The performances of this algorithm show a major improvement over the ones of the algorithms known up to now.
On the continuous Fermat-Weber problem
Venue: arXiv cs.CG 2003
Year: 2003

We give the first exact algorithmic study of facility location problems that deal with finding a median for a continuum of demand points. In particular, we consider versions of the ``continuous k-median (Fermat-Weber) problem'' where the goal is to select one or more center points that minimize the average distance to a set of points in a demand region. In such problems, the average is computed as an integral over the relevant region, versus the usual discrete sum of distances. The resulting facility location problems are inherently geometric, requiring analysis techniques of computational geometry. We provide polynomial-time algorithms for various versions of the L1 1-median (Fermat-Weber) problem. We also consider the multiple-center version of the L1 k-median problem, which we prove is NP-hard for large k.
Providing Diversity in K-Nearest Neighbor Query Results
Venue: arXiv cs.DB 2003
Year: 2003

Given a point query Q in multi-dimensional space, K-Nearest Neighbor (KNN) queries return the K closest answers according to given distance metric in the database with respect to Q. In this scenario, it is possible that a majority of the answers may be very similar to some other, especially when the data has clusters. For a variety of applications, such homogeneous result sets may not add value to the user. In this paper, we consider the problem of providing diversity in the results of KNN queries, that is, to produce the closest result set such that each answer is sufficiently different from the rest. We first propose a user-tunable definition of diversity, and then present an algorithm, called MOTLEY, for producing a diverse result set as per this definition. Through a detailed experimental evaluation on real and synthetic data, we show that MOTLEY can produce diverse result sets by reading only a small fraction of the tuples in the database. Further, it imposes no additional overhead on the evaluation of traditional KNN queries, thereby providing a seamless interface between diversity and distance.
Maximum dispersion and geometric maximum weight cliques
Venue: arXiv cs.DS 2003
Year: 2003

We consider a facility location problem, where the objective is to ``disperse'' a number of facilities, i.e., select a given number k of locations from a discrete set of n candidates, such that the average distance between selected locations is maximized. In particular, we present algorithmic results for the case where vertices are represented by points in d-dimensional space, and edge weights correspond to rectilinear distances. Problems of this type have been considered before, with the best result being an approximation algorithm with performance ratio 2. For the case where k is fixed, we establish a linear-time algorithm that finds an optimal solution. For the case where k is part of the input, we present a polynomial-time approximation scheme.
Value-at-Risk and Expected Shortfall for Quadratic portfolio of securities with mixture of elliptic Distributed Risk Factors
Venue: arXiv cs.CE 2003
Year: 2003

Generally, in the financial literature, the notion of quadratic VaR is implicitly confused with the Delta-Gamma VaR, because more authors dealt with portfolios that contains derivatives instruments. In this paper, we postpone to estimate the Value-at-Risk of a quadratic portfolio of securities (i.e equities) without the Delta and Gamma greeks, when the joint log-returns changes with multivariate elliptic distribution. We have reduced the estimation of the quadratic VaR of such portfolio to a resolution of one dimensional integral equation. To illustrate our method, we give special attention to the mixture of normal and mixture of t-student distribution. For given VaR, when joint Risk Factors changes with elliptic distribution, we show how to estimate an Expected Shortfall .
An information theory for preferences
Venue: arXiv cs.AI 2003
Year: 2003

Recent literature in the last Maximum Entropy workshop introduced an analogy between cumulative probability distributions and normalized utility functions. Based on this analogy, a utility density function can de defined as the derivative of a normalized utility function. A utility density function is non-negative and integrates to unity. These two properties form the basis of a correspondence between utility and probability. A natural application of this analogy is a maximum entropy principle to assign maximum entropy utility values. Maximum entropy utility interprets many of the common utility functions based on the preference information needed for their assignment, and helps assign utility values based on partial preference information. This paper reviews maximum entropy utility and introduces further results that stem from the duality between probability and utility.
On secret sharing for graphs
Venue: arXiv cs.CR 2003
Year: 2003

In the paper we discuss how to share the secrets, that are graphs. So, far secret sharing schemes were designed to work with numbers. As the first step, we propose conditions for "graph to number" conversion methods. Hence, the existing schemes can be used, without weakening their properties. Next, we show how graph properties can be used to extend capabilities of secret sharing schemes. This leads to proposal of using such properties for number based secret sharing.
Design and Implementation of MPICH2 over InfiniBand with RDMA Support
Venue: arXiv cs.AR 2003
Year: 2003

For several years, MPI has been the de facto standard for writing parallel applications. One of the most popular MPI implementations is MPICH. Its successor, MPICH2, features a completely new design that provides more performance and flexibility. To ensure portability, it has a hierarchical structure based on which porting can be done at different levels. In this paper, we present our experiences designing and implementing MPICH2 over InfiniBand. Because of its high performance and open standard, InfiniBand is gaining popularity in the area of high-performance computing. Our study focuses on optimizing the performance of MPI-1 functions in MPICH2. One of our objectives is to exploit Remote Direct Memory Access (RDMA) in Infiniband to achieve high performance. We have based our design on the RDMA Channel interface provided by MPICH2, which encapsulates architecture-dependent communication functionalities into a very small set of functions. Starting with a basic design, we apply different optimizations and also propose a zero-copy-based design. We characterize the impact of our optimizations and designs using microbenchmarks. We have also performed an application-level evaluation using the NAS Parallel Benchmarks. Our optimized MPICH2 implementation achieves 7.6 $μ$s latency and 857 MB/s bandwidth, which are close to the raw performance of the underlying InfiniBand layer. Our study shows that the RDMA Channel interface in MPICH2 provides a simple, yet powerful, abstraction that enables implementations with high performance by exploiting RDMA operations in InfiniBand. To the best of our knowledge, this is the first high-performance design and implementation of MPICH2 on InfiniBand using RDMA support.
Problem of Application Job Monitoring in GRID Systems
Venue: arXiv cs.DC 2003
Year: 2003

We present a new approach to monitoring of the execution process of an application job in the GRID environment. The main point of the approach is use of GRID ervices to access monitoring information with the security level available in GRID.
2 P2P or Not 2 P2P?
Venue: arXiv cs.NI 2003
Year: 2003

In the hope of stimulating discussion, we present a heuristic decision tree that designers can use to judge the likely suitability of a P2P architecture for their applications. It is based on the characteristics of a wide range of P2P systems from the literature, both proposed and deployed.
Ackermann Encoding, Bisimulations, and OBDDs
Venue: arXiv cs.LO 2003
Year: 2003

We propose an alternative way to represent graphs via OBDDs based on the observation that a partition of the graph nodes allows sharing among the employed OBDDs. In the second part of the paper we present a method to compute at the same time the quotient w.r.t. the maximum bisimulation and the OBDD representation of a given graph. The proposed computation is based on an OBDD-rewriting of the notion of Ackermann encoding of hereditarily finite sets into natural numbers.
An Optimal Algorithm for the Maximum-Density Segment Problem
Venue: arXiv cs.DS 2003
Year: 2003

We address a fundamental problem arising from analysis of biomolecular sequences. The input consists of two numbers $w_{\min}$ and $w_{\max}$ and a sequence $S$ of $n$ number pairs $(a_i,w_i)$ with $w_i>0$. Let {\em segment} $S(i,j)$ of $S$ be the consecutive subsequence of $S$ between indices $i$ and $j$. The {\em density} of $S(i,j)$ is $d(i,j)=(a_i+a_{i+1}+...+a_j)/(w_i+w_{i+1}+...+w_j)$. The {\em maximum-density segment problem} is to find a maximum-density segment over all segments $S(i,j)$ with $w_{\min}\leq w_i+w_{i+1}+...+w_j \leq w_{\max}$. The best previously known algorithm for the problem, due to Goldwasser, Kao, and Lu, runs in $O(n\log(w_{\max}-w_{\min}+1))$ time. In the present paper, we solve the problem in O(n) time. Our approach bypasses the complicated {\em right-skew decomposition}, introduced by Lin, Jiang, and Chao. As a result, our algorithm has the capability to process the input sequence in an online manner, which is an important feature for dealing with genome-scale sequences. Moreover, for a type of input sequences $S$ representable in $O(m)$ space, we show how to exploit the sparsity of $S$ and solve the maximum-density segment problem for $S$ in $O(m)$ time.
Using Counterfactuals in Knowledge-Based Programming
Venue: arXiv cs.DC 2003
Year: 2003

This paper adds counterfactuals to the framework of knowledge-based programs of Fagin, Halpern, Moses, and Vardi. The use of counterfactuals is illustrated by designing a protocol in which an agent stops sending messages once it knows that it is safe to do so. Such behavior is difficult to capture in the original framework because it involves reasoning about counterfactual executions, including ones that are not consistent with the protocol. Attempts to formalize these notions without counterfactuals are shown to lead to rather counterintuitive behavior.