OpenRaiser/Intern-Atlas huggingface dataset:
Using Regression Techniques to Predict Large Data Transfers
Venue: arXiv cs.DC 2003
Year: 2003

The recent proliferation of Data Grids and the increasingly common practice of using resources as distributed data stores provide a convenient environment for communities of researchers to share, replicate, and manage access to copies of large datasets. This has led to the question of which replica can be accessed most efficiently. In such environments, fetching data from one of the several replica locations requires accurate predictions of end-to-end transfer times. The answer to this question can depend on many factors, including physical characteristics of the resources and the load behavior on the CPUs, networks, and storage devices that are part of the end-to-end data path linking possible sources and sinks. Our approach combines end-to-end application throughput observations with network and disk load variations and captures whole-system performance and variations in load patterns. Our predictions characterize the effect of load variations of several shared devices (network and disk) on file transfer times. We develop a suite of univariate and multivariate predictors that can use multiple data sources to improve the accuracy of the predictions as well as address Data Grid variations (availability of data and sporadic nature of transfers). We ran a large set of data transfer experiments using GridFTP and observed performance predictions within 15% error for our testbed sites, which is quite promising for a pragmatic system.
How NP got a new definition: a survey of probabilistically checkable proofs
Venue: arXiv cs.CC 2003
Year: 2003

We survey a collective achievement of a group of researchers: the PCP Theorems. They give new definitions of the class \np, and imply that computing approximate solutions to many \np-hard problems is itself \np-hard. Techniques developed to prove them have had many other consequences.
On a composition of digraphs
Venue: arXiv cs.DM 2003
Year: 2003

Many "good" topologies for interconnection networks are based on line digraphs of regular digraphs. These digraphs support unitary matrices. We propose the property "being the digraph of a unitary matrix" as additional criterion for the design of new interconnection networks. We define a composition of digraphs, which we call diagonal union. Diagonal union can be used to construct digraphs of unitary matrices. We remark that digraphs obtained via diagonal union are state split graphs, as defined in symbolic dynamics. Finally, we list some potential directions for future research.
On the Ramsey Numbers for Bipartite Multigraphs
Venue: arXiv cs.DM 2003
Year: 2003

A coloring of a complete bipartite graph is shuffle-preserved if it is the case that assigning a color $c$ to edges $(u, v)$ and $(u', v')$ enforces the same color assignment for edges $(u, v')$ and $(u',v)$. (In words, the induced subgraph with respect to color $c$ is complete.) In this paper, we investigate a variant of the Ramsey problem for the class of complete bipartite multigraphs. (By a multigraph we mean a graph in which multiple edges, but no loops, are allowed.) Unlike the conventional m-coloring scheme in Ramsey theory which imposes a constraint (i.e., $m$) on the total number of colors allowed in a graph, we introduce a relaxed version called m-local coloring which only requires that, for every vertex $v$, the number of colors associated with $v$'s incident edges is bounded by $m$. Note that the number of colors found in a graph under $m$-local coloring may exceed m. We prove that given any $n \times n$ complete bipartite multigraph $G$, every shuffle-preserved $m$-local coloring displays a monochromatic copy of $K_{p,p}$ provided that $2(p-1)(m-1) < n$. Moreover, the above bound is tight when (i) $m=2$, or (ii) $n=2^k$ and $m=3\cdot 2^{k-2}$ for every integer $k\geq 2$. As for the lower bound of $p$, we show that the existence of a monochromatic $K_{p,p}$ is not guaranteed if $p> \lceil \frac{n}{m} \rceil$. Finally, we give a generalization for $k$-partite graphs and a method applicable to general graphs. Many conclusions found in $m$-local coloring can be inferred to similar results of $m$-coloring.
Optimizing Optimal Reduction: A Type Inference Algorithm for Elementary Affine Logic
Venue: arXiv cs.LO 2003
Year: 2003

We present a type inference algorithm for lambda-terms in Elementary Affine Logic using linear constraints. We prove that the algorithm is correct and complete.
On Nonspecific Evidence
Venue: arXiv cs.AI 2003
Year: 2003

When simultaneously reasoning with evidences about several different events it is necessary to separate the evidence according to event. These events should then be handled independently. However, when propositions of evidences are weakly specified in the sense that it may not be certain to which event they are referring, this may not be directly possible. In this paper a criterion for partitioning evidences into subsets representing events is established. This criterion, derived from the conflict within each subset, involves minimising a criterion function for the overall conflict of the partition. An algorithm based on characteristics of the criterion function and an iterative optimisation among partitionings of evidences is proposed.
Creating Prototypes for Fast Classification in Dempster-Shafer Clustering
Venue: arXiv cs.AI 2003
Year: 2003

We develop a classification method for incoming pieces of evidence in Dempster-Shafer theory. This methodology is based on previous work with clustering and specification of originally nonspecific evidence. This methodology is here put in order for fast classification of future incoming pieces of evidence by comparing them with prototypes representing the clusters, instead of making a full clustering of all evidence. This method has a computational complexity of O(M * N) for each new piece of evidence, where M is the maximum number of subsets and N is the number of prototypes chosen for each subset. That is, a computational complexity independent of the total number of previously arrived pieces of evidence. The parameters M and N are typically fixed and domain dependent in any application.
Applying Data Mining and Machine Learning Techniques to Submarine Intelligence Analysis
Venue: arXiv cs.AI 2003
Year: 2003

We describe how specialized database technology and data analysis methods were applied by the Swedish defense to help deal with the violation of Swedish marine territory by foreign submarine intruders during the Eighties and early Nineties. Among several approaches tried some yielded interesting information, although most of the key questions remain unanswered. We conclude with a survey of belief-function- and genetic-algorithm-based methods which were proposed to support interpretation of intelligence reports and prediction of future submarine positions, respectively.
Fast Dempster-Shafer clustering using a neural network structure
Venue: arXiv cs.AI 2003
Year: 2003

In this article we study a problem within Dempster-Shafer theory where 2**n - 1 pieces of evidence are clustered by a neural structure into n clusters. The clustering is done by minimizing a metaconflict function. Previously we developed a method based on iterative optimization. However, for large scale problems we need a method with lower computational complexity. The neural structure was found to be effective and much faster than iterative optimization for larger problems. While the growth in metaconflict was faster for the neural structure compared with iterative optimization in medium sized problems, the metaconflict per cluster and evidence was moderate. The neural structure was able to find a global minimum over ten runs for problem sizes up to six clusters.
Dempster-Shafer clustering using Potts spin mean field theory
Venue: arXiv cs.AI 2003
Year: 2003

In this article we investigate a problem within Dempster-Shafer theory where 2**q - 1 pieces of evidence are clustered into q clusters by minimizing a metaconflict function, or equivalently, by minimizing the sum of weight of conflict over all clusters. Previously one of us developed a method based on a Hopfield and Tank model. However, for very large problems we need a method with lower computational complexity. We demonstrate that the weight of conflict of evidence can, as an approximation, be linearized and mapped to an antiferromagnetic Potts Spin model. This facilitates efficient numerical solution, even for large problem sizes. Optimal or nearly optimal solutions are found for Dempster-Shafer clustering benchmark tests with a time complexity of approximately O(N**2 log**2 N). Furthermore, an isomorphism between the antiferromagnetic Potts spin model and a graph optimization problem is shown. The graph model has dynamic variables living on the links, which have a priori probabilities that are directly related to the pairwise conflict between pieces of evidence. Hence, the relations between three different models are shown.
Untraceable Email Cluster Bombs: On Agent-Based Distributed Denial of Service
Venue: arXiv cs.CY 2003
Year: 2003

We uncover a vulnerability that allows for an attacker to perform an email-based attack on selected victims, using only standard scripts and agents. What differentiates the attack we describe from other, already known forms of distributed denial of service (DDoS) attacks is that an attacker does not need to infiltrate the network in any manner -- as is normally required to launch a DDoS attack. Thus, we see this type of attack as a poor man's DDoS. Not only is the attack easy to mount, but it is also almost impossible to trace back to the perpetrator. Along with descriptions of our attack, we demonstrate its destructive potential with (limited and contained) experimental results. We illustrate the potential impact of our attack by describing how an attacker can disable an email account by flooding its inbox; block competition during on-line auctions; harm competitors with an on-line presence; disrupt phone service to a given victim; cheat in SMS-based games; disconnect mobile corporate leaders from their networks; and disrupt electronic elections. Finally, we propose a set of countermeasures that are light-weight, do not require modifications to the infrastructure, and can be deployed in a gradual manner.
Towards automation of computing fabrics using tools from the fabric management workpackage of the EU DataGrid project
Venue: arXiv cs.DC 2003
Year: 2003

The EU DataGrid project workpackage 4 has as an objective to provide the necessary tools for automating the management of medium size to very large computing fabrics. At the end of the second project year subsystems for centralized configuration management (presented at LISA'02) and performance/exception monitoring have been delivered. This will soon be augmented with a subsystem for node installation and service configuration, which is based on existing widely used standards where available (e.g. rpm, kickstart, init.d scripts) and clean interfaces to OS dependent components (e.g. base installation and service management). The three subsystems together allow for centralized management of very large computer farms. Finally, a fault tolerance system is being developed for tying together the above subsystems to form a complete framework for automated enterprise computing management by 3Q03. All software developed is open source covered by the EU DataGrid project license agreements. This article describes the architecture behind the designed fabric management system and the status of the different developments. It also covers the experience with an existing tool for automated configuration and installation that have been adapted and used from the beginning to manage the EU DataGrid testbed, which is now used for LHC data challenges.
Sharp Bounds for Bandwidth of Clique Products
Venue: arXiv cs.DM 2003
Year: 2003

The bandwidth of a graph is the labeling of vertices with minimum maximum edge difference. For many graph families this is NP-complete. A classic result computes the bandwidth for the hypercube. We generalize this result to give sharp lower bounds for products of cliques. This problem turns out to be equivalent to one in communication over multiple channels in which channels can fail and the information sent over those channels is lost. The goal is to create an encoding that minimizes the difference between the received and the original information while having as little redundancy as possible. Berger-Wolf and Reingold [2] have considered the problem for the equal size cliques (or equal capacity channels). This paper presents a tight lower bound and an algorithm for constructing the labeling for the product of any number of arbitrary size cliques.
Performance comparison between iSCSI and other hardware and software solutions
Venue: arXiv cs.PF 2003
Year: 2003

We report on our investigations on some technologies that can be used to build disk servers and networks of disk servers using commodity hardware and software solutions. It focuses on the performance that can be achieved by these systems and gives measured figures for different configurations. It is divided into two parts : iSCSI and other technologies and hardware and software RAID solutions. The first part studies different technologies that can be used by clients to access disk servers using a gigabit ethernet network. It covers block access technologies (iSCSI, hyperSCSI, ENBD). Experimental figures are given for different numbers of clients and servers. The second part compares a system based on 3ware hardware RAID controllers, a system using linux software RAID and IDE cards and a system mixing both hardware RAID and software RAID. Performance measurements for reading and writing are given for different RAID levels.
GraXML - Modular Geometric Modeler
Venue: arXiv cs.GR 2003
Year: 2003

Many entities managed by HEP Software Frameworks represent spatial (3-dimensional) real objects. Effective definition, manipulation and visualization of such objects is an indispensable functionality. GraXML is a modular Geometric Modeling toolkit capable of processing geometric data of various kinds (detector geometry, event geometry) from different sources and delivering them in ways suitable for further use. Geometric data are first modeled in one of the Generic Models. Those Models are then used to populate powerful Geometric Model based on the Java3D technology. While Java3D has been originally created just to provide visualization of 3D objects, its light weight and high functionality allow an effective reuse as a general geometric component. This is possible also thanks to a large overlap between graphical and general geometric functionality and modular design of Java3D itself. Its graphical functionalities also allow a natural visualization of all manipulated elements. All these techniques have been developed primarily (or only) for the Java environment. It is, however, possible to interface them transparently to Frameworks built in other languages, like for example C++. The GraXML toolkit has been tested with data from several sources, as for example ATLAS and ALICE detector description and ATLAS event data. Prototypes for other sources, like Geometry Description Markup Language (GDML) exist too and interface to any other source is easy to add.
Minimum Model Semantics for Logic Programs with Negation-as-Failure
Venue: arXiv cs.LO 2003
Year: 2003

We give a purely model-theoretic characterization of the semantics of logic programs with negation-as-failure allowed in clause bodies. In our semantics the meaning of a program is, as in the classical case, the unique minimum model in a program-independent ordering. We use an expanded truth domain that has an uncountable linearly ordered set of truth values between False (the minimum element) and True (the maximum), with a Zero element in the middle. The truth values below Zero are ordered like the countable ordinals. The values above Zero have exactly the reverse order. Negation is interpreted as reflection about Zero followed by a step towards Zero; the only truth value that remains unaffected by negation is Zero. We show that every program has a unique minimum model M_P, and that this model can be constructed with a T_P iteration which proceeds through the countable ordinals. Furthermore, we demonstrate that M_P can also be obtained through a model intersection construction which generalizes the well-known model intersection theorem for classical logic programming. Finally, we show that by collapsing the true and false values of the infinite-valued model M_P to (the classical) True and False, we obtain a three-valued model identical to the well-founded one.
On the Verge of One Petabyte - the Story Behind the BaBar Database System
Venue: arXiv cs.DB 2003
Year: 2003

The BaBar database has pioneered the use of a commercial ODBMS within the HEP community. The unique object-oriented architecture of Objectivity/DB has made it possible to manage over 700 terabytes of production data generated since May'99, making the BaBar database the world's largest known database. The ongoing development includes new features, addressing the ever-increasing luminosity of the detector as well as other changing physics requirements. Significant efforts are focused on reducing space requirements and operational costs. The paper discusses our experience with developing a large scale database system, emphasizing universal aspects which may be applied to any large scale system, independently of underlying technology used.
Visualization for Periodic Population Movement between Distinct Localities
Venue: arXiv cs.IR 2003
Year: 2003

We present a new visualization method to summarize and present periodic population movement between distinct locations, such as floors, buildings, cities, or the like. In the specific case of this paper, we have chosen to focus on student movement between college dormitories on the Columbia University campus. The visual information is presented to the information analyst in the form of an interactive geographical map, in which specific temporal periods as well as individual buildings can be singled out for detailed data exploration. The navigational interface has been designed to specifically meet a geographical setting.
Grid-based access control for Unix environments, Filesystems and Web Sites
Venue: arXiv cs.DC 2003
Year: 2003

The EU DataGrid has deployed a grid testbed at approximately 20 sites across Europe, with several hundred registered users. This paper describes authorisation systems produced by GridPP and currently used on the EU DataGrid Testbed, including local Unix pool accounts and fine-grained access control with Access Control Lists and Grid-aware filesystems, fileservers and web developement environments.
The FRED Event Display: an Extensible HepRep Client for GLAST
Venue: arXiv cs.GR 2003
Year: 2003

A new graphics client prototype for the HepRep protocol is presented. Based on modern toolkits and high level languages (C++ and Ruby), Fred is an experiment to test applicability of scripting facilities to the high energy physics event display domain. Its flexible structure, extensibility and the use of the HepRep protocol are key features for its use in the astroparticle experiment GLAST.
Multi-valued Connectives for Fuzzy Sets
Venue: arXiv cs.OH 2003
Year: 2003

We present a procedure for the construction of multi-valued t-norms and t-conorms. Our procedure makes use of a pair of single-valued t-norms and the respective dual t-conorms and produces interval-valued t-norms and t-conorms. In this manner we combine desirable characteristics of different t-norms and t-conorms; if we use the t-norm min and t-conorm max, then the resulting structure is a superlattice, i.e. the multivalued analog of a lattice.
Monodic temporal resolution
Venue: arXiv cs.LO 2003
Year: 2003

Until recently, First-Order Temporal Logic (FOTL) has been little understood. While it is well known that the full logic has no finite axiomatisation, a more detailed analysis of fragments of the logic was not previously available. However, a breakthrough by Hodkinson et.al., identifying a finitely axiomatisable fragment, termed the monodic fragment, has led to improved understanding of FOTL. Yet, in order to utilise these theoretical advances, it is important to have appropriate proof techniques for the monodic fragment. In this paper, we modify and extend the clausal temporal resolution technique, originally developed for propositional temporal logics, to enable its use in such monodic fragments. We develop a specific normal form for formulae in FOTL, and provide a complete resolution calculus for formulae in this form. Not only is this clausal resolution technique useful as a practical proof technique for certain monodic classes, but the use of this approach provides us with increased understanding of the monodic fragment. In particular, we here show how several features of monodic FOTL are established as corollaries of the completeness result for the clausal temporal resolution method. These include definitions of new decidable monodic classes, simplification of existing monodic classes by reductions, and completeness of clausal temporal resolution in the case of monodic logics with expanding domains, a case with much significance in both theory and practice.
OVAL: the CMS Testing Robot
Venue: arXiv cs.SE 2003
Year: 2003

Oval is a testing tool which help developers to detect unexpected changes in the behavior of their software. It is able to automatically compile some test programs, to prepare on the fly the needed configuration files, to run the tests within a specified Unix environment, and finally to analyze the output and check expectations. Oval does not provide utility code to help writing the tests, therefore it is quite independant of the programming/scripting language of the software to be tested. It can be seen as a kind of robot which apply the tests and warn about any unexpected change in the output. Oval was developed by the LLR laboratory for the needs of the CMS experiment, and it is now recommended by the CERN LCG project.
Fine-Grained Authorization for Job and Resource Management Using Akenti and the Globus Toolkit
Venue: arXiv cs.DC 2003
Year: 2003

As the Grid paradigm is adopted as a standard way of sharing remote resources across organizational domains, the need for fine-grained access control to these resources increases. This paper presents an authorization solution for job submission and control, developed as part of the National Fusion Collaboratory, that uses the Globus Toolkit 2 and the Akenti authorization service in order to perform fine-grained authorization of job and resource management requests in a Grid environment. At job startup, it allows the system to evaluate a user's Resource Specification Language request against authorization policies on resource usage (determining how many CPUs or memory a user can use on a given resource or which executables the user can run). Furthermore, based on authorization policies, it allows other virtual organization members to manage the user's job.
The Community Authorization Service: Status and Future
Venue: arXiv cs.SE 2003
Year: 2003

Virtual organizations (VOs) are communities of resource providers and users distributed over multiple policy domains. These VOs often wish to define and enforce consistent policies in addition to the policies of their underlying domains. This is challenging, not only because of the problems in distributing the policy to the domains, but also because of the fact that those domains may each have different capabilities for enforcing the policy. The Community Authorization Service (CAS) solves this problem by allowing resource providers to delegate some policy authority to the VO while maintaining ultimate control over their resources. In this paper we describe CAS and our past and current implementations of CAS, and we discuss our plans for CAS-related research.