Roberto Bruni ; Hernán Melgratti ; Ugo Montanari - Concurrency and Probability: Removing Confusion, Compositionally

lmcs:5271 - Logical Methods in Computer Science, December 19, 2019, Volume 15, Issue 4 - https://doi.org/10.23638/LMCS-15(4:17)2019
Concurrency and Probability: Removing Confusion, CompositionallyArticle

Authors: Roberto Bruni ; Hernán Melgratti ; Ugo Montanari

Assigning a satisfactory truly concurrent semantics to Petri nets with confusion and distributed decisions is a long standing problem, especially if one wants to resolve decisions by drawing from some probability distribution.
Here we propose a general solution based on a recursive, static decomposition of (occurrence) nets in loci of decision, called structural branching cells (s-cells). Each s-cell exposes a set of alternatives, called transactions. Our solution transforms a given Petri net into another net whose transitions are the transactions of the s-cells and whose places are those of the original net, with some auxiliary structure for bookkeeping. The resulting net is confusion-free, and thus conflicting alternatives can be equipped with probabilistic choices, while nonintersecting alternatives are purely concurrent and their probability distributions are independent. The validity of the construction is witnessed by a tight correspondence with the recursively stopped configurations of Abbes and Benveniste. Some advantages of our approach are that: i) s-cells are defined statically and locally in a compositional way;
ii) our resulting nets faithfully account for concurrency.


Volume: Volume 15, Issue 4
Secondary volumes: Selected Papers of the 33rd ACM/IEEE Symposium on Logic in Computer Science (LICS 2018)
Published on: December 19, 2019
Accepted on: October 29, 2019
Submitted on: March 8, 2019
Keywords: Computer Science - Logic in Computer Science, F.1.1, F.1.2, F.1.1, F.1.2
Funding:
    Source : OpenAIRE Graph
  • Behavioural Application Program Interfaces; Funder: European Commission; Code: 778233

1 Document citing this article

Consultation statistics

This page has been seen 3230 times.
This article's PDF has been downloaded 601 times.