title: The CMS Integration Grid Testbed

abstract: The CMS Integration Grid Testbed (IGT) comprises USCMS Tier-1 and Tier-2 hardware at the following sites: the California Institute of Technology, Fermi National Accelerator Laboratory, the University of California at San Diego, and the University of Florida at Gainesville. The IGT runs jobs using the Globus Toolkit with a DAGMan and Condor-G front end. The virtual organization (VO) is managed using VO management scripts from the European Data Grid (EDG). Gridwide monitoring is accomplished using local tools such as Ganglia interfaced into the Globus Metadata Directory Service (MDS) and the agent based Mona Lisa. Domain specific software is packaged and installed using the Distrib ution After Release (DAR) tool of CMS, while middleware under the auspices of the Virtual Data Toolkit (VDT) is distributed using Pacman. During a continuo us two month span in Fall of 2002, over 1 million official CMS GEANT based Monte Carlo events were generated and returned to CERN for analysis while being demonstrated at SC2002. In this paper, we describe the process that led to one of the world's first continuously available, functioning grids.


title: Clarens Client and Server Applications

abstract: Several applications have been implemented with access via the Clarens web service infrastructure, including virtual organization management, JetMET physics data analysis using relational databases, and Storage Resource Broker (SRB) access. This functionality is accessible transparently from Python scripts, the Root analysis framework and from Java applications and browser applets.


title: The Clarens web services architecture

abstract: Clarens is a uniquely flexible web services infrastructure providing a unified access protocol to a diverse set of functions useful to the HEP community. It uses the standard HTTP protocol combined with application layer, certificate based authentication to provide single sign-on to individuals, organizations and hosts, with fine-grained access control to services, files and virtual organization (VO) management. This contribution describes the server functionality, while client applications are described in a subsequent talk.


title: R-GMA: First results after deployment

abstract: We describe R-GMA (Relational Grid Monitoring Architecture) which is being developed within the European DataGrid Project as an 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 VO 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 to do the job. We are able to invoke MDS info-provider scripts and publish the resulting information via R-GMA in addition to having some of our own sensors. APIs are available which allow the user to deploy monitoring and information services for any application that may be needed in the future. We have used it both for information about the grid (primarily to find what services are available at any one time) and for application monitoring. R-GMA has been deployed in Grid testbeds, we describe the results and experiences of this deployment.


title: Managing Dynamic User Communities in a Grid of Autonomous Resources

abstract: One of the fundamental concepts in Grid computing is the creation of Virtual Organizations (VO's): a set of resource consumers and providers that join forces to solve a common problem. Typical examples of Virtual Organizations include collaborations formed around the Large Hadron Collider (LHC) experiments. To date, Grid computing has been applied on a relatively small scale, linking dozens of users to a dozen resources, and management of these VO's was a largely manual operation. With the advance of large collaboration, linking more than 10000 users with a 1000 sites in 150 counties, a comprehensive, automated management system is required. It should be simple enough not to deter users, while at the same time ensuring local site autonomy. The VO Management Service (VOMS), developed by the EU DataGrid and DataTAG projects[1, 2], is a secured system for managing authorization for users and resources in virtual organizations. It extends the existing Grid Security Infrastructure[3] architecture with embedded VO affiliation assertions that can be independently verified by all VO members and resource providers. Within the EU DataGrid project, Grid services for job submission, file- and database access are being equipped with fine- grained authorization systems that take VO membership into account. These also give resource owners the ability to ensure site security and enforce local access policies. This paper will describe the EU DataGrid security architecture, the VO membership service and the local site enforcement mechanisms Local Centre Authorization Service (LCAS), Local Credential Mapping Service(LCMAPS) and the Java Trust and Authorization Manager.


title: The Virtual Monte Carlo

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


title: Experience with the Open Source based implementation for ATLAS Conditions Data Management System

abstract: Conditions Data in high energy physics experiments is frequently seen as every data needed for reconstruction besides the event data itself. This includes all sorts of slowly evolving data like detector alignment, calibration and robustness, and data from detector control system. Also, every Conditions Data Object is associated with a time interval of validity and a version. Besides that, quite often is useful to tag collections of Conditions Data Objects altogether. These issues have already been investigated and a data model has been proposed and used for different implementations based in commercial DBMSs, both at CERN and for the BaBar experiment. The special case of the ATLAS complex trigger that requires online access to calibration and alignment data poses new challenges that have to be met using a flexible and customizable solution more in the line of Open Source components. Motivated by the ATLAS challenges we have developed an alternative implementation, based in an Open Source RDBMS. Several issues were investigated land will be described in this paper: -The best way to map the conditions data model into the relational database concept considering what are foreseen as the most frequent queries. -The clustering model best suited to address the scalability problem. -Extensive tests were performed and will be described. The very promising results from these tests are attracting the attention from the HEP community and driving further developments.


title: The first deployment of workload management services on the EU DataGrid Testbed: feedback on design and implementation

abstract: Application users have now been experiencing for about a year with the standardized resource brokering services provided by the 'workload management' package of the EU DataGrid project (WP1). Understanding, shaping and pushing the limits of the system has provided valuable feedback on both its design and implementation. A digest of the lessons, and "better practices", that were learned, and that were applied towards the second major release of the software, is given.


title: The new BaBar Data Reconstruction Control System

abstract: The BaBar experiment is characterized by extremely high luminosity, a complex detector, and a huge data volume, with increasing requirements each year. To fulfill these requirements a new control system has been designed and developed for the offline data reconstruction system. The new control system described in this paper provides the performance and flexibility needed to manage a large number of small computing farms, and takes full benefit of OO design. The infrastructure is well isolated from the processing layer, it is generic and flexible, based on a light framework providing message passing and cooperative multitasking. The system is actively distributed, enforces the separation between different processing tiers by using different naming domains, and glues them together by dedicated brokers. It provides a powerful Finite State Machine framework to describe custom processing models in a simple regular language. This paper describes this new control system, currently in use at SLAC and Padova on ~450 CPUs organized in 12 farms.


title: Virtual Data in CMS Production

abstract: Initial applications of the GriPhyN Chimera Virtual Data System have been performed within the context of CMS Production of Monte Carlo Simulated Data. The GriPhyN Chimera system consists of four primary components: 1) a Virtual Data Language, which is used to describe virtual data products, 2) a Virtual Data Catalog, which is used to store virtual data entries, 3) an Abstract Planner, which resolves all dependencies of a particular virtual data product and forms a location and existence independent plan, 4) a Concrete Planner, which maps an abstract, logical plan onto concrete, physical grid resources accounting for staging in/out files and publishing results to a replica location service. A CMS Workflow Planner, MCRunJob, is used to generate virtual data products using the Virtual Data Language. Subsequently, a prototype workflow manager, known as WorkRunner, is used to schedule the instantiation of virtual data products across a grid.


title: On multiple connectedness of regions visible due to multiple diffuse reflections

abstract: It is known that the region $V(s)$ of a simple polygon $P$, directly visible (illuminable) from an internal point $s$, is simply connected. Aronov et al. \cite{addpp981} established that the region $V_1(s)$ of a simple polygon visible from an internal point $s$ due to at most one diffuse reflection on the boundary of the polygon $P$, is also simply connected. In this paper we establish that the region $V_2(s)$, visible from $s$ due to at most two diffuse reflections may be multiply connected; we demonstrate the construction of an $n$-sided simple polygon with a point $s$ inside it so that and the region of $P$ visible from $s$ after at most two diffuse reflections is multiple connected.


title: Grid Data Management in Action: Experience in Running and Supporting Data Management Services in the EU DataGrid Project

abstract: In the first phase of the EU DataGrid (EDG) project, a Data Management System has been implemented and provided for deployment. The components of the current EDG Testbed are: a prototype of a Replica Manager Service built around the basic services provided by Globus, a centralised Replica Catalogue to store information about physical locations of files, and the Grid Data Mirroring Package (GDMP) that is widely used in various HEP collaborations in Europe and the US for data mirroring. During this year these services have been refined and made more robust so that they are fit to be used in a pre-production environment. Application users have been using this first release of the Data Management Services for more than a year. In the paper we present the components and their interaction, our implementation and experience as well as the feedback received from our user communities. We have resolved not only issues regarding integration with other EDG service components but also many of the interoperability issues with components of our partner projects in Europe and the U.S. The paper concludes with the basic lessons learned during this operation. These conclusions provide the motivation for the architecture of the next generation of Data Management Services that will be deployed in EDG during 2003.


title: GraXML - Modular Geometric Modeler

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


title: Transparent Persistence with Java Data Objects

abstract: Flexible and performant Persistency Service is a necessary component of any HEP Software Framework. The building of a modular, non-intrusive and performant persistency component have been shown to be very difficult task. In the past, it was very often necessary to sacrifice modularity to achieve acceptable performance. This resulted in the strong dependency of the overall Frameworks on their Persistency subsystems. Recent development in software technology has made possible to build a Persistency Service which can be transparently used from other Frameworks. Such Service doesn't force a strong architectural constraints on the overall Framework Architecture, while satisfying high performance requirements. Java Data Object standard (JDO) has been already implemented for almost all major databases. It provides truly transparent persistency for any Java object (both internal and external). Objects in other languages can be handled via transparent proxies. Being only a thin layer on top of a used database, JDO doesn't introduce any significant performance degradation. Also Aspect-Oriented Programming (AOP) makes possible to treat persistency as an orthogonal Aspect of the Application Framework, without polluting it with persistence-specific concepts. 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++. Fully functional prototypes of flexible and non-intrusive persistency modules have been build for several other packages, as for example FreeHEP AIDA and LCG Pool AttributeSet (package Indicium).


title: SCRAM: Software configuration and management for the LHC Computing Grid project

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


title: Computing sharp and scalable bounds on errors in approximate zeros of univariate polynomials

abstract: There are several numerical methods for computing approximate zeros of a given univariate polynomial. In this paper, we develop a simple and novel method for determining sharp upper bounds on errors in approximate zeros of a given polynomial using Rouche's theorem from complex analysis. We compute the error bounds using non-linear optimization. Our bounds are scalable in the sense that we compute sharper error bounds for better approximations of zeros. We use high precision computations using the LEDA/real floating-point filter for computing our bounds robustly.


title: Modelling Biochemical Operations on RNA Secondary Structures

abstract: 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\ss e-Rhode's Algebra Transformation Systems.


title: Minimum Model Semantics for Logic Programs with Negation-as-Failure

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


title: A monitoring tool for a GRID operation center

abstract: WorldGRID is an intercontinental testbed spanning Europe and the US integrating architecturally different Grid implementations based on the Globus toolkit. The WorldGRID testbed has been successfully demonstrated during the WorldGRID demos at SuperComputing 2002 (Baltimore) and IST2002 (Copenhagen) where real HEP application jobs were transparently submitted from US and Europe using "native" mechanisms and run where resources were available, independently of their location. To monitor the behavior and performance of such testbed and spot problems as soon as they arise, DataTAG has developed the EDT-Monitor tool based on the Nagios package that allows for Virtual Organization centric views of the Grid through dynamic geographical maps. The tool has been used to spot several problems during the WorldGRID operations, such as malfunctioning Resource Brokers or Information Servers, sites not correctly configured, job dispatching problems, etc. In this paper we give an overview of the package, its features and scalability solutions and we report on the experience acquired and the benefit that a GRID operation center would gain from such a tool.


title: Relational databases for data management in PHENIX

abstract: PHENIX is one of the two large experiments at the Relativistic Heavy Ion Collider (RHIC) at Brookhaven National Laboratory (BNL) and archives roughly 100TB of experimental data per year. In addition, large volumes of simulated data are produced at multiple off-site computing centers. For any file catalog to play a central role in data management it has to face problems associated with the need for distributed access and updates. To be used effectively by the hundreds of PHENIX collaborators in 12 countries the catalog must satisfy the following requirements: 1) contain up-to-date data, 2) provide fast and reliable access to the data, 3) have write permissions for the sites that store portions of data. We present an analysis of several available Relational Database Management Systems (RDBMS) to support a catalog meeting the above requirements and discuss the PHENIX experience with building and using the distributed file catalog.


title: On the Verge of One Petabyte - the Story Behind the BaBar Database System

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


title: Visualization for Periodic Population Movement between Distinct Localities

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


title: Techniques for effective vocabulary selection

abstract: The vocabulary of a continuous speech recognition (CSR) system is a significant factor in determining its performance. In this paper, we present three principled approaches to select the target vocabulary for a particular domain by trading off between the target out-of-vocabulary (OOV) rate and vocabulary size. We evaluate these approaches against an ad-hoc baseline strategy. Results are presented in the form of OOV rate graphs plotted against increasing vocabulary size for each technique.


title: The Redesigned BaBar Event Store: Believe the Hype

abstract: As the BaBar experiment progresses, it produces new and unforeseen requirements and increasing demands on capacity and feature base. The current system is being utilized well beyond its original design specifications, and has scaled appropriately, maintaining data consistency and durability. The persistent event storage system has remained largely unchanged since the initial implementation, and thus includes many design features which have become performance bottlenecks. Programming interfaces were designed before sufficient usage information became available. Performance and efficiency were traded off for added flexibility to cope with future demands. With significant experience in managing actual production data under our belt, we are now in a position to recraft the system to better suit current needs. The Event Store redesign is intended to eliminate redundant features while adding new ones, increase overall performance, and contain the physical storage cost of the world's largest database.


title: Monitoring Systems and Services

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


title: Permutation Generation: Two New Permutation Algorithms

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


title: BdbServer++: A User Driven Data Location and Retrieval Tool

abstract: The adoption of Grid technology has the potential to greatly aid the BaBar experiment. BdbServer was originally designed to extract copies of data from the Objectivity/DB database at SLAC and IN2P3. With data now stored in multiple locations in a variety of data formats, we are enhancing this tool. This will enable users to extract selected deep copies of event collections and ship them to the requested site using the facilities offered by the existing Grid infrastructure. By building on the work done by various groups in BaBar, and the European DataGrid, we have successfully expanded the capabilities of the BdbServer software. This should provide a framework for future work in data distribution.


title: HEP Applications Evaluation of the EDG Testbed and Middleware

abstract: Workpackage 8 of the European Datagrid project was formed in January 2001 with representatives from the four LHC experiments, and with experiment independent people from five of the six main EDG partners. In September 2002 WP8 was strengthened by the addition of effort from BaBar and D0. The original mandate of WP8 was, following the definition of short- and long-term requirements, to port experiment software to the EDG middleware and testbed environment. A major additional activity has been testing the basic functionality and performance of this environment. This paper reviews experiences and evaluations in the areas of job submission, data management, mass storage handling, information systems and monitoring. It also comments on the problems of remote debugging, the portability of code, and scaling problems with increasing numbers of jobs, sites and nodes. Reference is made to the pioneeering work of Atlas and CMS in integrating the use of the EDG Testbed into their data challenges. A forward look is made to essential software developments within EDG and to the necessary cooperation between EDG and LCG for the LCG prototype due in mid 2003.


title: An Abstract Programming System

abstract: The system PL permits the translation of abstract proofs of program correctness into programs in a variety of programming languages. A programming language satisfying certain axioms may be the target of such a translation. The system PL also permits the construction and proof of correctness of programs in an abstract programming language, and permits the translation of these programs into correct programs in a variety of languages. The abstract programming language has an imperative style of programming with assignment statements and side-effects, to allow the efficient generation of code. The abstract programs may be written by humans and then translated, avoiding the need to write the same program repeatedly in different languages or even the same language. This system uses classical logic, is conceptually simple, and permits reasoning about nonterminating programs using Scott-Strachey style denotational semantics.


title: A Software Data Transport Framework for Trigger Applications on Clusters

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


title: Grid-based access control for Unix environments, Filesystems and Web Sites

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


title: The FRED Event Display: an Extensible HepRep Client for GLAST

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


title: Length-Based Attacks for Certain Group Based Encryption Rewriting Systems

abstract: In this note, we describe a probabilistic attack on public key cryptosystems based on the word/conjugacy problems for finitely presented groups of the type proposed recently by Anshel, Anshel and Goldfeld. In such a scheme, one makes use of the property that in the given group the word problem has a polynomial time solution, while the conjugacy problem has no known polynomial solution. An example is the braid group from topology in which the word problem is solvable in polynomial time while the only known solutions to the conjugacy problem are exponential. The attack in this paper is based on having a canonical representative of each string relative to which a length function may be computed. Hence the term length attack. Such canonical representatives are known to exist for the braid group.


title: Multi-valued Connectives for Fuzzy Sets

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


title: A ROOT/IO Based Software Framework for CMS

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


title: A Transformational Decision Procedure for Non-Clausal Propositional Formulas

abstract: A decision procedure for detecting valid propositional formulas is presented. It is based on the Davis-Putnam method and deals with propositional formulas that are initially converted to negational normal form. This procedure splits variables but, in contrast to other decision procedures based on the Davis-Putnam method, it does not branch. Instead, this procedure iteratively makes validity-preserving transformations of fragments of the formula. The transformations involve only a minimal formula part containing occurrences of the selected variable. Selection of the best variable for splitting is crucial in this decision procedure - it may shorten the decision process dramatically. A variable whose splitting leads to a minimal size of the transformed formula is selected. Also, the decision procedure performs plenty of optimizations based on calculation of delta-sets. Some optimizations lead to removing fragments of the formula. Others detect variables for which a single truth value assignment is sufficient. The latest information about this research can be found at http://www.sakharov.net/valid.html


title: Sequence Prediction based on Monotone Complexity

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

categories: cs.AI cs.IT cs.LG math.IT math.ST stat.TH


title: Flow-based analysis of Internet traffic

abstract: We propose flow-based analysis to estimate quality of an Internet connection. Using results from the queuing theory we compare two expressions for backbone traffic that have different scopes of applicability. A curve that shows dependence of utilization of a link on a number of active flows in it describes different states of the network. We propose a methodology for plotting such a curve using data received from a Cisco router by NetFlow protocol, determining the working area and the overloading point of the network. Our test is an easy way to find a moment for upgrading the backbone.


title: Quanta: a Language for Modeling and Manipulating Information Structures

abstract: We present a theory for modeling the structure of information and a language (Quanta) expressing the theory. Unlike Shannon's information theory, which focuses on the amount of information in an information system, we focus on the structure of the information in the system. For example, we can model the information structure corresponding to an algorithm or a physical process such as the structure of a quantum interaction. After a brief discussion of the relation between an evolving state-system and an information structure, we develop an algebra of information pieces (infons) to represent the structure of systems where descriptions of complex systems are constructed from expressions involving descriptions of simpler information systems. We map the theory to the Von Neumann computing model of sequences/conditionals/repetitions, and to the class/object theory of object-oriented programming (OOP).


title: Bayesian Information Extraction Network

abstract: Dynamic Bayesian networks (DBNs) offer an elegant way to integrate various aspects of language in one model. Many existing algorithms developed for learning and inference in DBNs are applicable to probabilistic language modeling. To demonstrate the potential of DBNs for natural language processing, we employ a DBN in an information extraction task. We show how to assemble wealth of emerging linguistic instruments for shallow parsing, syntactic and semantic tagging, morphological decomposition, named entity recognition etc. in order to incrementally build a robust information extraction system. Our method outperforms previously published results on an established benchmark domain.


title: The Open Language Archives Community: An infrastructure for distributed archiving of language resources

abstract: New ways of documenting and describing language via electronic media coupled with new ways of distributing the results via the World-Wide Web offer a degree of access to language resources that is unparalleled in history. At the same time, the proliferation of approaches to using these new technologies is causing serious problems relating to resource discovery and resource creation. This article describes the infrastructure that the Open Language Archives Community (OLAC) has built in order to address these problems. Its technical and usage infrastructures address problems of resource discovery by constructing a single virtual library of distributed resources. Its governance infrastructure addresses problems of resource creation by providing a mechanism through which the language-resource community can express its consensus on recommended best practices.


title: Monodic temporal resolution

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


title: IGUANA Architecture, Framework and Toolkit for Interactive Graphics

abstract: IGUANA is a generic interactive visualisation framework based on a C++ component model. It provides powerful user interface and visualisation primitives in a way that is not tied to any particular physics experiment or detector design. The article describes interactive visualisation tools built using IGUANA for the CMS and D0 experiments, as well as generic GEANT4 and GEANT3 applications. It covers features of the graphical user interfaces, 3D and 2D graphics, high-quality vector graphics output for print media, various textual, tabular and hierarchical data views, and integration with the application through control panels, a command line and different multi-threading models.


title: Skip Graphs

abstract: Skip graphs are a novel distributed data structure, based on skip lists, that provide the full functionality of a balanced tree in a distributed system where resources are stored in separate nodes that may fail at any time. They are designed for use in searching peer-to-peer systems, and by providing the ability to perform queries based on key ordering, they improve on existing search tools that provide only hash table functionality. Unlike skip lists or other tree data structures, skip graphs are highly resilient, tolerating a large fraction of failed nodes without losing connectivity. In addition, constructing, inserting new nodes into, searching a skip graph, and detecting and repairing errors in the data structure introduced by node failures can be done using simple and straightforward algorithms.


title: Compositional competitiveness for distributed algorithms

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


title: The WorldGrid transatlantic testbed: a successful example of Grid interoperability across EU and U.S. domains

abstract: The European DataTAG project has taken a major step towards making the concept of a worldwide computing Grid a reality. In collaboration with the companion U.S. project iVDGL, DataTAG has realized an intercontinental testbed spanning Europe and the U.S. integrating architecturally different Grid implementations based on the Globus toolkit. The WorldGrid testbed has been successfully demonstrated at SuperComputing 2002 and IST2002 where real HEP application jobs were transparently submitted from U.S. and Europe using native mechanisms and run where resources were available, independently of their location. In this paper we describe the architecture of the WorldGrid testbed, the problems encountered and the solutions taken in realizing such a testbed. With our work we present an important step towards interoperability of Grid middleware developed and deployed in Europe and the U.S.. Some of the solutions developed in WorldGrid will be adopted by the LHC Computing Grid first service. To the best of our knowledge, this is the first large-scale testbed that combines middleware components and makes them work together.


title: Compact Approximation of Lattice Functions with Applications to Large-Alphabet Text Search

abstract: We propose a very simple randomised data structure that stores an approximation from above of a lattice-valued function. Computing the function value requires a constant number of steps, and the error probability can be balanced with space usage, much like in Bloom filters. The structure is particularly well suited for functions that are bottom on most of their domain. We then show how to use our methods to store in a compact way the bad-character shift function for variants of the Boyer-Moore text search algorithms. As a result, we obtain practical implementations of these algorithms that can be used with large alphabets, such as Unicode collation elements, with a small setup time. The ideas described in this paper have been implemented as free software under the GNU General Public License within the MG4J project (http://mg4j.dsi.unimi.it/).


title: Concrete uses of XML in software development and data analysis

abstract: XML is now becoming an industry standard for data description and exchange. Despite this there are still some questions about how or if this technology can be useful in High Energy Physics software development and data analysis. This paper aims to answer these questions by demonstrating how XML is used in the IceCube software development system, data handling and analysis. It does this by first surveying the concepts and tools that make up the XML technology. It then goes on to discuss concrete examples of how these concepts and tools are used to speed up software development in IceCube and what are the benefits of using XML in IceCube's data handling and analysis chain. The overall aim of this paper it to show that XML does have many benefits to bring High Energy Physics software development and data analysis.


title: Parallel netCDF: A Scientific High-Performance I/O Interface

abstract: Dataset storage, exchange, and access play a critical role in scientific applications. For such purposes netCDF serves as a portable and efficient file format and programming interface, which is popular in numerous scientific application domains. However, the original interface does not provide an efficient mechanism for parallel data storage and access. In this work, we present a new parallel interface for writing and reading netCDF datasets. This interface is derived with minimum changes from the serial netCDF interface but defines semantics for parallel access and is tailored for high performance. The underlying parallel I/O is achieved through MPI-IO, allowing for dramatic performance gains through the use of collective I/O optimizations. We compare the implementation strategies with HDF5 and analyze both. Our tests indicate programming convenience and significant I/O performance improvement with this parallel netCDF interface.


title: Hyperdense Coding Modulo 6 with Filter-Machines

abstract: We show how one can encode $n$ bits with $n^{o(1)}$ ``wave-bits'' using still hypothetical filter-machines (here $o(1)$ denotes a positive quantity which goes to 0 as $n$ goes to infity). Our present result - in a completely different computational model - significantly improves on the quantum superdense-coding breakthrough of Bennet and Wiesner (1992) which encoded $n$ bits by $\lceil{n/2}\rceil$ quantum-bits. We also show that our earlier algorithm (Tech. Rep. TR03-001, ECCC, See ftp://ftp.eccc.uni-trier.de/pub/eccc/reports/2003/TR03-001/index.html) which used $n^{o(1)}$ muliplication for computing a representation of the dot-product of two $n$-bit sequences modulo 6, and, similarly, an algorithm for computing a representation of the multiplication of two $n\times n$ matrices with $n^{2+o(1)}$ multiplications can be turned to algorithms computing the exact dot-product or the exact matrix-product with the same number of multiplications with filter-machines. With classical computation, computing the dot-product needs $\Omega(n)$ multiplications and the best known algorithm for matrix multiplication (D. Coppersmith and S. Winograd, Matrix multiplication via arithmetic progressions, J. Symbolic Comput., 9(3):251--280, 1990) uses $n^{2.376}$ multiplications.


title: Introduction to the CoNLL-2003 Shared Task: Language-Independent Named Entity Recognition

abstract: We describe the CoNLL-2003 shared task: language-independent named entity recognition. We give background information on the data sets (English and German) and the evaluation method, present a general overview of the systems that have taken part in the task and discuss their performance.


title: A data Grid testbed environment in Gigabit WAN with HPSS

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


title: ATLAS Data Challenge 1

abstract: In 2002 the ATLAS experiment started a series of Data Challenges (DC) of which the goals are the validation of the Computing Model, of the complete software suite, of the data model, and to ensure the correctness of the technical choices to be made. A major feature of the first Data Challenge (DC1) was the preparation and the deployment of the software required for the production of large event samples for the High Level Trigger (HLT) and physics communities, and the production of those samples as a world-wide distributed activity. The first phase of DC1 was run during summer 2002, and involved 39 institutes in 18 countries. More than 10 million physics events and 30 million single particle events were fully simulated. Over a period of about 40 calendar days 71000 CPU-days were used producing 30 Tbytes of data in about 35000 partitions. In the second phase the next processing step was performed with the participation of 56 institutes in 21 countries (~ 4000 processors used in parallel). The basic elements of the ATLAS Monte Carlo production system are described. We also present how the software suite was validated and the participating sites were certified. These productions were already partly performed by using different flavours of Grid middleware at ~ 20 sites.


title: A Community Authorization Service for Group Collaboration

abstract: In "Grids" and "collaboratories," we find distributed communities of resource providers and resource consumers, within which often complex and dynamic policies govern who can use which resources for which purpose. We propose a new approach to the representation, maintenance, and enforcement of such policies that provides a scalable mechanism for specifying and enforcing these policies. Our approach allows resource providers to delegate some of the authority for maintaining fine-grained access control policies to communities, while still maintaining ultimate control over their resources. We also describe a prototype implementation of this approach and an application in a data management context.


title: OVAL: the CMS Testing Robot

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


title: BlueOx: A Java Framework for Distributed Data Analysis

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


title: Twelve Ways to Build CMS Crossings from ROOT Files

abstract: The simulation of CMS raw data requires the random selection of one hundred and fifty pileup events from a very large set of files, to be superimposed in memory to the signal event. The use of ROOT I/O for that purpose is quite unusual: the events are not read sequentially but pseudo-randomly, they are not processed one by one in memory but by bunches, and they do not contain orthodox ROOT objects but many foreign objects and templates. In this context, we have compared the performance of ROOT containers versus the STL vectors, and the use of trees versus a direct storage of containers. The strategy with best performances is by far the one using clones within trees, but it stays hard to tune and very dependant on the exact use-case. The use of STL vectors could bring more easily similar performances in a future ROOT release.


title: IceCube's Development Environment

abstract: When the IceCube experiment started serious software development it needed a development environment in which both its developers and clients could work and that would encourage and support a good software development process. Some of the key features that IceCube wanted in such a environment were: the separation of the configuration and build tools; inclusion of an issue tracking system; support for the Unified Change Model; support for unit testing; and support for continuous building. No single, affordable, off the shelf, environment offered all these features. However there are many open source tools that address subsets of these feature, therefore IceCube set about selecting those tools which it could use in developing its own environment and adding its own tools where no suitable tools were found. This paper outlines the tools that where chosen, what are their responsibilities in the development environment and how they fit together. The complete environment will be demonstrated with a walk through of single cycle of the development process.


title: Installing, Running and Maintaining Large Linux Clusters at CERN

abstract: Having built up Linux clusters to more than 1000 nodes over the past five years, we already have practical experience confronting some of the LHC scale computing challenges: scalability, automation, hardware diversity, security, and rolling OS upgrades. This paper describes the tools and processes we have implemented, working in close collaboration with the EDG project [1], especially with the WP4 subtask, to improve the manageability of our clusters, in particular in the areas of system installation, configuration, and monitoring. In addition to the purely technical issues, providing shared interactive and batch services which can adapt to meet the diverse and changing requirements of our users is a significant challenge. We describe the developments and tuning that we have introduced on our LSF based systems to maximise both responsiveness to users and overall system utilisation. Finally, this paper will describe the problems we are facing in enlarging our heterogeneous Linux clusters, the progress we have made in dealing with the current issues and the steps we are taking to gridify the clusters


title: The Use of HepRep in GLAST

abstract: HepRep is a generic, hierarchical format for description of graphics representables that can be augmented by physics information and relational properties. It was developed for high energy physics event display applications and is especially suited to client/server or component frameworks. The GLAST experiment, an international effort led by NASA for a gamma-ray telescope to launch in 2006, chose HepRep to provide a flexible, extensible and maintainable framework for their event display without tying their users to any one graphics application. To support HepRep in their GUADI infrastructure, GLAST developed a HepRep filler and builder architecture. The architecture hides the details of XML and CORBA in a set of base and helper classes allowing physics experts to focus on what data they want to represent. GLAST has two GAUDI services: HepRepSvc, which registers HepRep fillers in a global registry and allows the HepRep to be exported to XML, and CorbaSvc, which allows the HepRep to be published through a CORBA interface and which allows the client application to feed commands back to GAUDI (such as start next event, or run some GAUDI algorithm). GLAST's HepRep solution gives users a choice of client applications, WIRED (written in Java) or FRED (written in C++ and Ruby), and leaves them free to move to any future HepRep-compliant event display.


title: DIRAC - Distributed Infrastructure with Remote Agent Control

abstract: This paper describes DIRAC, the LHCb Monte Carlo production system. DIRAC has a client/server architecture based on: Compute elements distributed among the collaborating institutes; Databases for production management, bookkeeping (the metadata catalogue) and software configuration; Monitoring and cataloguing services for updating and accessing the databases. Locally installed software agents implemented in Python monitor the local batch queue, interrogate the production database for any outstanding production requests using the XML-RPC protocol and initiate the job submission. The agent checks and, if necessary, installs any required software automatically. After the job has processed the events, the agent transfers the output data and updates the metadata catalogue. DIRAC has been successfully installed at 18 collaborating institutes, including the DataGRID, and has been used in recent Physics Data Challenges. In the near to medium term future we must use a mixed environment with different types of grid middleware or no middleware. We describe how this flexibility has been achieved and how ubiquitously available grid middleware would improve DIRAC.


title: Operational Aspects of Dealing with the Large BaBar Data Set

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


title: Learning to Order Facts for Discourse Planning in Natural Language Generation

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


title: A Model for Grid User Management

abstract: Registration and management of users in a large scale Grid computing environment presents new challenges that are not well addressed by existing protocols. Within a single Virtual Organization (VO), thousands of users will potentially need access to hundreds of computing sites, and the traditional model where users register for local accounts at each site will present significant scaling problems. However, computing sites must maintain control over access to the site and site policies generally require individual local accounts for every user. We present here a model that allows users to register once with a VO and yet still provides all of the computing sites the information they require with the required level of trust. We have developed tools to allow sites to automate the management of local accounts and the mappings between Grid identities and local accounts.


title: Exploiting peer group concept for adaptive and highly available services

abstract: This paper presents a prototype for redundant, highly available and fault tolerant peer to peer framework for data management. Peer to peer computing is gaining importance due to its flexible organization, lack of central authority, distribution of functionality to participating nodes and ability to utilize unused computational resources. Emergence of GRID computing has provided much needed infrastructure and administrative domain for peer to peer computing. The components of this framework exploit peer group concept to scope service and information search, arrange services and information in a coherent manner, provide selective redundancy and ensure availability in face of failure and high load conditions. A prototype system has been implemented using JXTA peer to peer technology and XML is used for service description and interfaces, allowing peers to communicate with services implemented in various platforms including web services and JINI services. It utilizes code mobility to achieve role interchange among services and ensure dynamic group membership. Security is ensured by using Public Key Infrastructure (PKI) to implement group level security policies for membership and service access.


title: POOL File Catalog, Collection and Metadata Components

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


title: The COMPASS Event Store in 2002

abstract: COMPASS, the fixed-target experiment at CERN studying the structure of the nucleon and spectroscopy, collected over 260 TB during summer 2002 run. All these data, together with reconstructed events information, were put from the beginning in a database infrastructure based on Objectivity/DB and on the hierarchical storage manager CASTOR. The experience in the usage of the database is reviewed and the evolution of the system outlined.


title: The AliEn system, status and perspectives

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


title: AliEn Resource Brokers

abstract: AliEn (ALICE Environment) is a lightweight GRID framework developed by the Alice Collaboration. When the experiment starts running, it will collect data at a rate of approximately 2 PB per year, producing O(109) files per year. All these files, including all simulated events generated during the preparation phase of the experiment, must be accounted and reliably tracked in the GRID environment. The backbone of AliEn is a distributed file catalogue, which associates universal logical file name to physical file names for each dataset and provides transparent access to datasets independently of physical location. The file replication and transport is carried out under the control of the File Transport Broker. In addition, the file catalogue maintains information about every job running in the system. The jobs are distributed by the Job Resource Broker that is implemented using a simplified pull (as opposed to traditional push) architecture. This paper describes the Job and File Transport Resource Brokers and shows that a similar architecture can be applied to solve both problems.


title: Distributed Offline Data Reconstruction in BaBar

abstract: The BaBar experiment at SLAC is in its fourth year of running. The data processing system has been continuously evolving to meet the challenges of higher luminosity running and the increasing bulk of data to re-process each year. To meet these goals a two-pass processing architecture has been adopted, where 'rolling calibrations' are quickly calculated on a small fraction of the events in the first pass and the bulk data reconstruction done in the second. This allows for quick detector feedback in the first pass and allows for the parallelization of the second pass over two or more separate farms. This two-pass system allows also for distribution of processing farms off-site. The first such site has been setup at INFN Padova. The challenges met here were many. The software was ported to a full Linux-based, commodity hardware system. The raw dataset, 90 TB, was imported from SLAC utilizing a 155 Mbps network link. A system for quality control and export of the processed data back to SLAC was developed. Between SLAC and Padova we are currently running three pass-one farms, with 32 CPUs each, and nine pass-two farms with 64 to 80 CPUs each. The pass-two farms can process between 2 and 4 million events per day. Details about the implementation and performance of the system will be presented.


title: Fine-Grained Authorization for Job and Resource Management Using Akenti and the Globus Toolkit

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


title: AliEnFS - a Linux File System for the AliEn Grid Services

abstract: Among the services offered by the AliEn (ALICE Environment http://alien.cern.ch) Grid framework there is a virtual file catalogue to allow transparent access to distributed data-sets using various file transfer protocols. $alienfs$ (AliEn File System) integrates the AliEn file catalogue as a new file system type into the Linux kernel using LUFS, a hybrid user space file system framework (Open Source http://lufs.sourceforge.net). LUFS uses a special kernel interface level called VFS (Virtual File System Switch) to communicate via a generalised file system interface to the AliEn file system daemon. The AliEn framework is used for authentication, catalogue browsing, file registration and read/write transfer operations. A C++ API implements the generic file system operations. The goal of AliEnFS is to allow users easy interactive access to a worldwide distributed virtual file system using familiar shell commands (f.e. cp,ls,rm ...) The paper discusses general aspects of Grid File Systems, the AliEn implementation and present and future developments for the AliEn Grid File System.


title: The EU DataGrid Workload Management System: towards the second major release

abstract: In the first phase of the European DataGrid project, the 'workload management' package (WP1) implemented a working prototype, providing users with an environment allowing to define and submit jobs to the Grid, and able to find and use the ``best'' resources for these jobs. Application users have now been experiencing for about a year now with this first release of the workload management system. The experiences acquired, the feedback received by the user and the need to plug new components implementing new functionalities, triggered an update of the existing architecture. A description of this revised and complemented workload management system is given.


title: GridMonitor: Integration of Large Scale Facility Fabric Monitoring with Meta Data Service in Grid Environment

abstract: Grid computing consists of the coordinated use of large sets of diverse, geographically distributed resources for high performance computation. Effective monitoring of these computing resources is extremely important to allow efficient use on the Grid. The large number of heterogeneous computing entities available in Grids makes the task challenging. In this work, we describe a Grid monitoring system, called GridMonitor, that captures and makes available the most important information from a large computing facility. The Grid monitoring system consists of four tiers: local monitoring, archiving, publishing and harnessing. This architecture was applied on a large scale linux farm and network infrastructure. It can be used by many higher-level Grid services including scheduling services and resource brokering.


title: Understanding and Coping with Hardware and Software Failures in a Very Large Trigger Farm

abstract: When thousands of processors are involved in performing event filtering on a trigger farm, there is likely to be a large number of failures within the software and hardware systems. BTeV, a proton/antiproton collider experiment at Fermi National Accelerator Laboratory, has designed a trigger, which includes several thousand processors. If fault conditions are not given proper treatment, it is conceivable that this trigger system will experience failures at a high enough rate to have a negative impact on its effectiveness. The RTES (Real Time Embedded Systems) collaboration is a group of physicists, engineers, and computer scientists working to address the problem of reliability in large-scale clusters with real-time constraints such as this. Resulting infrastructure must be highly scalable, verifiable, extensible by users, and dynamically changeable.


title: Data Management for Physics Analysis in Phenix (BNL, RHIC)

abstract: Every year the PHENIX collaboration deals with increasing volume of data (now about 1/4 PB/year). Apparently the more data the more questions how to process all the data in most efficient way. In recent past many developments in HEP computing were dedicated to the production environment. Now we need more tools to help to obtain physics results from the analysis of distributed simulated and experimental data. Developments in Grid architectures gave many examples how distributed computing facilities can be organized to meet physics analysis needs. We feel that our main task in this area is to try to use already developed systems or system components in PHENIX environment. We are concentrating here on the followed problems: file/replica catalog which keep names of our files, data moving over WAN, job submission in multicluster environment. PHENIX is a running experiment and this fact narrowed our ability to test new software on the collaboration computer facilities. We are experimenting with system prototypes at State University of New York at Stony Brook (SUNYSB) where we run midrange computing cluster for physics analysis. The talk is dedicated to discuss some experience with Grid software and achieved results.


title: FAYE: A Java Implement of the Frame/Stream/Stop Analysis Model

abstract: FAYE, The Frame AnalYsis Executable, is a Java based implementation of the Frame/Stream/Stop model for analyzing data. Unlike traditional Event based analysis models, the Frame/Stream/Stop model has no preference as to which part of any data is to be analyzed, and an Event get as equal treatment as a change in the high voltage. This model means that FAYE is a suitable analysis framework for many different type of data analysis, such as detector trends or as a visualization core. During the design of FAYE the emphasis has been on clearly delineating each of the executable's responsibilities and on keeping their implementations as completely independent as possible. This leads to the large part of FAYE being a generic core which is experiment independent, and smaller section that customizes this core to an experiments own data structures. This customization can even be done in C++, using JNI, while the executable's control remains in Java. This paper reviews the Frame/Stream/Stop model and then looks at how FAYE has approached its implementation, with an emphasis on which responsibilities are handled by the generic core, and which parts an experiment must provide as part of the customization portion of the executable.


title: The TESLA Requirements Database

abstract: In preparation for the planned linear collider TESLA, DESY is designing the required buildings and facilities. The accelerator and infrastructure components have to be allocated to buildings, and their required areas for installation, operation and maintenance have to be determined. Interdisciplinary working groups specify the project from different viewpoints and need to develop a common vision as a precondition for an optimal solution. A commercial requirements database is used as a collaborative tool, enabling concurrent requirements specification by independent working groups. The requirements database ensures long term storage and availability of the emerging knowledge, and it offers a central platform for communication which is available for all project members. It is successfully operating since summer 2002 and has since then become an important tool for the design team.


title: ROOT Status and Future Developments

abstract: In this talk we will review the major additions and improvements made to the ROOT system in the last 18 months and present our plans for future developments. The additons and improvements range from modifications to the I/O sub-system to allow users to save and restore objects of classes that have not been instrumented by special ROOT macros, to the addition of a geometry package designed for building, browsing, tracking and visualizing detector geometries. Other improvements include enhancements to the quick analysis sub-system (TTree::Draw()), the addition of classes that allow inter-file object references (TRef, TRefArray), better support for templated and STL classes, amelioration of the Automatic Script Compiler and the incorporation of new fitting and mathematical tools. Efforts have also been made to increase the modularity of the ROOT system with the introduction of more abstract interfaces and the development of a plug-in manager. In the near future, we intend to continue the development of PROOF and its interfacing with GRID environments. We plan on providing an interface between Geant3, Geant4 and Fluka and the new geometry package. The ROOT GUI classes will finally be available on Windows and we plan to release a GUI inspector and builder. In the last year, ROOT has drawn the endorsement of additional experiments and institutions. It is now officially supported by CERN and used as key I/O component by the LCG project.


title: Integrated Information Management for TESLA

abstract: Next-generation projects in High Energy Physics will reach again a new dimension of complexity. Information management has to ensure an efficient and economic information flow within the collaborations, offering world-wide up-to-date information access to the collaborators as one condition for successful projects. DESY introduces several information systems in preparation for the planned linear collider TESLA: a Requirements Management System (RMS) is in production for the TESLA planning group, a Product Data Management System (PDMS) is in production since the beginning of 2002 and is supporting the cavity preparation and the general engineering of accelerator components. A pilot Asset Management System (AMS) is in production for supporting the management and maintenance of the technical infrastructure, and a Facility Management System (FMS) with a Geographic Information System (GIS) is currently being introduced to support civil engineering. Efforts have been started to integrate the systems with the goal that users can retrieve information through a single point of access. The paper gives an introduction to information management and the activities at DESY.


title: BOA: Framework for Automated Builds

abstract: Managing large-scale software products is a complex software engineering task. The automation of the software development, release and distribution process is most beneficial in the large collaborations, where the big number of developers, multiple platforms and distributed environment are typical factors. This paper describes Build and Output Analyzer framework and its components that have been developed in CMS to facilitate software maintenance and improve software quality. The system allows to generate, control and analyze various types of automated software builds and tests, such as regular rebuilds of the development code, software integration for releases and installation of the existing versions.


title: An on-line Integrated Bookkeeping: electronic run log book and Meta-Data Repository for ATLAS

abstract: In the context of the ATLAS experiment there is growing evidence of the importance of different kinds of Meta-data including all the important details of the detector and data acquisition that are vital for the analysis of the acquired data. The Online BookKeeper (OBK) is a component of ATLAS online software that stores all information collected while running the experiment, including the Meta-data associated with the event acquisition, triggering and storage. The facilities for acquisition of control data within the on-line software framework, together with a full functional Web interface, make the OBK a powerful tool containing all information needed for event analysis, including an electronic log book. In this paper we explain how OBK plays a role as one of the main collectors and managers of Meta-data produced on-line, and we'll also focus on the Web facilities already available. The usage of the web interface as an electronic run logbook is also explained, together with the future extensions. We describe the technology used in OBK development and how we arrived at the present level explaining the previous experience with various DBMS technologies. The extensive performance evaluations that have been performed and the usage in the production environment of the ATLAS test beams are also analysed.


title: The Community Authorization Service: Status and Future

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


title: The Athena Startup Kit

abstract: The Athena Startup Kit (ASK), is an interactive front-end to the Atlas software framework (ATHENA). Written in python, a very effective "glue" language, it is build on top of the, in principle unrelated, code repository, build, configuration, debug, binding, and analysis tools. ASK automates many error-prone tasks that are otherwise left to the end-user, thereby pre-empting a whole category of potential problems. Through the existing tools, which ASK will setup for the user if and as needed, it locates available resources, maintains job coherency, manages the run-time environment, allows for interactivity and debugging, and provides standalone execution scripts. An end-user who wants to run her own analysis algorithms within the standard environment can let ASK generate the appropriate skeleton package, the needed dependencies and run-time, as well as a default job options script. For new and casual users, ASK comes with a graphical user interface; for advanced users, ASK has a scriptable command line interface. Both are built on top of the same set of libraries. ASK does not need to be, and isn't, experiment neutral. Thus it has built-in workarounds for known gotcha's, that would otherwise be a major time-sink for each and every new user. ASK minimizes the overhead for those physicists in Atlas who just want to write and run their analysis code.


title: BaBar Web job submission with Globus authentication and AFS access

abstract: We present two versions of a grid job submission system produced for the BaBar experiment. Both use globus job submission to process data spread across various sites, producing output which can be combined for analysis. The problems encountered with authorisation and authentication, data location, job submission, and the input and output sandboxes are described, as are the solutions. The total system is still some way short of the aims of enterprises such as the EDG, but represent a significant step along the way.


title: GANGA: a user-Grid interface for Atlas and LHCb

abstract: The Gaudi/Athena and Grid Alliance (GANGA) is a front-end for the configuration, submission, monitoring, bookkeeping, output collection, and reporting of computing jobs run on a local batch system or on the grid. In particular, GANGA handles jobs that use applications written for the Gaudi software framework shared by the Atlas and LHCb experiments. GANGA exploits the commonality of Gaudi-based computing jobs, while insulating against grid-, batch- and framework-specific technicalities, to maximize end-user productivity in defining, configuring, and executing jobs. Designed for a python-based component architecture, GANGA has a modular underpinning and is therefore well placed for contributing to, and benefiting from, work in related projects. Its functionality is accessible both from a scriptable command-line interface, for expert users and automated tasks, and through a graphical interface, which simplifies the interaction with GANGA for beginning and c1asual users. This paper presents the GANGA design and implementation, the development of the underlying software bus architecture, and the functionality of the first public GANGA release.


title: GMA Instrumentation of the Athena Framework using NetLogger

abstract: Grid applications are, by their nature, wide-area distributed applications. This WAN aspect of Grid applications makes the use of conventional monitoring and instrumentation tools (such as top, gprof, LSF Monitor, etc) impractical for verification that the application is running correctly and efficiently. To be effective, monitoring data must be "end-to-end", meaning that all components between the Grid application endpoints must be monitored. Instrumented applications can generate a large amount of monitoring data, so typically the instrumentation is off by default. For jobs running on a Grid, there needs to be a general mechanism to remotely activate the instrumentation in running jobs. The NetLogger Toolkit Activation Service provides this mechanism. To demonstrate this, we have instrumented the ATLAS Athena Framework with NetLogger to generate monitoring events. We then use a GMA-based activation service to control NetLogger's trigger mechanism. The NetLogger trigger mechanism allows one to easily start, stop, or change the logging level of a running program by modifying a trigger file. We present here details of the design of the NetLogger implementation of the GMA-based activation service and the instrumentation service for Athena. We also describe how this activation service allows us to non-intrusively collect and visualize the ATLAS Athena Framework monitoring data.


title: OO Model of the STAR offline production "Event Display" and its implementation based on Qt-ROOT

abstract: The paper presents the "Event Display" package for the STAR offline production as a special visualization tool to debug the reconstruction code. This can be achieved if an author of the algorithm / code may build his/her own custom Event Display alone from the base software blocks and re-used some well-designed, easy to learn user-friendly patterns. For STAR offline production Event Display ROOT with Qt lower level interface was chosen as the base tools.


title: Using CAS to Manage Role-Based VO Sub-Groups

abstract: LHC-era HENP experiments will generate unprecidented volumes of data and require commensurately large compute resources. These resources are larger than can be marshalled at any one site within the community. Production reconstruction, analysis, and simulation will need to take maximum advantage of these distributed computing and storage resources using the new capabilities offered by the Grid computing paradigm. Since large-scale, coordinated Grid computing involves user access across many Regional Centers and national and funding boundaries, one of the most crucial aspects of Grid computing is that of user authentication and authorization. While projects such as the DOE Grids CA have gone a long way to solving the problem of distributed authentication, the authorization problem is still largely open. We have developed and tested a prototype VO-Role management system using the Community Authorization Service (CAS) from the Globus project. CAS allows for a flexible definition of resources. In this protoype we define a role as a resource within the CAS database and assign individuals in the VO access to that resource to indicate their ability to assert the role. The access of an individual to this VO-Role resource is then an annotation of the user's CAS proxy certificate. This annotation is then used by the local resource managers to authorize access to local compute and storage resources at a granularity which is base on neither VOs nor individuals. We report here on the configuration details for the CAS database and the Globus Gatekeeper and on how this general approch could be formalized and extended to meet the clear needs of LHC experiments using the Grid.


title: The StoreGate: a Data Model for the Atlas Software Architecture

abstract: The Atlas collaboration at CERN has adopted the Gaudi software architecture which belongs to the blackboard family: data objects produced by knowledge sources (e.g. reconstruction modules) are posted to a common in-memory data base from where other modules can access them and produce new data objects. The StoreGate has been designed, based on the Atlas requirements and the experience of other HENP systems such as Babar, CDF, CLEO, D0 and LHCB, to identify in a simple and efficient fashion (collections of) data objects based on their type and/or the modules which posted them to the Transient Data Store (the blackboard). The developer also has the freedom to use her preferred key class to uniquely identify a data object according to any other criterion. Besides this core functionality, the StoreGate provides the developers with a powerful interface to handle in a coherent fashion persistable references, object lifetimes, memory management and access control policy for the data objects in the Store. It also provides a Handle/Proxy mechanism to define and hide the cache fault mechanism: upon request, a missing Data Object can be transparently created and added to the Transient Store presumably retrieving it from a persistent data-base, or even reconstructing it on demand.


title: Worldwide Fast File Replication on Grid Datafarm

abstract: The Grid Datafarm architecture is designed for global petascale data-intensive computing. It provides a global parallel filesystem with online petascale storage, scalable I/O bandwidth, and scalable parallel processing, and it can exploit local I/O in a grid of clusters with tens of thousands of nodes. One of features is that it manages file replicas in filesystem metadata for fault tolerance and load balancing. This paper discusses and evaluates several techniques to support long-distance fast file replication. The Grid Datafarm manages a ranked group of files as a Gfarm file, each file, called a Gfarm file fragment, being stored on a filesystem node, or replicated on several filesystem nodes. Each Gfarm file fragment is replicated independently and in parallel using rate-controlled HighSpeed TCP with network striping. On a US-Japan testbed with 10,000 km distance, we achieve 419 Mbps using 2 nodes on each side, and 741 Mbps using 4 nodes out of 893 Mbps with two transpacific networks.


title: Universal Sequential Decisions in Unknown Environments

abstract: We give a brief introduction to the AIXI model, which unifies and overcomes the limitations of sequential decision theory and universal Solomonoff induction. While the former theory is suited for active agents in known environments, the latter is suited for passive prediction of unknown environments.


title: Building A High Performance Parallel File System Using Grid Datafarm and ROOT I/O

abstract: Sheer amount of petabyte scale data foreseen in the LHC experiments require a careful consideration of the persistency design and the system design in the world-wide distributed computing. Event parallelism of the HENP data analysis enables us to take maximum advantage of the high performance cluster computing and networking when we keep the parallelism both in the data processing phase, in the data management phase, and in the data transfer phase. A modular architecture of FADS/ Goofy, a versatile detector simulation framework for Geant4, enables an easy choice of plug-in facilities for persistency technologies such as Objectivity/DB and ROOT I/O. The framework is designed to work naturally with the parallel file system of Grid Datafarm (Gfarm). FADS/Goofy is proven to generate 10^6 Geant4-simulated Atlas Mockup events using a 512 CPU PC cluster. The data in ROOT I/O files is replicated using Gfarm file system. The histogram information is collected from the distributed ROOT files. During the data replication it has been demonstrated to achieve more than 2.3 Gbps data transfer rate between the PC clusters over seven participating PC clusters in the United States and in Japan.


title: Grid-Brick Event Processing Framework in GEPS

abstract: Experiments like ATLAS at LHC involve a scale of computing and data management that greatly exceeds the capability of existing systems, making it necessary to resort to Grid-based Parallel Event Processing Systems (GEPS). Traditional Grid systems concentrate the data in central data servers which have to be accessed by many nodes each time an analysis or processing job starts. These systems require very powerful central data servers and make little use of the distributed disk space that is available in commodity computers. The Grid-Brick system, which is described in this paper, follows a different approach. The data storage is split among all grid nodes having each one a piece of the whole information. Users submit queries and the system will distribute the tasks through all the nodes and retrieve the result, merging them together in the Job Submit Server. The main advantage of using this system is the huge scalability it provides, while its biggest disadvantage appears in the case of failure of one of the nodes. A workaround for this problem involves data replication or backup.


title: BaBar - A Community Web Site in an Organizational Setting

abstract: The BABAR Web site was established in 1993 at the Stanford Linear Accelerator Center (SLAC) to support the BABAR experiment, to report its results, and to facilitate communication among its scientific and engineering collaborators, currently numbering about 600 individuals from 75 collaborating institutions in 10 countries. The BABAR Web site is, therefore, a community Web site. At the same time it is hosted at SLAC and funded by agencies that demand adherence to policies decided under different priorities. Additionally, the BABAR Web administrators deal with the problems that arise during the course of managing users, content, policies, standards, and changing technologies. Desired solutions to some of these problems may be incompatible with the overall administration of the SLAC Web sites and/or the SLAC policies and concerns. There are thus different perspectives of the same Web site and differing expectations in segments of the SLAC population which act as constraints and challenges in any review or re-engineering activities. Web Engineering, which post-dates the BABAR Web, has aimed to provide a comprehensive understanding of all aspects of Web development. This paper reports on the first part of a recent review of application of Web Engineering methods to the BABAR Web site, which has led to explicit user and information models of the BABAR community and how SLAC and the BABAR community relate and react to each other. The paper identifies the issues of a community Web site in a hierarchical, semi-governmental sector and formulates a strategy for periodic reviews of BABAR and similar sites.


title: The MammoGrid Project Grids Architecture

abstract: The aim of the recently EU-funded MammoGrid project is, in the light of emerging Grid technology, to develop a European-wide database of mammograms that will be used to develop a set of important healthcare applications and investigate the potential of this Grid to support effective co-working between healthcare professionals throughout the EU. The MammoGrid consortium intends to use a Grid model to enable distributed computing that spans national borders. This Grid infrastructure will be used for deploying novel algorithms as software directly developed or enhanced within the project. Using the MammoGrid clinicians will be able to harness the use of massive amounts of medical image data to perform epidemiological studies, advanced image processing, radiographic education and ultimately, tele-diagnosis over communities of medical "virtual organisations". This is achieved through the use of Grid-compliant services [1] for managing (versions of) massively distributed files of mammograms, for handling the distributed execution of mammograms analysis software, for the development of Grid-aware algorithms and for the sharing of resources between multiple collaborating medical centres. All this is delivered via a novel software and hardware information infrastructure that, in addition guarantees the integrity and security of the medical data. The MammoGrid implementation is based on AliEn, a Grid framework developed by the ALICE Collaboration. AliEn provides a virtual file catalogue that allows transparent access to distributed data-sets and provides top to bottom implementation of a lightweight Grid applicable to cases when handling of a large number of files is required. This paper details the architecture that will be implemented by the MammoGrid project.


title: MonALISA : A Distributed Monitoring Service Architecture

abstract: The MonALISA (Monitoring Agents in A Large Integrated Services Architecture) system provides a distributed monitoring service. MonALISA is based on a scalable Dynamic Distributed Services Architecture which is designed to meet the needs of physics collaborations for monitoring global Grid systems, and is implemented using JINI/JAVA and WSDL/SOAP technologies. The scalability of the system derives from the use of multithreaded Station Servers to host a variety of loosely coupled self-describing dynamic services, the ability of each service to register itself and then to be discovered and used by any other services, or clients that require such information, and the ability of all services and clients subscribing to a set of events (state changes) in the system to be notified automatically. The framework integrates several existing monitoring tools and procedures to collect parameters describing computational nodes, applications and network performance. It has built-in SNMP support and network-performance monitoring algorithms that enable it to monitor end-to-end network performance as well as the performance and state of site facilities in a Grid. MonALISA is currently running around the clock on the US CMS test Grid as well as an increasing number of other sites. It is also being used to monitor the performance and optimize the interconnections among the reflectors in the VRVS system.