Dependence and Independence for Reversible Process Calculi
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912076442632192 |
|---|---|
| author | Aubert, Clément Phillips, Iain Ulidowski, Irek |
| author_facet | Aubert, Clément Phillips, Iain Ulidowski, Irek |
| contents | To refine formal methods for concurrent systems, there are several ways of enriching classical operational semantics of process calculi. One can enable the auditing and undoing of past synchronisations thanks to communication keys, thus easing the study of true concurrency as a by-product. Alternatively, proof labels embed information about the origins of actions in transition labels, facilitating syntactic analysis. Enriching proof labels with keys enables a theory of the relations on transitions and on events based on their labels only. We offer for the first time separate definitions of dependence relation and independence relation, and prove their complementarity on connected transitions instead of postulating it. Leveraging the recent axiomatic approach to reversibility, we prove the canonicity of these relations and provide additional tools to study the relationships between e.g., concurrency and causality on transitions and events. Finally, we make precise the subtle relationship between bisimulations based on both forward and backward transitions, on key ordering, and on dependency preservation, providing a direct definition of History Preserving bisimulation for CCS. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_14699 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Dependence and Independence for Reversible Process Calculi Aubert, Clément Phillips, Iain Ulidowski, Irek Logic in Computer Science 68Q85 F.4.2 To refine formal methods for concurrent systems, there are several ways of enriching classical operational semantics of process calculi. One can enable the auditing and undoing of past synchronisations thanks to communication keys, thus easing the study of true concurrency as a by-product. Alternatively, proof labels embed information about the origins of actions in transition labels, facilitating syntactic analysis. Enriching proof labels with keys enables a theory of the relations on transitions and on events based on their labels only. We offer for the first time separate definitions of dependence relation and independence relation, and prove their complementarity on connected transitions instead of postulating it. Leveraging the recent axiomatic approach to reversibility, we prove the canonicity of these relations and provide additional tools to study the relationships between e.g., concurrency and causality on transitions and events. Finally, we make precise the subtle relationship between bisimulations based on both forward and backward transitions, on key ordering, and on dependency preservation, providing a direct definition of History Preserving bisimulation for CCS. |
| title | Dependence and Independence for Reversible Process Calculi |
| topic | Logic in Computer Science 68Q85 F.4.2 |
| url | https://arxiv.org/abs/2410.14699 |