Computing average response time Book Section


Author(s): Chatterjee, Krishnendu; Henzinger, Thomas A; Otop, Jan
Article/Chapter Title: Computing average response time
Title Series: LNCS
Affiliation IST Austria
Abstract: Responsiveness—the requirement that every request to a system be eventually handled—is one of the fundamental liveness properties of a reactive system. Average response time is a quantitative measure for the responsiveness requirement used commonly in performance evaluation. We show how average response time can be computed on state-transition graphs, on Markov chains, and on game graphs. In all three cases, we give polynomial-time algorithms.
Keywords: Reactive system; Markov processes; Quantitative measures; Polynomial approximation; Polynomial-time algorithms; Liveness properties; Game graphs; On state; Performance evaluations; Response time (computer systems)
Book Title: Principles of Modeling
Volume: 10760
ISBN: 03029743 (ISSN)
Publisher: Springer  
Date Published: 2018-07-20
Start Page: 143
End Page: 161
DOI: 10.1007/978-3-319-95246-8_9
Notes: This research was supported in part by the Austrian Science Fund (FWF) under grants S11402-N23, S11407-N23 (RiSE/SHiNE) and Z211-N23 (Wittgenstein Award), ERC Start grant (279307: Graph Games), Vienna Science and Technology Fund (WWTF) through project ICT15-003 and by the National Science Centre (NCN), Poland under grant 2014/15/D/ST6/04543.
Open access: no
IST Austria Authors
  1. Thomas A. Henzinger
    415 Henzinger
Related IST Austria Work