Abstract

Limiting behaviors are quantitative measures of how a nonterminating system behaves "in the long run". For example, how often is a given component used, how much memory does the operating system use "on the average", or how long time does a car have to wait at the traffic light "on the average". We consider probabilistic infinite-state systems, modeled as Markov chains, which possess what we call a finite eager attractor. Examples of such systems include Probabilistic Lossy Channel Systems (PLCS). PLCS can be used to model communication protocols with unbounded communication channels and probabilistic message losses. We show that the steady state distribution can be approximated up-to an arbitrary precision for Markov chains with finite eager attractors. Then we generalize the result and show how to approximate the limiting average expected reward.

This is an extended version of a conference presentation of the following paper:
Parosh Aziz Abdulla, Noomene Ben Henda, Richard Mayr, Sven Sandberg. Limiting behavior of Markov chains with eager attractors. In 3rd International Conference on the Quantitative Evaluation of SysTems (QEST), Pedro R. D'Argentio, Andrew Milner, Gerardo Rubino (eds.), Pages 253-262, August 2006.

A technical report version of the paper is available here.

The slides are here: sxi (401 KB) , pdf (5.27 MB), 16 per page pdf (5.55 MB).