Survey Lecture: Joost-Pieter Katoen: Can we meet the deadline? Most probably: yes!

Thursday, July 13, 2023, 12:30pm

Location: Computer Science Center, Building E2, ground floor, B-IT room 5053.2.

Speaker: Joost-Pieter Katoen

 

Abstract: 

Continuous-time Markov chains are used in systems biology, classical performance evaluation, reliability engineering, physics, and so on. We study a the following analysis problem for CMTCs: how to compute the probability to reach a certain target state within a given deadline?
Phrased more practically: how likely is it that all substrates have turned into products in a catalytic chemical reaction within a week?
We will show that this probability can be characterised as a unique solution of a Volterra integral equation system, whose computation can be reduced to transient analysis of a slightly modified CTMC.
We will show why this problem is of practical relevance, that it can be efficiently solved on CTMCs with millions of states, and why its natural generalisation to stochastic scheduling problems is hard.

This result was published in 1999, received a test-of-time award in 2022, and forms the ingredient of many state-of-the-art CTMC tools.