VALUETOOLS 2008
INTER-PERF 2008WNS2 2008MODENETS 2008GAMECOMM 2008SMCTOOLS 2008

    SMCTOOLS

    3rd International ICST Workshop on Tools for solving Structured Markov Chains

    Performance evaluation methodologies based on structured Markov chains have taken a more prominent role over the last two decades. During this time, due to the strong exploitation of the involved structures, the techniques used to assess the performance measures of interest have advanced significan…

    Performance evaluation methodologies based on structured Markov chains have taken a more prominent role over the last two decades. During this time, due to the strong exploitation of the involved structures, the techniques used to assess the performance measures of interest have advanced significantly in terms of their efficiency, while becoming more complex at the same time. This increased complexity often acts as an opposing force to a more wide spread use of these advanced methodologies. Making these novel techniques more accessible via a set of software tools is therefore essential to further promote their integration in the system design.

    more »
    Editor(s): John Baras and Costas Courcoubetis
    Publisher
    ICST
    ISBN
    978-963-9799-31-8
    Conference dates
    20th Oct 2008
    Location
    Athens, Greece
    Appeared in EUDL
    29th Nov 2011
    Appears in
    ACM Digital Library

    Copyright © 2011–2013 ICST

    • Analysis of an on-line algorithm for solving large Markov chains

      Research Article in 3rd International ICST Workshop on Tools for solving Structured Markov Chains

      Nelly Litvak, Philippe Robert

      Abstract
      Algorithms for ranking of web pages such as Google Page-Rank assign importance scores according to a stationary distribution of a Markov random walk on the web graph. Although in the classical search…Algorithms for ranking of web pages such as Google Page-Rank assign importance scores according to a stationary distribution of a Markov random walk on the web graph. Although in the classical search scheme the ranking scores are pre-computed off-line, several challenging problems in contemporary web search, such as personalized search and search in entity graphs, require on-line PageRank computation. In this work we present a probabilistic point of view for an original on-line algorithm proposed by Abiteboul, Preda and Cobena [1]. According to this algorithm, at the beginning, each page receives an equal amount of 'cash', and every time when a page is visited by a random walk, it distributes its cash among its outgoing links. The PageRank score of a page is then proportional to the amount of cash transferred from this page. In this paper, instead of dealing with the variable 'cash', which is continuous, we create a two-dimensional discrete 'cat and mouse' Markov chain such that the amount of cash on each page can be expressed via probabilities for this new Markov chain. We also indicate further research directions, such as the analysis of the cat and mouse chain in the case when the cat's movements are described by a classical stochastic process such as the M/M/1 random walk.
       more »

    • CSRL Model Checking with Closed-Form Bounding Distributions

      Research Article in 3rd International ICST Workshop on Tools for solving Structured Markov Chains

      Nihal Pekergin, Sana Younès

      Abstract
      Continuous Stochastic Logic (CSL) which lets to express real time probabilistic properties on Continuous Time Markov Chains (CTMC) has been augmented by reward structures to check also performability…Continuous Stochastic Logic (CSL) which lets to express real time probabilistic properties on Continuous Time Markov Chains (CTMC) has been augmented by reward structures to check also performability measures. Thus Continuous Stochastic Reward Logic (CSRL) defined on Markov Reward Models (MRM) provides a framework to verify performance-related and as well as dependability-related measures. Probabilistic model checking can be provided through bounding transient, steady-state distributions of the underlying Markov chain, since models are checked to see if the considered measures are guaranteed or not. We propose to extend the model checking algorithm that we have proposed for CSL to the CSRL operators. This method is based on the construction of bounding models having closed-form transient and steady-state distributions by means of Stochastic Comparison technique. In the case when the model can be checked by this method we gain significantly in time and memory complexity. However in case when we can not conclude if the considered formula is satisfied or not, we may apply classical model checking algorithms.
       more »

    • Iterative Aggregation - Disaggregation Methods and Ordering Algorithms

      Research Article in 3rd International ICST Workshop on Tools for solving Structured Markov Chains

      Ivana Pultarová

      Abstract
      The paper presents some modifications of two-level methods for computing stationary probability distribution vector of large discrete time Markov chains. The approach considered is an iterative aggre…The paper presents some modifications of two-level methods for computing stationary probability distribution vector of large discrete time Markov chains. The approach considered is an iterative aggregation - disaggregation method. Two types of permuting the events are considered in order to improve the convergence.
       more »

    • Some bounds for M(t)/M(t)/S queue with catastrophes

      Research Article in 3rd International ICST Workshop on Tools for solving Structured Markov Chains

      Alexander I. I. Zeifman, Yakov Satin, Alexander Chegodaev, Vladimir Bening, Vsevolod Shorgin

      Abstract
      We consider the M(t)/M(t)/S queue with catastrophes. The bounds of the rate of convergence to the limit regime and the estimates of the limit probabilities are obtained. We also study the bounds for …We consider the M(t)/M(t)/S queue with catastrophes. The bounds of the rate of convergence to the limit regime and the estimates of the limit probabilities are obtained. We also study the bounds for the mean of the queue and consider an example.
       more »

    • The Discrete-Time Queueing System with Inversive Service Order and Probabilistic Priority

      Research Article in 3rd International ICST Workshop on Tools for solving Structured Markov Chains

      Alexander Pechinkin, Sergey Shorgin

      Abstract
      This paper considers a queueing system Geo/G/1/∞ with inversive service order and probabilistic priority that is determined as follows. Upon arrival into the system of a new customer its length i is …This paper considers a queueing system Geo/G/1/∞ with inversive service order and probabilistic priority that is determined as follows. Upon arrival into the system of a new customer its length i is compared with the (remaining) length j of the customer in the device and with the probability of d(i, j), which depends only on i and j, a new arrival will occupy the server while pushing out a servicing customer to the first place in the queue, and with the supplemental probability d(i, j) = 1 - d(i, j), alternatively, a customer that was under service keeps on being served while the newly arrived one occupies the first position in the queue. The remaining queue shifts by one state. The main stationary characteristics of such system's behavior have been found.
       more »