Branching pomsets: Design, expressiveness and applications to choreographies - Inria - Institut national de recherche en sciences et technologies du numérique Access content directly
Journal Articles Journal of Logical and Algebraic Methods in Programming Year : 2023

Branching pomsets: Design, expressiveness and applications to choreographies

Abstract

Choreographic languages describe possible sequences of interactions among a set of agents. Typical models are based on languages or automata over sending and receiving actions. Pomsets provide a more compact alternative by using a partial order to explicitly represent causality and concurrency between these actions. However, pomsets offer no representation of choices, thus a set of pomsets is required to represent branching behaviour. For example, if an agent Alice can send one of two possible messages to Bob three times, one would need a set of 2 × 2 × 2 distinct pomsets to represent all possible branches of Alice's behaviour. This paper proposes an extension of pomsets, named branching pomsets, with a branching structure that can represent Alice's behaviour using 2 + 2 + 2 ordered actions. We compare the expressiveness of branching pomsets with that of several forms of event structures from the literature. We encode choreographies as branching pomsets and show that the pomset semantics of the encoded choreographies are bisimilar to their operational semantics. Furthermore, we define well-formedness conditions on branching pomsets, inspired by multiparty session types, and we prove that the well-formedness of a branching pomset is a sufficient condition for the realisability of the represented communication protocol. Finally, we present a prototype tool that implements our theory of branching pomsets, focusing on its applications to choreographies.
Fichier principal
Vignette du fichier
branching-pomsets-jlamp-2023.pdf (1.23 Mo) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-04360686 , version 1 (21-12-2023)

Licence

Attribution

Identifiers

Cite

Luc Edixhoven, Sung-Shik Jongmans, José Proença, Ilaria Castellani. Branching pomsets: Design, expressiveness and applications to choreographies. Journal of Logical and Algebraic Methods in Programming, 2023, 136, ⟨10.1016/j.jlamp.2023.100919⟩. ⟨hal-04360686⟩

Collections

INRIA INRIA2 ANR
17 View
5 Download

Altmetric

Share

Gmail Facebook X LinkedIn More