Distinguished Lecture: The Quest for Average Response Time

Thursday, November 15, 2018 -
4:00pm to 5:00pm
CS 1240

Speaker Name: 

Tom Henzinger, President

Speaker Institution: 

IST Austria (Inst. of Science and Technology Austria)



Cookies Location: 

CS 1240


Responsiveness -the requirement that every request to a system be
eventually handled- is one of the fundamental liveness properties of a
reactive system and lies at the heart of all methods for specifying
and verifying liveness. Average response time is a quantitative
measure for the responsiveness requirement used commonly in
performance evaluation. The static computation of average response
time has proved remarkably elusive even for finite-state models of
reactive systems. We present a robust formalism that allows the
specification and computation of quantitative temporal properties
including average response time. The formalism is based on nested
weighted automata, which can serve as monitors for measuring the
response time of a reactive system. We show that quantitative
properties specified by nested weighted automata can be computed in
exponential space for nondeterministic finite-state models of reactive
systems and in polynomial time for probabilistic finite-state models.
The specific property of average response time can be computed in
polynomial time in both cases.


Thomas A. Henzinger is president of IST Austria (Institute of Science
and Technology Austria). He holds a Dipl.-Ing. degree in Computer
Science from Kepler University in Linz, Austria, an M.S. degree in
Computer and Information Sciences from the University of Delaware, a
Ph.D. degree in Computer Science from Stanford University (1991), and
a Dr.h.c. from Fourier University in Grenoble, France (2012) and from
Masaryk University in Brno, Czech Republic (2015). He was Assistant
Professor of Computer Science at Cornell University (1992-95),
Assistant Professor (1996-97), Associate Professor (1997-98), and
Professor (1998-2004) of Electrical Engineering and Computer Sciences
at the University of California, Berkeley. He was also Director at the
Max-Planck Institute for Computer Science in Saarbruecken, Germany
(1999) and Professor of Computer and Communication Sciences at EPFL in
Lausanne, Switzerland (2004-09). His research focuses on modern
systems theory, especially models, algorithms, and tools for the
design and verification of reliable software, hardware, and embedded
systems. His HyTech tool was the first model checker for mixed
discrete-continuous systems. He is an ISI highly cited researcher, a
member of Academia Europaea, a member of the German Academy of
Sciences (Leopoldina), a member of the Austrian Academy of Sciences, a
Fellow of the AAAS, a Fellow of the ACM, and a Fellow of the IEEE. He
has received the Milner Award of the Royal Society, the Wittgenstein
Award of the Austrian Science Fund, and an ERC Advanced Investigator