Report

Teaser, summary, work performed and final results

Periodic Reporting for period 1 - PACT (Proof-theoretical Approaches to Concurrency Theory)

Teaser

The project was based on the observation that the development of logical foundations had been a very successful methodology in the framework of sequential programming, and proposed to investigate a similar development in the framework of concurrent programming. This is...

Summary

The project was based on the observation that the development of logical foundations had been a very successful methodology in the framework of sequential programming, and proposed to investigate a similar development in the framework of concurrent programming. This is particularly challenging, because the current move from the standard setting towards programs running in a distributed way, potentially on mobile infrastructures, has lead to a very complex theory where safety guarantees are still difficult to obtain. The fundamental question of the project (how to develop well-behaved correspondence between proofs and concurrent programs) also yields important problems in proof theory, where some progress has been made recently in representing proofs in a more parallel ways, but the interaction of sequentiality and parallelism remains obscure. The project was therefore organised in two steps: first, the connection between proofs and programs should be studied in a setting without sequentiality (that is, without the ability to explicitly order actions in a program), and only then should sequentiality be added to expand the expressivity of programs. The main challenge lies in the development of a system offering a representation of proofs flexible enough to capture simple programs in a simple way and yet allow for an extension to arbitrary sequentiality. In order to achieve this, the proof-theoretical investigation has to be guided by the known structure of concurrent programming models: here the guiding perspective was given by the family of languages around the pi-calculus (a mathematical model for concurrent programs), and in particular the solos calculus, in which all actions are parallel cannot be explicity ordered (as a basis for further extension to arbitrary sequentiality).

Work performed

\"The first step was the definition of a correspondence between a simple sequent calculus proof system for linear logic and a typed version of the solos calculus. The problem here is a mismatch between the tree-based structure of proofs and the shape of concurrent programs. In order to achieve more control over the structure of proofs, we used the focusing technique, which also implicitly introduces a certain form of sequentiality. It is however insufficient, so that much more investigation into the notion of sequentiality in proof theory was necessary. Other logical formalisms had to be considered, starting with natural deduction, which takes the form of proof-nets in the case of linear logic. Trying to define an adequate correspondence between highly parallel programs and proof objects lead to the design of a system of natural deduction for classical logic (supporting parallelism but involving less control mechanisms than linear logic). But this extension beyond standard proof-theoretical formalisms requires to adapt standard mechanisms and in particular the normalisation procedure, the specific transformation that models computation within logics. Normalisation is a subtle mechanism that can only be meaningfully extended by applying entirely logical principles. The definition of such a transformation that could support a form of arbitrary sequentiality lead to the conclusion that an even more fine-grained representation was needed. The third step in the investigation was therefore to tackle sequentiality through non-commutativity in proof theory, as allowed by the formalism of the calculus of structures. However, the great flexibility offered by this approach comes with a price: proving the basic properties of such a system (in particular normalisation) can be very difficult, and most existing techniques are not syntactic and \"\"small-step\"\" enough to be suitably interpreted as computation. Such a system allows to combine pieces of proofs just as pieces of distributed programs can be combined, but the problem of designing a correct, terminating normalisation procedure working through small-steps transformations is still open.\"

Final results

Investigations into logical foundations for concurrent programming are still in their early phase. Despite the enthusiasm around this idea when linear logic was introduced, it took a long time for research in this field to build up a better understanding of the problems at hand. The various formalisms and proof systems investigated during this project all have their benefits and drawbacks: they belong to the groundwork for further developments, in showing how certain features are important or conversely what approaches reach their limit when introducing sequentiality into a parallel setting. An important lesson here is that the abstract notion of sequentiality (to be observed in normalisation procedures in proof theory) must be studied much more thoroughly. It was used from the very beginning in concurrent programming languages, but is not nearly as present in logical studies. After this investigation, it seems that we either have to restrict the kind of sequentiality offered (thus discarding the option to arbitrarily order any actions in a program) or develop completely novel methods in more advanced logical formalisms (such as the calculus of structures).

Website & more info

More info: https://www.mtv.tu-berlin.de/menue/research/research_projects/pact_projekt/parameter/de/.