Fixed-delay Events in Generalized Semi-Markov Processes Revisited

BRÁZDIL, Tomáš, Jan KRČÁL, Jan KŘETÍNSKÝ and Vojtěch ŘEHÁK. Fixed-delay Events in Generalized Semi-Markov Processes Revisited. In CONCUR 2011 - Concurrency Theory: 22nd International Conference. Berlin Heidelberg New York: Springer, 2011, p. 140-155. ISBN 978-3-642-23216-9.

Basic information

Original name

Fixed-delay Events in Generalized Semi-Markov Processes Revisited

Authors

BRÁZDIL, Tomáš (203 Czech Republic, guarantor, belonging to the institution), Jan KRČÁL (203 Czech Republic, belonging to the institution), Jan KŘETÍNSKÝ (203 Czech Republic, belonging to the institution) and Vojtěch ŘEHÁK (203 Czech Republic, belonging to the institution)

Edition

Berlin Heidelberg New York, CONCUR 2011 - Concurrency Theory: 22nd International Conference, p. 140-155, 16 pp. 2011

Publisher

Springer

---

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Germany

Confidentiality degree

není předmětem státního či obchodního tajemství

Publication form

printed version "print"

RIV identification code

RIV/00216224:14330/11:00049932

Organization unit

Faculty of Informatics

ISBN

978-3-642-23216-9

UT WoS

000307082500010

Keywords in English

generalized semi-Markov processes; long-run average; stability; discrete events

Tags

best1

Tags

International impact, Reviewed

---

Abstract

V originále

We study long run average behavior of generalized semi-Markov processes with both fixed-delay events as well as variable-delay events. We show that allowing two fixed-delay events and one variable-delay event may cause an unstable behavior of a GSMP. In particular, we show that a frequency of a given state may not be defined for almost all runs (or more generally, an invariant measure may not exist). We use this observation to disprove several results from literature. Next we study GSMP with at most one fixed-delay event combined with an arbitrary number of variable-delay events. We prove that such a GSMP always possesses an invariant measure which means that the frequencies of states are always well defined and we provide algorithms for approximation of these frequencies. Additionally, we show that the positive results remain valid even if we allow an arbitrary number of reasonably restricted fixed-delay events.

---

Links

GAP202/10/1469, research and development project	Name: Formální metody pro analýzu a verifikaci komplexních systémů Investor: Czech Science Foundation
GD102/09/H042, research and development project	Name: Matematické a inženýrské metody pro vývoj spolehlivých a bezpečných paralelních a distribuovaných počítačových systémů Investor: Czech Science Foundation
MSM0021622419, plan (intention)	Name: Vysoce paralelní a distribuované výpočetní systémy Investor: Ministry of Education, Youth and Sports of the CR, Highly Parallel and Distributed Computing Systems
MUNI/A/0057/2011, interní kód MU	Name: Posílení zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity (Acronym: SKONF) Investor: Masaryk University, Category A
MUNI/A/0914/2009, interní kód MU	Name: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace (Acronym: SV-FI MAV) Investor: Masaryk University, Category A
1M0545, research and development project	Name: Institut Teoretické Informatiky Investor: Ministry of Education, Youth and Sports of the CR, Institute for Theoretical Computer Science