Rob van Glabbeek

Accepting PhD Students

PhD projects

Concurrency theory

If you made any changes in Pure these will be visible here soon.

Personal profile

Research Interests

Comparative Concurrency Semantics. Mathematical models and formal languages for the representation of distributed systems and the verification of statements about them; in particular foundational work investigating the possibilities of such models and languages. 

My specific research interests include: models of concurrency, process algebra, mesh network protocols, mutual exclusion, time-outs, compositional implementation relations, structural operational semantics, proof nets for linear logic, temporal logic, synchronous versus asynchronous communication in distributed systems, and building a theory of processes with probabilities and nondeterminism. Lately I am particularly interested in formulating and proving liveness properties, saying that a system reaches a desired state.

Websites

Collaborative Activity

I maintain close ties with the concurrency group at Stanford University. My work on proof nets and on higher-dimensional automata is to a large extent in cooperation with this group. I also participate in research activities in process algebra and structural operational semantics that span many European sites, including Eindhoven University of Technology and the Free University in Amsterdam. My work on synchronous versus asynchronous communication is in cooperation with Ursula Goltz and Jens-Wolfhard Schicke-Uffmann, from the University of Braunschweig, Germany. My work on justness, and on wireless mesh networks, is in collaboration with Peter Hoefner and several students at ANU, Canberra, Australia

Positions available

Interested in doing a PhD/Master's/Bachelor's/Honour's thesis with me? I'm willing to supervise good students on any topic that suits both the student and me. This list should give an inkling of my research interests. 

Biography

Rob van Glabbeek has a strong international reputation in the study of the theory of concurrent computation, having made particular contributions to the conciliation of the interleaving and the true concurrency communities by codeveloping the current view of branching time and causality as orthogonal but interacting dimensions of concurrency. He condensed many divergent views on semantic equivalences into the linear time- branching time spectrum. The resulting publications are required reading in the graduate programs of several universities. Together with Peter Weijland he invented the notion of branching bisimulation, that since has become the prototypical example of a branching time equivalence, and the semantic equivalence used in most verification tools based on equivalence checking. With Ursula Goltz he proposed the notion of action refinement as a useful tool for evaluating semantic equivalences and implementation relations. This gave rise to a wave of publications, including a dozen Ph.D. theses. With Peter Rittgen he initiated the application of process algebraic methods in the formal description and analysis of economic production processes. As consultant for Ricoh innovations he contributed to the practical application of concurrency-theoretic ideas in workflow management. With Dominic Hughes he made a crucial contribution to the proof theory of linear logic by proposing a notion of proof net that had been sought after in vain by linear logicians since the inception of linear logic. Together with Vaughan Pratt he initiated the now widespread use of higher dimensional automata and other geometric models of concurrency. With Gordon Plotkin he integrated various causality respecting models of concurrency, including Petri nets, event structures and propositional theories. By bridging the areas of structural operational semantics and logic programming, he developed a proof method and semantics that applies simultaneously to transition system specifications and logic programs. With Wan Fokkink he used results from unification theory and from modal logic to obtain compositionality results in structural operational semantics. This research gave rise to many congruence formats for semantic equivalences and preorders, which allow one to infer compositionality from purely syntactic properties of language specifications. In 2017 he even contributed a congruence format for recursion.

In 2007, in cooperation with Yuxin Deng, Matthew Hennessy, Carroll Morgan and Chenyi Zhang, he characterised the may- and must-testing preorders for processes with probabilistic and nondeterministic choice, thereby solving a problem that was posed in 1992 and had remained open ever since. Together with Bas Ploeger, he showed that the leading algorithm for determining whether a program (abstractly represented as a transition system) correctly simulates another such program, is based on a fixed point theory that is irreparably flawed; and repaired the algorithm in a way that bypasses this fixed point theory. In 2011, together with NICTA colleagues Peter Höfner, Annabelle MvIver, Ansgar Fehnker, Marius Portman and Wee Lum Tan, he developed a new process algebra for wireless mesh networks and used it to obtain the first rigorous formalisation of the specification of the popular Ad-hoc On-demand Distance Vector (AODV) routing protocol. This revealed that under a plausible interpretation of the original specification of AODV, the protocol does admit routing loops; this is in direct contradiction with popular belief, the promises of the AODV specification, and the main paper on AODV (with 26000 citations). The NICTA team also proved loop-freedom of AODV under a subtly different interpretation of the original specification. In cooperation with Tim Bourke, this work was mechanically formalised with the theorem prover Isabelle/HOL. In 2012, together with Ursula Goltz and Jens Schicke-Uffmann, he gave a precise characterisation of the class of concurrent systems, modelled as plain Petri nets, that, without making concessions on branching time behaviour, concurrency or divergence, cannot be implemented in a distributed way using only asynchronous communication.

In 2015, jointly with Peter Höfner, he established that fair schedulers, as frequently occur in network routers and operating systems, as well as correct mutual exclusion protocols, cannot be rendered in standard process algebras like CCS, at least not without resorting to fairness assumptions. For this type of application, mild extensions of CCS are called for. Also together with Peter Höfner, he wrote a definitive survey of fairness assumptions for concurrent systems, and introduced justness, an assumption in between progress and weak fairness, that is crucial for proving liveness properties of distributed system. In 2019 he published a research agenda for proving liveness properties that is based on this notion; it calls for a radical adaptation of established theories, including strong bisimilarity. He added reward testing as a new and more powerful mode of testing concurrent systems, besides the classical modes of may, must and should testing. With Vincent Gramoli and Pierre Tholoniat he presented the first cross-chain payment protocol that works correctly in the presence of clock skew, and introduced asynchronous networks of timed automata to formalise such protocols. He also investigated how the correctness of such protocols depends on (partially) synchronous communication. In 2020 he proposed reactive temporal logic, a form of temporal logic better adapted to the study of reactive systems. Amongst others, it allows unambiguous formal specifications of what does and doesn't count as a correct mutual exclusion protocol.

Van Glabbeek extended the expressivess of standard process algebras by introding a time-out operator that does not require a quantified notion of time. He developed a comprehensive framework for comparing the expressiveness of process calculi, and applied it to show that the π-calculus is no more expressive then a variant of CCS in which the result of a synchronisation of two actions is itself an action subject to relabelling or restriction, rather than the silent action τ. This contradicts the long-held belief that the π-calculus captures a concept of mobility that cannot be captured by immobile calculi like CCS, CSP or ACP.  In collaboration with Ross Horne and Peter Höfner, he strengthened the theory of session types, by making them sound and complete for a more powerful notion of lock-freedom.  Recently, he formulated an impossibility result that appears to contradict much published work and folklore: When assuming atomicity, in the sense that read and writes to a shared register cannot interrupt each other, or overlap in time, it is fundamentally impossible to achieve speed-independent mutual exclusion, where starvation-freedom holds without making a fairness assumption.  This can be achieved when giving up on speed independence or atomicity.

In addition, he has organised workshops on combining compositionality and concurrency, on logic, language and information, on the Unified Modelling Language, on workflow management, web services and business process modelling, on automatic and semi-automatic system verification, on structural operational semantics, and on formal methods for embedded systems.
      He is editor-in-chief of Electronic Proceedings in Theoretical Computer Science, a member of the editorial boards of Information and Computation and Theoretical Computer Science, and has been on several dozen program committees.

Education/Academic qualification

Computer Science, Doctor of Philosophy (PhD), Comparative Concurrency Semantics and Refinement of Actions, Vrije Universiteit Amsterdam

Award Date: 16 May 1990

Mathematics, Master of Science (with Distinction), Good Coverings, Leiden University

… → Nov 1984

External positions

Adjunct Professor, UNSW Australia

1 Jun 2004 → …

Research affiliate, Stanford University

1 Sept 2002 → …

Fingerprint

Dive into the research topics where Rob van Glabbeek is active. These topic labels come from the works of this person. Together they form a unique fingerprint.
  • 1 Similar Profiles

Collaborations and top research areas from the last five years

Recent external collaboration on country/territory level. Dive into details by clicking on the dots or