In this book we consider the important case of M
) being a concurrent system, where the number of replicated processes depends on the parameter n
but each process is independent of n
. Examples are cache coherence protocols, networks of finite-state agents, and systems that solve mutual exclusion or scheduling problems. Further examples are abstractions of systems, where the processes of the original systems actually depend on the parameter.
The literature in this area has studied a wealth of computational models based on a variety of synchronization and communication primitives, including token passing, broadcast, and guarded transitions. Often, different terminology is used in the literature, and results are based on implicit assumptions. In this book, we introduce a computational model that unites the central synchronization and communication primitives of many models, and unveils hidden assumptions from the literature. We survey existing decidability and undecidability results, and give a systematic view of the basic problems in this exciting research area.
Table of Contents
System Model and Specification Languages
Standard Proof Machinery
Rendezvous and Broadcast
Ad Hoc Networks
Parameterized Model Checking Tools
About the Author(s)Roderick Bloem, Swen Jacobs, Ayrat Khalimov
, Graz University of Technology, Austria
Roderick Bloem is a professor at Graz University of Technology. He received an M.Sc. in computer science from Leiden University in the Netherlands (1996) and a Ph.D. from the University of Colorado at Boulder (2001). His thesis work, under the supervision of Fabio Somenzi, was on formal verification using Linear Temporal Logic. Since 2002, he has been an assistant professor at Graz University of Technology and a full profesor since 2008. His research interests are in formal methods for the design and verification of digital systems, including hardware, software, and combinations such as embedded systems. He studies applications of game theory to the automatic synthesis of systems from their specifications, connections between temporal logics and omega-automata, model checking, and automatic fault localization and repair.
Swen Jacobs is a postdoc at Saarland University. He received his Ph.D. (Dr. Ing.) from Saarland University for his work on decision procedures for the verification of complex systems at the Max-Planck-Institute for Informatics. He worked at Ecole Polytechnique Federale de Lausanne (EPFL), at Technical University Graz, and has been a visiting professor at the University of Ljubljana. His current work focuses on the automated verification and synthesis of distributed systems, based on a combination of logical and game-theoretic methods.
Ayrat Khalimov is a Ph.D. student at Technical University of Graz, Austria. He received his Master's degree in applied physics and Mathematics at Moscow Insitute of Physics and Technology (MIPT), with the thesis focusing on a method of calculation of current leakages in hardware circuits. Later, he joined Dependable Systems Lab at Ecole Polytechnique Federale de Lausanne (EPFL) for an internship where he researched symbolic execution techniques for software verification. His current area of research is parameterized synthesis and verification.Igor Konnov, Helmut Veith, Josef Widder
, Vienna University of Technology, Austria
Igor Konnov is a postdoc at the Formal Methods in Systems Engineering Group, Institute of Information Systems of TU Wien (Vienna University of Technology). His research interests include model checking, parameterized model checking, and verification of distributed algorithms. He received his Specialist (comparable to M.Sc.) and Ph.D. degrees in applied mathematics and computer science from Lomonosov Moscow State University. In his Ph.D. thesis, he introduced new techniques for parameterized model checking.
Helmut Veith is a professor at the Faculty of Informatics of TU Wien (Vienna University of Technology), and an adjunct professor at Carnegie Mellon University. He has a diploma in Computational Logic and a Ph.D. sub auspiciis praesidentis in Computer Science, both from TU Wien. Prior to his appointment to Vienna, he held professor positions at TU Darmstadt and TU Munich. In his research, Helmut Veith applies formal and logical methods to problems in software technology and engineering. His current work focuses on model checking, software verification and testing, embedded software, and computer security.
Josef Widder is an assistant professor at the Faculty of Informatics of TU Wien. His primary area of interest is the theoretical approach to distributed algorithms, currently focusing on automated verification of fault-tolerant distributed algorithms. He received his Ph.D. (Doctor technicae), and his habilitation in computer science from TU Wien. He worked at the Embedded Computing Systems group and the Formal Methods in Systems Engineering group of TU Wien (Austria), the Laboratoire d'Informatique de l'Ecole Polytechnique (France), and the Parasol Lab at Texas A&M University (USA).Sasha Rubin
, University of Naples
Sasha Rubin is a postdoc at the UniversitÃ degli Studi di Napoli "Federico II" (University of Naples). He is broadly interested in the connections between automata theory and logic, and in particular, in formal verification, game theory, and finite model theory. He received his Ph.D. from the University of Auckland and was awarded the Vice-chancellor's prize for the best doctoral thesis in the Faculty of Science. He previously held a New Zealand Science and Technology Postdoctoral Fellowship. He is currently a Marie Curie fellow of the Istituto Nazionale di Alta Matematica.