OpenRaiser/Intern-Atlas huggingface dataset:
Small Spans in Scaled Dimension
Venue: arXiv cs.CC 2003
Year: 2003

Juedes and Lutz (1995) proved a small span theorem for polynomial-time many-one reductions in exponential time. This result says that for language A decidable in exponential time, either the class of languages reducible to A (the lower span) or the class of problems to which A can be reduced (the upper span) is small in the sense of resource-bounded measure and, in particular, that the degree of A is small. Small span theorems have been proven for increasingly stronger polynomial-time reductions, and a small span theorem for polynomial-time Turing reductions would imply BPP != EXP. In contrast to the progress in resource-bounded measure, Ambos-Spies, Merkle, Reimann, and Stephan (2001) showed that there is no small span theorem for the resource-bounded dimension of Lutz (2000), even for polynomial-time many-one reductions. Resource-bounded scaled dimension, recently introduced by Hitchcock, Lutz, and Mayordomo (2003), provides rescalings of resource-bounded dimension. We use scaled dimension to further understand the contrast between measure and dimension regarding polynomial-time spans and degrees. We strengthen prior results by showing that the small span theorem holds for polynomial-time many-one reductions in the -3rd-order scaled dimension, but fails to hold in the -2nd-order scaled dimension. Our results also hold in exponential space. As an application, we show that determining the -2nd- or -1st-order scaled dimension in ESPACE of the many-one complete languages for E would yield a proof of P = BPP or P != PSPACE. On the other hand, it is shown unconditionally that the complete languages for E have -3rd-order scaled dimension 0 in ESPACE and -2nd- and -1st-order scaled dimension 1 in E.
Transforming the Structure of Network Interconnection and Transport
Venue: arXiv cs.CY 2003
Year: 2003

Vibrant development of a network-based economy requires separating investment in highly location specific local access technology from the development of standardized, geography-independent, wide-area network services. Thus far interconnection arrangements and associated regulations have been too closely tied to the idiosyncratic geographic structure of individual operators' networks. A key industry challenge is to foster the development of a wide area lattice of common geographic points of interconnection. Sound regulatory and anti-trust policy can help address this industry need.
Growth in the "New Economy": U.S. Bandwidth Use and Pricing Across the 1990s
Venue: arXiv cs.CY 2003
Year: 2003

An acceleration in the growth of communications bandwidth in use and a rapid reduction in bandwidth prices have not accompanied the U.S. economy's strong performance in the second half of the 1990s. Overall U.S. bandwidth in use has grown robustly throughout the 1990s, but growth has not significantly accelerated in the second half of 1990s. Average prices for U.S. bandwidth in use have fallen little in nominal terms in the second half of the 1990s. Policy makers and policy analysts should recognize that institutional change, rather than more competitors of established types, appears to be key to dramatic improvements in bandwidth growth and prices. Such a development could provide a significant additional impetus to aggregate growth and productivity.
Hardness as randomness: a survey of universal derandomization
Venue: arXiv cs.CC 2003
Year: 2003

We survey recent developments in the study of probabilistic complexity classes. While the evidence seems to support the conjecture that probabilism can be deterministically simulated with relatively low overhead, i.e., that $P=BPP$, it also indicates that this may be a difficult question to resolve. In fact, proving that probabilistic algorithms have non-trivial deterministic simulations is basically equivalent to proving circuit lower bounds, either in the algebraic or Boolean models.
A Framework for Searching AND/OR Graphs with Cycles
Venue: arXiv cs.AI 2003
Year: 2003

Search in cyclic AND/OR graphs was traditionally known to be an unsolved problem. In the recent past several important studies have been reported in this domain. In this paper, we have taken a fresh look at the problem. First, a new and comprehensive theoretical framework for cyclic AND/OR graphs has been presented, which was found missing in the recent literature. Based on this framework, two best-first search algorithms, S1 and S2, have been developed. S1 does uninformed search and is a simple modification of the Bottom-up algorithm by Martelli and Montanari. S2 performs a heuristically guided search and replicates the modification in Bottom-up's successors, namely HS and AO*. Both S1 and S2 solve the problem of searching AND/OR graphs in presence of cycles. We then present a detailed analysis for the correctness and complexity results of S1 and S2, using the proposed framework. We have observed through experiments that S1 and S2 output correct results in all cases.
The Ubiquitous Interactor - Device Independent Access to Mobile Services
Venue: arXiv cs.HC 2003
Year: 2003

The Ubiquitous Interactor (UBI) addresses the problems of design and development that arise around services that need to be accessed from many different devices. In UBI, the same service can present itself with different user interfaces on different devices. This is done by separating interaction between users and services from presentation. The interaction is kept the same for all devices, and different presentation information is provided for different devices. This way, tailored user interfaces for many different devices can be created without multiplying development and maintenance work. In this paper we describe the system design of UBI, the system implementation, and two services implemented for the system: a calendar service and a stockbroker service.
The NPC Framework for Building Information Dissemination Networks
Venue: arXiv cs.DL 2003
Year: 2003

Numerous systems for dissemination, retrieval, and archiving of documents have been developed in the past. Those systems often focus on one of these aspects and are hard to extend and combine. Typically, the transmission protocols, query and filtering languages are fixed as well as the interfaces to other systems. We rather envisage the seamless establishment of networks among the providers, repositories and consumers of information, supporting information retrieval and dissemination while being highly interoperable and extensible. We propose a framework with a single event-based mechanism that unifies document storage, retrieval, and dissemination. This framework offers complete openness with respect to document and metadata formats, transmission protocols, and filtering mechanisms. It specifies a high-level building kit, by which arbitrary processors for document streams can be incorporated to support the retrieval, transformation, aggregation and disaggregation of documents. Using the same kit, interfaces for different transmission protocols can be added easily to enable the communication with various information sources and information consumers.
Power Law Distributions in Class Relationships
Venue: arXiv cs.SE 2003
Year: 2003

Power law distributions have been found in many natural and social phenomena, and more recently in the source code and run-time characteristics of Object-Oriented (OO) systems. A power law implies that small values are extremely common, whereas large values are extremely rare. In this paper, we identify twelve new power laws relating to the static graph structures of Java programs. The graph structures analyzed represented different forms of OO coupling, namely, inheritance, aggregation, interface, parameter type and return type. Identification of these new laws provide the basis for predicting likely features of classes in future developments. The research in this paper ties together work in object-based coupling and World Wide Web structures.
A Monitoring System for the BaBar INFN Computing Cluster
Venue: arXiv cs.PF 2003
Year: 2003

Monitoring large clusters is a challenging problem. It is necessary to observe a large quantity of devices with a reasonably short delay between consecutive observations. The set of monitored devices may include PCs, network switches, tape libraries and other equipments. The monitoring activity should not impact the performances of the system. In this paper we present PerfMC, a monitoring system for large clusters. PerfMC is driven by an XML configuration file, and uses the Simple Network Management Protocol (SNMP) for data collection. SNMP is a standard protocol implemented by many networked equipments, so the tool can be used to monitor a wide range of devices. System administrators can display informations on the status of each device by connecting to a WEB server embedded in PerfMC. The WEB server can produce graphs showing the value of different monitored quantities as a function of time; it can also produce arbitrary XML pages by applying XSL Transformations to an internal XML representation of the cluster's status. XSL Transformations may be used to produce HTML pages which can be displayed by ordinary WEB browsers. PerfMC aims at being relatively easy to configure and operate, and highly efficient. It is currently being used to monitor the Italian Reprocessing farm for the BaBar experiment, which is made of about 200 dual-CPU Linux machines.
The use of Ethernet in the DataFlow of the ATLAS Trigger & DAQ
Venue: arXiv cs.NI 2003
Year: 2003

The article analyzes a proposed network topology for the ATLAS DAQ DataFlow, and identifies the Ethernet features required for a proper operation of the network: MAC address table size, switch performance in terms of throughput and latency, the use of Flow Control, Virtual LANs and Quality of Service. We investigate these features on some Ethernet switches, and conclude on their usefulness for the ATLAS DataFlow network.
A Generic Multi-node State Monitoring Subsystem
Venue: arXiv cs.DC 2003
Year: 2003

The BaBar online data acquisition (DAQ) system includes approximately fifty Unix systems that collectively implement the level-three trigger. These systems all run the same code. Each of these systems has its own state, and this state is expected to change in response to changes in the overall DAQ system. A specialized subsystem has been developed to initiate processing on this collection of systems, and to monitor them both for error conditions and to ensure that they all follow the same state trajectory within a specifiable period of time. This subsystem receives start commands from the main DAQ run control system, and reports major coherent state changes, as well as error conditions, back to the run control system. This state monitoring subsystem has the novel feature that it does not know anything about the state machines that it is monitoring, and hence does not introduce any fundamentally new state machine into the overall system. This feature makes it trivially applicable to other multi-node subsystems. Indeed it has already found a second application beyond the level-three trigger, within the BaBar experiment.
The Virtual Monte Carlo
Venue: arXiv cs.SE 2003
Year: 2003

The concept of Virtual Monte Carlo (VMC) has been developed by the ALICE Software Project to allow different Monte Carlo simulation programs to run without changing the user code, such as the geometry definition, the detector response simulation or input and output formats. Recently, the VMC classes have been integrated into the ROOT framework, and the other relevant packages have been separated from the AliRoot framework and can be used individually by any other HEP project. The general concept of the VMC and its set of base classes provided in ROOT will be presented. Existing implementations for Geant3, Geant4 and FLUKA and simple examples of usage will be described.
SCRAM: Software configuration and management for the LHC Computing Grid project
Venue: arXiv cs.OH 2003
Year: 2003

Recently SCRAM (Software Configuration And Management) has been adopted by the applications area of the LHC computing grid project as baseline configuration management and build support infrastructure tool. SCRAM is a software engineering tool, that supports the configuration management and management processes for software development. It resolves the issues of configuration definition, assembly break-down, build, project organization, run-time environment, installation, distribution, deployment, and source code distribution. It was designed with a focus on supporting a distributed, multi-project development work-model. We will describe the underlying technology, and the solutions SCRAM offers to the above software engineering processes, while taking a users view of the system under configuration management.
Modelling Biochemical Operations on RNA Secondary Structures
Venue: arXiv cs.CE 2003
Year: 2003

In this paper we model several simple biochemical operations on RNA molecules that modify their secondary structure by means of a suitable variation of Große-Rhode's Algebra Transformation Systems.
Monitoring Systems and Services
Venue: arXiv cs.OH 2003
Year: 2003

The DESY Computer Center is the home of O(1000) computers supplying a wide range of different services Monitoring such a large installation is a challenge. After a long time running a SNMP based commercial Network Management System, the evaluation of a new System was started. There are a lot of different commercial and freeware products on the market, but none of them fully satisfied all our requirements. After re-valuating our original requirements we selected NAGIOS as our monitoring and alarming tool. After a successful test we are in production since autumn 2002 and are extending the service to fully support a distributed monitoring and alarming.
Permutation Generation: Two New Permutation Algorithms
Venue: arXiv cs.DS 2003
Year: 2003

Two completely new algorithms for generating permutations, shift-cursor algorithm and level algorithm, and their efficient implementations are presented in this paper. One implementation of the shift cursor algorithm gives an optimal solution of the permutation generation problem, and one implementation of the level algorithm can be used to generate random permutations.
A Software Data Transport Framework for Trigger Applications on Clusters
Venue: arXiv cs.DC 2003
Year: 2003

In the future ALICE heavy ion experiment at CERN's Large Hadron Collider input data rates of up to 25 GB/s have to be handled by the High Level Trigger (HLT) system, which has to scale them down to at most 1.25 GB/s before being written to permanent storage. The HLT system that is being designed to cope with these data rates consists of a large PC cluster, up to the order of a 1000 nodes, connected by a fast network. For the software that will run on these nodes a flexible data transport and distribution software framework has been developed. This framework consists of a set of separate components, that can be connected via a common interface, allowing to construct different configurations for the HLT, that are even changeable at runtime. To ensure a fault-tolerant operation of the HLT, the framework includes a basic fail-over mechanism that will be further expanded in the future, utilizing the runtime reconnection feature of the framework's component interface. First performance tests show very promising results for the software, indicating that it can achieve an event rate for the data transport sufficiently high to satisfy ALICE's requirements.
A ROOT/IO Based Software Framework for CMS
Venue: arXiv cs.DB 2003
Year: 2003

The implementation of persistency in the Compact Muon Solenoid (CMS) Software Framework uses the core I/O functionality of ROOT. We will discuss the current ROOT/IO implementation, its evolution from the prior Objectivity/DB implementation, and the plans and ongoing work for the conversion to "POOL", provided by the LHC Computing Grid (LCG) persistency project.
Sequence Prediction based on Monotone Complexity
Venue: arXiv cs.AI 2003
Year: 2003

This paper studies sequence prediction based on the monotone Kolmogorov complexity Km=-log m, i.e. based on universal deterministic/one-part MDL. m is extremely close to Solomonoff's prior M, the latter being an excellent predictor in deterministic as well as probabilistic environments, where performance is measured in terms of convergence of posteriors or losses. Despite this closeness to M, it is difficult to assess the prediction quality of m, since little is known about the closeness of their posteriors, which are the important quantities for prediction. We show that for deterministic computable environments, the "posterior" and losses of m converge, but rapid convergence could only be shown on-sequence; the off-sequence behavior is unclear. In probabilistic environments, neither the posterior nor the losses converge, in general.
Compositional competitiveness for distributed algorithms
Venue: arXiv cs.DS 2003
Year: 2003

We define a measure of competitive performance for distributed algorithms based on throughput, the number of tasks that an algorithm can carry out in a fixed amount of work. This new measure complements the latency measure of Ajtai et al., which measures how quickly an algorithm can finish tasks that start at specified times. The novel feature of the throughput measure, which distinguishes it from the latency measure, is that it is compositional: it supports a notion of algorithms that are competitive relative to a class of subroutines, with the property that an algorithm that is k-competitive relative to a class of subroutines, combined with an l-competitive member of that class, gives a combined algorithm that is kl-competitive. In particular, we prove the throughput-competitiveness of a class of algorithms for collect operations, in which each of a group of n processes obtains all values stored in an array of n registers. Collects are a fundamental building block of a wide variety of shared-memory distributed algorithms, and we show that several such algorithms are competitive relative to collects. Inserting a competitive collect in these algorithms gives the first examples of competitive distributed algorithms obtained by composition using a general construction.
A data Grid testbed environment in Gigabit WAN with HPSS
Venue: arXiv cs.DC 2003
Year: 2003

For data analysis of large-scale experiments such as LHC Atlas and other Japanese high energy and nuclear physics projects, we have constructed a Grid test bed at ICEPP and KEK. These institutes are connected to national scientific gigabit network backbone called SuperSINET. In our test bed, we have installed NorduGrid middleware based on Globus, and connected 120TB HPSS at KEK as a large scale data store. Atlas simulation data at ICEPP has been transferred and accessed using SuperSINET. We have tested various performances and characteristics of HPSS through this high speed WAN. The measurement includes comparison between computing and storage resources are tightly coupled with low latency LAN and long distant WAN.
BlueOx: A Java Framework for Distributed Data Analysis
Venue: arXiv cs.DC 2003
Year: 2003

High energy physics experiments including those at the Tevatron and the upcoming LHC require analysis of large data sets which are best handled by distributed computation. We present the design and development of a distributed data analysis framework based on Java. Analysis jobs run through three phases: discovery of data sets available, brokering/assignment of data sets to analysis servers, and job execution. Each phase is represented by a set of abstract interfaces. These interfaces allow different techniques to be used without modification to the framework. For example, the communications interface has been implemented by both a packet protocol and a SOAP-based scheme. User authentication can be provided either through simple passwords or through a GSI certificates system. Data from CMS HCAL Testbeams, the L3 LEP experiment, and a hypothetical high-energy linear collider experiment have been interfaced with the framework.
Operational Aspects of Dealing with the Large BaBar Data Set
Venue: arXiv cs.DB 2003
Year: 2003

To date, the BaBar experiment has stored over 0.7PB of data in an Objectivity/DB database. Approximately half this data-set comprises simulated data of which more than 70% has been produced at more than 20 collaborating institutes outside of SLAC. The operational aspects of managing such a large data set and providing access to the physicists in a timely manner is a challenging and complex problem. We describe the operational aspects of managing such a large distributed data-set as well as importing and exporting data from geographically spread BaBar collaborators. We also describe problems common to dealing with such large datasets.
Learning to Order Facts for Discourse Planning in Natural Language Generation
Venue: arXiv cs.CL 2003
Year: 2003

This paper presents a machine learning approach to discourse planning in natural language generation. More specifically, we address the problem of learning the most natural ordering of facts in discourse plans for a specific domain. We discuss our methodology and how it was instantiated using two different machine learning algorithms. A quantitative evaluation performed in the domain of museum exhibit descriptions indicates that our approach performs significantly better than manually constructed ordering rules. Being retrainable, the resulting planners can be ported easily to other similar domains, without requiring language technology expertise.
POOL File Catalog, Collection and Metadata Components
Venue: arXiv cs.DB 2003
Year: 2003

The POOL project is the common persistency framework for the LHC experiments to store petabytes of experiment data and metadata in a distributed and grid enabled way. POOL is a hybrid event store consisting of a data streaming layer and a relational layer. This paper describes the design of file catalog, collection and metadata components which are not part of the data streaming layer of POOL and outlines how POOL aims to provide transparent and efficient data access for a wide range of environments and use cases - ranging from a large production site down to a single disconnected laptops. The file catalog is the central POOL component translating logical data references to physical data files in a grid environment. POOL collections with their associated metadata provide an abstract way of accessing experiment data via their logical grouping into sets of related data objects.
The AliEn system, status and perspectives
Venue: arXiv cs.DC 2003
Year: 2003

AliEn is a production environment that implements several components of the Grid paradigm needed to simulate, reconstruct and analyse HEP data in a distributed way. The system is built around Open Source components, uses the Web Services model and standard network protocols to implement the computing platform that is currently being used to produce and analyse Monte Carlo data at over 30 sites on four continents. The aim of this paper is to present the current AliEn architecture and outline its future developments in the light of emerging standards.