13887054
A resource management framework for interactive Grids
Traditional use of Grid computing systems has been for batch jobs in the scientific and academic computing. We envision the next generation Grid computing systems to support graphical interactive sessions. In this paper, we propose a resource management framework for supporting graphical interactive sessions in a Grid computing system. We describe the high-level architectural resource management framework distributed among the submission node, central scheduler node, and the execution node. We then describe in detail the resource management framework on the execution node. The description of the resource management framework on the scheduler node is kept at a high level in this paper. The framework on execution nodes consists of Resource Management Agents, an Admission Control system and Application Predictor system. The agents on the execution node are Startup Agents, Sensor Agents, Monitoring Agents, Aggregator Agents, Enforcement Agents and Registration Agents. The Session Admission Control system is responsible for determining if a new application session can be admitted to the execution node. An Application Predictor system is responsible for predicting the resource utilization behavior of applications based on data obtained from the Resource Management Agents. The proposed framework allows for implementation of a scalable and extensible middleware for interactive Grid resource management. It supports fine-grained performance guarantees specified in service level agreements and brings forth some important and novel contributions to enable graphical interactive sessions on Grids. Copyright © 2004 John Wiley & Sons, Ltd.
17912290
An environment for enabling interactive grids
Traditional use of grid computing allows a user to submit batch jobs in a grid environment. We believe, next generation grids will extend the application domain to include interactive graphical sessions. We term such grids interactive grids. In this paper, we describe some of the challenges involved in building interactive grids. These include fine grain access control, QoS guarantees, and dynamic account management. In order to architect interactive grids, we propose and describe I-GENV, an environment for enabling interactive grids. I-GENV consists of GISH-'Grid Interactive Shell', Controlled Desktop, SAC-'Session Admission Control' module, GMMA-'Grid Monitoring and Management Agents', System Policies, and Dynamic Account Manager. We also present our testbed implementation of I-GENV using and extending Globus Toolkit 2.0 for the Grid middleware infrastructure, and VNC as the remote display technology.
47390024
On the combinatorial and algebraic complexity of quantifier elimination
In this paper we give a new algorithm for performing quantifier elimination from first order formulae over real closed fields. This algorithm improves the complexity of the asymptotically fastest algorithm for this problem, known to this date. A new feature of our algorithm is that the role of the algebraic part (the dependence on the degrees of the input polynomials) and the combinatorial part (the dependence on the number of polynomials) are separated, making possible our improved complexity bound. Another new feature is that the degrees of the polynomials in the equivalent quantifier-free formula that we output, are independent of the number of input polynomials. As special cases of this algorithm, we obtain new and improved algorithms for deciding a sentence in the first order theory over real closed fields, and also for solving the existential problem in the first order theory over real closed fields. Using the theory developed in this paper, we also give an improved bound on the radius of a ball centered at the origin, which is guaranteed to intersect every connected component of the sign partition induced by a family of polynomials. We also use our methods to obtain algorithms for solving certain decision problems in real and complex geometry which improves the complexity of the currently known algorithms for these problems.<<ETX>>
2261271
Selecting and Composing Web Services through Iterative Reformulation of Functional Specifications
We propose a specification-driven approach to Web service composition. The proposed framework allows users to start with a high-level, possibly incomplete specification of a desired (goal) service that is to be realized using a subset of the available component services. These services are represented by the system using transition systems augmented with guards over variables with infinite domains and are used to determine a strategy for their composition that would realize the goal service. In the event that the goal service cannot be realized using the available services, the system identifies the cause(s) for such failure which can then be used by the developer to reformulate the goal specification. Thus, the system supports Web service composition through iterative refinement of the functional specifications. We present a prototype implementation in tabled-logic programming environment that illustrates the key features of the proposed approach
9536962
On the combinatorial and algebraic complexity of quantifier elimination
In this paper, a new algorithm for performing quantifier elimination from first order formulas over real closed fields in given. This algorithm improves the complexity of the asymptotically fastest algorithm for this problem, known to this data. A new feature of this algorithm is that the role of the algebraic part (the dependence on the degrees of the imput polynomials) and the combinatorial part (the dependence on the number of polynomials) are sparated. Another new feature is that the degrees of the polynomials in the equivalent quantifier-free formula that is output, are independent of the number of input polynomials. As special cases of this algorithm new and improved algorithms for deciding a sentence in the first order theory over real closed fields, and also for solving the existential problem in the first order theory over real closed fields, are obtained.
2629561
Compositional Analysis for Verification of Parameterized Systems
Many safety-critical systems that have been considered by the verification community are parameterized by the number of concurrent components in the system, and hence describe an infinite family of systems. Traditional model checking techniques can only be used to verify specific instances of this family. In this paper, we present a technique based on compositional model checking and program analysis for automatic verification of infinite families of systems. The technique views a parameterized system as an expression in a process algebra (CCS) and interprets this expression over a domain of formulas (modal mu-calculus), considering a process as a property transformer. The transformers are constructed using partial model checking techniques. At its core, our technique solves the verification problem by finding the limit of a chain of formulas. We present a widening operation to find such a limit for properties expressible in a subset of modal mu-calculus. We describe the verification of a number of parameterized systems using our technique to demonstrate its utility.
2511594
Specification Synthesis for Monitoring and Analysis of MANET Protocols
This paper introduces an approach to automatic synthesis of the specification models of routing protocol behavior from the observed flow of the network traffic. In particular, our technique generalizes the monitored sequences of routing messages constructing a high-level abstract view of the protocol. The basis of our method is similar to inductive logic programming technique that derives a sound hypothesis from the individual examples. The preliminary experiments are presented on the example of AODV ad-hoc routing protocol.