New choreographic logic links program proofs and network behaviors
Two Sides of the Same Proof: Extraction and Projection in Choreographic Programming
Logic in Computer Science
Summary
Communicating computers often follow preset sequences called choreographies to avoid confusion or deadlock. This paper shows how such choreographies can be analyzed and created using ideas from logic, treating them like mathematical proofs. The authors extend previous work to handle repeated or endless behaviors and prove their method fully captures a wide range of safe network interactions. They also show how to recover a choreography by examining the network communication patterns themselves.
What this means in practice
- •For distributed system builders: Ensure distributed programs are free from locking issues by verifying their choreography corresponds to safe proofs in extended logic.
- •For network protocol designers: Extract concise choreographies from existing network interactions to better understand and optimize infinite or cyclic communication patterns.
A theory result. No direct application yet.
Authors
Matteo Acclavio, Giulia Manara, Fabrizio Montesi, Marco Peressotti
Abstract
A new approach to the theory of choreographic languages has recently been proposed, based on the interpretation of choreographies with finite behaviors as proofs in an extension of linear logic. This paper further develops this approach to cyclic proofs to be capable of representing infinite behaviors, and prove a completeness result for choreographies with respect to the class of lock-free networks. We show that in a choreographies-as-proofs correspondence, the proof equivalence induced by rule permutations corresponds to bisimilarity, and that, under adequate assumption on the procedure definitions, the proof search procedure has a finite search space, and can be used to extract a choreography from a network.