Realisability of Branching Pomsets

Luc Edixhoven; Sung-Shik Jongmans

doi:10.1007/978-3-031-20872-0_11

Realisability of Branching Pomsets

Luc Edixhoven^*, Sung-Shik Jongmans

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference Article in proceeding › Academic › peer-review

Abstract

A communication protocol is realisable if it can be faithfully
implemented in a distributed fashion by communicating agents. Pomsets
offer a way to compactly represent concurrency in communication protocols and have been recently used for the purpose of realisability analysis.
In this paper we focus on the recently introduced branching pomsets,
which also compactly represent choices. 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.

Original language	English
Title of host publication	Formal Aspects of Component Software
Subtitle of host publication	18th International Conference, FACS 2022, Virtual Event, November 10–11, 2022, Proceedings
Editors	Silvia Lizeth Tapia Tarifa , José Proença
Place of Publication	Cham
Publisher	Springer, Cham
Chapter	11
Pages	185-204
Number of pages	20
Volume	13712
ISBN (Electronic)	978-3-031-20872-0
ISBN (Print)	978-3-031-20871-3
DOIs	https://doi.org/10.1007/978-3-031-20872-0_11
Publication status	Published - 2 Nov 2022
Event	18th International Conference on Formal Aspects of Component Software - Oslo, Norway Duration: 10 Nov 2022 → 11 Nov 2022 Conference number: 18 https://facs-conference.github.io/2022/

Publication series

Series	Lecture Notes in Computer Science
Volume	13712
ISSN	0302-9743

Conference

Conference	18th International Conference on Formal Aspects of Component Software
Abbreviated title	FACS 2022
Country/Territory	Norway
City	Oslo
Period	10/11/22 → 11/11/22
Internet address	https://facs-conference.github.io/2022/

Keywords

Choreographies
Pomsets
Realisability

Access to Document

10.1007/978-3-031-20872-0_11

Cite this

@inproceedings{59d6d52ff4734f318164a9b35c80bfed,

title = "Realisability of Branching Pomsets",

abstract = "A communication protocol is realisable if it can be faithfullyimplemented in a distributed fashion by communicating agents. Pomsetsoffer a way to compactly represent concurrency in communication protocols and have been recently used for the purpose of realisability analysis.In this paper we focus on the recently introduced branching pomsets,which also compactly represent choices. We define well-formedness conditions on branching pomsets, inspired by multiparty session types, andwe prove that the well-formedness of a branching pomset is a sufficientcondition for the realisability of the represented communication protocol.",

keywords = "Choreographies, Pomsets, Realisability",

author = "Luc Edixhoven and Sung-Shik Jongmans",

note = "DBLP License: DBLP's bibliographic metadata records provided through http://dblp.org/ are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.; 18th International Conference on Formal Aspects of Component Software, FACS 2022 ; Conference date: 10-11-2022 Through 11-11-2022",

year = "2022",

month = nov,

day = "2",

doi = "10.1007/978-3-031-20872-0_11",

language = "English",

isbn = "978-3-031-20871-3",

volume = "13712",

series = "Lecture Notes in Computer Science",

publisher = "Springer, Cham",

pages = "185--204",

editor = "{Silvia Lizeth Tapia Tarifa} and {Jos{\'e} Proen{\c c}a}",

booktitle = "Formal Aspects of Component Software",

url = "https://facs-conference.github.io/2022/",

}

Edixhoven, L & Jongmans, S-S 2022, Realisability of Branching Pomsets. in SLTT & JP (eds), Formal Aspects of Component Software: 18th International Conference, FACS 2022, Virtual Event, November 10–11, 2022, Proceedings. vol. 13712, Springer, Cham, Cham, Lecture Notes in Computer Science, vol. 13712, pp. 185-204, 18th International Conference on Formal Aspects of Component Software, Oslo, Norway, 10/11/22. https://doi.org/10.1007/978-3-031-20872-0_11

Realisability of Branching Pomsets. / Edixhoven, Luc; Jongmans, Sung-Shik.
Formal Aspects of Component Software: 18th International Conference, FACS 2022, Virtual Event, November 10–11, 2022, Proceedings. ed. / Silvia Lizeth Tapia Tarifa; José Proença. Vol. 13712 Cham: Springer, Cham, 2022. p. 185-204 (Lecture Notes in Computer Science, Vol. 13712).

Research output: Chapter in Book/Report/Conference proceeding › Conference Article in proceeding › Academic › peer-review

TY - GEN

T1 - Realisability of Branching Pomsets

AU - Edixhoven, Luc

AU - Jongmans, Sung-Shik

N1 - Conference code: 18

PY - 2022/11/2

Y1 - 2022/11/2

N2 - A communication protocol is realisable if it can be faithfullyimplemented in a distributed fashion by communicating agents. Pomsetsoffer a way to compactly represent concurrency in communication protocols and have been recently used for the purpose of realisability analysis.In this paper we focus on the recently introduced branching pomsets,which also compactly represent choices. We define well-formedness conditions on branching pomsets, inspired by multiparty session types, andwe prove that the well-formedness of a branching pomset is a sufficientcondition for the realisability of the represented communication protocol.

AB - A communication protocol is realisable if it can be faithfullyimplemented in a distributed fashion by communicating agents. Pomsetsoffer a way to compactly represent concurrency in communication protocols and have been recently used for the purpose of realisability analysis.In this paper we focus on the recently introduced branching pomsets,which also compactly represent choices. We define well-formedness conditions on branching pomsets, inspired by multiparty session types, andwe prove that the well-formedness of a branching pomset is a sufficientcondition for the realisability of the represented communication protocol.

KW - Choreographies

KW - Pomsets

KW - Realisability

UR - https://dblp.org/db/conf/facs2/facs2022.html#EdixhovenJ22

U2 - 10.1007/978-3-031-20872-0_11

DO - 10.1007/978-3-031-20872-0_11

M3 - Conference Article in proceeding

SN - 978-3-031-20871-3

VL - 13712

T3 - Lecture Notes in Computer Science

SP - 185

EP - 204

BT - Formal Aspects of Component Software

A2 - , Silvia Lizeth Tapia Tarifa

A2 - , José Proença

PB - Springer, Cham

CY - Cham

T2 - 18th International Conference on Formal Aspects of Component Software

Y2 - 10 November 2022 through 11 November 2022

ER -

Realisability of Branching Pomsets

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this