Lectures on formal methods and performance analysis : first EEF/Euro Summer School on Trends in Computer Science, Berg en Dal, the Netherlands, July 3-7, 2000 : revised lectures

Traditionally, models and methods for the analysis of the functional correctness of reactive systems, and those for the analysis of their performance (and - pendability) aspects, have been studied by di?erent research communities. This has resulted in the development of successful, but distinct and largely unrelated modeling and analysis techniques for both domains. In many modern systems, however, the di?erence between their functional features and their performance properties has become blurred, as relevant functionalities become inextricably linked to performance aspects, e.g. isochronous data transfer for live video tra- mission. During the last decade, this trend has motivated an increased interest in c- bining insights and results from the ?eld of formal methods – traditionally - cused on functionality – with techniques for performance modeling and analysis. Prominent examples of this cross-fertilization are extensions of process algebra and Petri nets that allow for the automatic generation of performance models, the use of formal proof techniques to assess the correctness of randomized - gorithms, and extensions of model checking techniques to analyze performance requirements automatically. We believe that these developments markthe - ginning of a new paradigm for the modeling and analysis of systems in which qualitative and quantitative aspects are studied from an integrated perspective. We are convinced that the further worktowards the realization of this goal will be a growing source of inspiration and progress for both communities. Traditionally, models and methods for the analysis of the functional correctness of reactive systems and those for the analysis of their performance (and dependability) aspects have been studied by different research communities. However, in modern systems the difference between their functional features and their performance properties has become blurred. During the last decade, this trend has motivated and increased interest in combining insights from the field of formal methods, traditionally focussed on functionality, with techniques from performance modeling and analysis. The 11 chapters in this book present the state of the art of research and tool development for the promising integrated approach towards modeling and analysis of functional and performance aspects of reactive systems Formal Methods For Performance Evaluation / Ulrich Herzog -- Markovian Models For Performance And Dependability Evaluation / Boudewijn R. Haverkort -- Introduction To Stochastic Petri Nets / Gianfranco Balbo -- Non-markovian Analysis / Reinhard German -- Process Algebra And Markov Chains / Ed Brinksma And Holger Hermanns -- Verification Of Randomized Distributed Algorithms / Roberto Segula -- Constructing Automata From Temporal Logic Formulas: A Tutorial / Pierre Wolper -- Exploiting Structure In Solution: Decomposing Compositional Models / Jane Hillston -- Stochastic Activity Networks: Formal Definitions And Concepts / William H. Sanders And John F. Meyer. Ed Brinksma, Holger Hermanns, Joost-pieter Katoen (eds.). Includes Bibliographical References And Index. Formal Methods for Performance Evaluation....Pages 1-37 Markovian Models for Performance and Dependability Evaluation....Pages 38-83 Introduction to Stochastic Petri Nets....Pages 84-155 Non-Markovian Analysis....Pages 156-182 Process Algebra and Markov Chains....Pages 183-231 Verification of Randomized Distributed Algorithms....Pages 232-260 Constructing Automata from Temporal Logic Formulas: A Tutorial⋆....Pages 261-277 Exploiting Structure in Solution: Decomposing Compositional Models....Pages 278-314 Stochastic Activity Networks: Formal Definitions and Concepts⋆....Pages 315-343 Distributed and Structured Analysis Approaches to Study Large and Complex Systems⋆....Pages 344-374 General Distributions in Process Algebra....Pages 375-429 Performance Evaluation (PE) means to investigate and optimize the dynamic time-varying behavior within and between the individual components of transportation and processing systems.