The iframe on this page is empty and contains no contentSkip to content

Department of  Computing

2013 - Technical Reports

Number Report Title
2013/1 Fatal Attractors in Parity Games
Michael Huth, Jim Huan-Pu Kuo and Nir Piterman, 31pp
2013/2 An Observationally Complete Program Logic for Imperative Higher-Order Functions
Kohei Honda, Nobuko Yoshida and Martin Berger, 80pp
2013/3 Monitoring Networks through Multiparty Session Types
Laura Bocchi, Tzu-Chun Chen, Romain Demangeon, Kohei Honda, and Nobuko Yoshida, 28pp
2013/4 Globally Governed Session Semantics
Dimitrios Kouzapas and Nobuko Yoshida, 32pp
2013/5 Multiparty Compatibility in Communicating Automata: Characterisation and Synthesis of Global Session Types
Pierre-Malo Deni“elou and Nobuko Yoshida, 22pp

Fatal Attractors in Parity Games

Michael Huth, Jim Huan-Pu Kuo and Nir Piterman, 31pp
Report: 2013/1

Download PDF Download

We study a new form of attractor in parity games and use it to define solvers that run in PTIME and are partial in that they do not solve all games completely. Technically, for color c this new attractor determines whether player c%2 can reach a set of nodes X of color c whilst avoiding any nodes of color less than c. Such an attractor is fatal if player c%2 can attract all nodes in X back to X in this manner. Our partial solvers detect fixed-points of nodes based on fatal attractors and correctly classify such nodes as won by player c%2.

Experimental results show that our partial solvers completely solve benchmarks that were constructed to challenge existing full solvers. Our partial solvers also have encouraging run times. For one partial solver we prove that its runtime is cubic in the number of nodes, that its output game is independent of the order in which attractors are computed, and that it solves all Buchi games.


An Observationally Complete Program Logic for Imperative Higher-Order Functions

Kohei Honda, Nobuko Yoshida and Martin Berger, 80pp
Report: 2013/2

Download PDF Download

We propose a simple compositional program logic for an imperative extension of call-by-value PCF, built on Hoare logic and our preceding work on program logics for pure higher-order functions. A systematic use of names and operations on them allows precise and general description of complex higher-order imperative behaviour. The proof rules of the logic exactly follow the syntax of the language and can cleanly embed, justify and extend the standard proof rules for total correctness of Hoare logic. The logic offers a foundation for general treatment of aliasing and local state on its basis, with minimal extensions. After establishing soundness, we prove that valid assertions for programs completely characterise their behaviour up to observational congruence, which is proved using a variant of finite canonical forms. The use of the logic is illustrated through reasoning examples which are hard to assert and infer using existing program logics.


Monitoring Networks through Multiparty Session Types

Laura Bocchi, Tzu-Chun Chen, Romain Demangeon, Kohei Honda, and Nobuko Yoshida, 28pp
Report: 2013/3

Download PDF Download

In large-scale distributed infrastructures, applications are realised through communications among distributed components. The need for methods for assuring safe interactions in such environments is recognized, however the existing frameworks, relying on centralised verifcation or restricted specifcation methods, have limited applicability. This paper proposes a new theory of monitored Π calculus with dynamic usageof multiparty session types (MPST), covering a rigorous foundation for safety assurance of distributed components which asynchronously communicate through multiparty sessions. Our theory establishes a framework for semantically precise decentralised run-time enforcement and provides reasoning principles over monitored distributed applications, which complement existing static analysis techniques. We introduce asynchrony through the means of explicit routers and global queues, and propose novel equivalences between networks, that capture the notion of interface equivalence, i.e. equating networks covering the same services to a user. We illustrate our static-dynamic analysis system with an ATM protocol as a running example and justify our theory with results: satisfaction equivalence, local/global safety and transparency, and session fidelity.


Globally Governed Session Semantics

Dimitrios Kouzapas and Nobuko Yoshida, 32pp
Report: 2013/4

Download PDF Download

This paper proposes a new bisimulation theory based on multiparty session types where a choreography specification governs the behaviour of session typed processes and their observer. The bisimulation is defined with the observer cooperating with the observed process in order to form complete global session scenarios and usable for proving correctness of optimisations for globally coordinating threads and processes. The induced bisimulation is strictly more fine-grained than the standard session bisimulation. The difference between the governed and standard bisimulations only appears when more than two interleaved multiparty sessions exist. This distinct feature enables to reason real scenarios in the large-scale distributed system where multiple choreographic sessions need to be interleaved. The compositionality of the governed bisimilarity is proved through the soundness and completeness with respect to the governed reduction-based congruence. Finally its usage is demonstrated by a thread transformation governed under multiple sessions in a real usecase in the large-scale cyberinfrustracture.


Multiparty Compatibility in Communicating Automata: Characterisation and Synthesis of Global Session Types

Pierre-Malo Deni“elou and Nobuko Yoshida, 22pp
Report: 2013/5

Download PDF Download

Multiparty session types are a type system that can ensure the safety and liveness of distributed peers via the global specification of their interactions. To construct a global specification from a set of distributed uncontrolled behaviours, this paper explores the problem of fully characterising multiparty session types in terms of communicating automata. We equip global and local session types with labelled transition systems (LTSs) that faithfully represent asynchronous communications through unbounded buffered channels. Using the equivalence between the two LTSs, we identify a class of communicating automata that exactly correspond to the projected local types. We exhibit an algorithm to synthesise a global type from a collection of communicating automata. The key property of our findings is the notion of multiparty compatibility which non-trivially extends the duality condition for binary session types.


 

Main campus address:
Imperial College London, South Kensington Campus, London SW7 2AZ, tel: +44 (0)20 7589 5111
Campus maps and information | About this site