Catálogo de publicaciones - libros

A service provisioning system typically contains a number of servers which may be distributed, heterogeneous and intermittently unavailable. They are used by the host in order to offer different services to a community of users. There may or may not be Service-Level Agreements involving Quality of Service constraints. In this context, there are several areas where dynamic optimisation problems arise quite naturally. These are (a) Routing and load-balancing: Where should an incoming request be sent for execution? If some queues grow large while others are short, can something be gained by transferring jobs among them? (b) Resource allocation: If different servers are dedicated to different types of service, how many should be assigned to each? When should a server be switched from one type of service to another? (c) Revenue maximisation:How are resource allocation and job admission policies affected by economic considerations? In particular, if service-level agreements specify payments for serving jobs and penalties for failing to provide a given quality of service, how many servers should be assigned to each type of service and when should jobs of that type be accepted?

These days, parallel and distributed state-space generation algorithms allow us to generate Markov chains with hundreds of millions of states. In order to solve such Markov chains for their steady-state behaviour, we typically use iterative algorithms, either on a single machine, or on a cluster of workstations. When dealing with such huge Markov chains, the accuracy of the computed probability vectors becomes a critical issue.

In this paper we report on experimental studies of, among others, the impact of different iterative solution techniques, erratic and stagnating convergence, the impact of the state-space ordering, the influence of the processor architecture chosen and the accuracy of the measure of interest, in relation to the accuracy of the individual state probabilities.

To say the least, the paper shows that the results from analysing extremely large Markov chains should be “appreciated with care”, and, in fact, questions the feasibility of the ambitious “5 nines programs” that some companies have recently started.

A parallel composition is defined for Markov reward chains with fast transitions and for discontinuous Markov reward chains. In this setting, compositionality with respect to the relevant aggregation preorders is established. For Markov reward chains with fast transitions the preorders are -lumping and -reduction. Discontinuous Markov reward chains are ‘limits’ of Markov reward chains with fast transitions, and have related notions of lumping and reduction. In total, four compositionality results are shown. In addition, the two parallel operators are related by a continuity property.

We consider a class of Markov chains known for its closed form transient and steady-state distributions. We show that some absorbing chains can be also seen as members of this class and we provide the closed form solution for their absorption time distributions. By constructing upper and lower bounding chains that belong to this particular class one can easily compute both lower and upper bounds for absorption time distribution of an arbitrary absorbing Markov chain. We provide a new algorithm for the construction of bounding chains from this class and we show a possible application of these bounds.

The characterization and the canonical representation of order phase type distributions (PH(n)) is an open research problem.

This problem is solved for  = 2, since the equivalence of the acyclic and the general PH distributions has been proven for a long time. However, no canonical representations have been introduced for the general PH distribution class so far for  > 2. In this paper we summarize the related results for  = 3. Starting from these results we recommend a canonical representation of the PH(3) class and present a transformation procedure to obtain the canonical representation based on any (not only Markovian) vector-matrix representation of the distribution.

Using this canonical transformation method we evaluate the moment bounds of the PH(3) distribution set and present the results of our numerical investigations.

In this paper we introduce time information in (Process Algebra for the Management of Resources). is a process algebra that simplifies the task of specifying processes whose behavior strongly depend on the resources that they have. One of the drawbacks of is that there is not an appropriate notion of time. In this paper we will consider that the duration of actions is controlled by a random variable. These random variables will take values, according to some probability distribution functions, that may depend, in particular, on the available resources. We present two examples showing the main features of our stochastic version of .

In this paper we describe how both, memory and time requirements for stochastic model checking of SPDL (stochastic propositional dynamic logic) formulae can significantly be reduced. SPDL is the stochastic extension of the multi-modal program logic PDL. SPDL provides means to specify path-based properties with or without timing restrictions. Paths can be characterised by so-called programs, essentially regular expressions, where the executability can be made dependent on the validity of test formulae. For model-checking SPDL path formulae it is necessary to build a product transition system (PTS) between the system model and the program automaton belonging to the path formula that is to be verified. In many cases, this PTS can be drastically reduced during the model checking procedure, as the program restricts the number of potentially satisfying paths. Therefore, we propose an approach that directly generates the reduced PTS from a given SPA specification and an SPDL path formula. The feasibility of this approach is shown through a selection of case studies, which show enormous state space reductions, at no increase in generation time.

In this paper we define a formal framework to test implementations that can be represented by the class of finite state machines introduced in [10]. First, we introduce an appropriate notion of test. Next, we provide an algorithm to derive test suites from specifications such that the constructed test suites are sound and complete with respect to two of the conformance relations introduced in [10]. In fact, the current paper together with [10] constitute a complete formal theory to specify and test the class of systems covered by the before mentioned stochastic finite state machines.

Distributed security models based on a ‘web of trust’ eliminate single points of failure and alleviate performance bottlenecks. However, such distributed approaches rely on the ability to find trust paths between participants, which introduces performance overhead. It is therefore of importance to develop trust path discovery algorithms that minimize such overhead. Since peer-to-peer (P2P) networks share various characteristics with the web of trust, P2P search algorithms can potentially be exploited to find trust paths. In this paper we systematically evaluate the application of P2P search algorithms to the trust path discovery problem. We consider the number of iterations required (as expressed by the TTL parameter) as well as the messaging overhead, for discovery of single as well as multiple trust paths. Since trust path discovery does not allow for resource replication (usual in P2P applications), we observe that trust path discovery is very sensitive to parameter choices in selective forwarding algorithms (such as K-walker), but is relatively fast when the underlying network topology is scale-free.

As Grid computing increasingly enters the commercial domain, performance and Quality of Service (QoS) issues are becoming a major concern. To guarantee that QoS requirements are continuously satisfied, the Grid middleware must be capable of predicting the application performance on the fly when deciding how to distribute the workload among the available resources. One way to achieve this is by using online performance models that get generated and analyzed on the fly. In this paper, we present a novel case study with the Globus Toolkit in which we show how performance models can be generated dynamically and used to provide online performance prediction capabilities. We have augmented the Grid middleware with an online performance prediction component that can be called at any time during operation to predict the Grid performance for a given resource allocation and load-balancing strategy. We evaluate the quality of our performance prediction mechanism and present some experimental results that demonstrate its effectiveness and practicality. The framework we propose can be used to design intelligent QoS-aware resource allocation and admission control mechanisms.