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 over these actions and by not making explicit the
possible interleaving of concurrent actions. However, pomsets offer no compact representation of
choices. 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 encode choreographies as branching pomsets and show that the pomset semantics of the encoded choreographies are bisimilar
to their operational semantics.
models are based on languages or automata over sending and receiving actions. Pomsets provide a
more compact alternative by using a partial order over these actions and by not making explicit the
possible interleaving of concurrent actions. However, pomsets offer no compact representation of
choices. 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 encode choreographies as branching pomsets and show that the pomset semantics of the encoded choreographies are bisimilar
to their operational semantics.
| Original language | English |
|---|---|
| Title of host publication | Proceedings 15th Interaction and Concurrency Experience |
| Subtitle of host publication | ICE'22 |
| Editors | Clément Aubert , Cinzia Di Giusto , Larisa Safina and Alceste Scalas |
| Publisher | Electronic Proceedings in Theoretical Computer Science (EPTCS) |
| Pages | 37-52 |
| Number of pages | 16 |
| Volume | 365 |
| DOIs | |
| Publication status | Published - 9 Aug 2022 |
| Event | 15th Interaction and Concurrency Experience - Lucca, Italy Duration: 17 Jun 2022 → 17 Jun 2022 https://www.discotec.org/2022/ice |
Publication series
| Series | Electronic proceedings in theoretical computer science |
|---|---|
| Volume | 356 |
| ISSN | 2075-2180 |
Workshop
| Workshop | 15th Interaction and Concurrency Experience |
|---|---|
| Abbreviated title | ICE 2022 |
| Country/Territory | Italy |
| City | Lucca |
| Period | 17/06/22 → 17/06/22 |
| Internet address |