Taming confusion for modeling and implementing probabilistic concurrent systems

Joost P. Katoen, Doron Peled

  • 3 Citations

Abstract

In concurrent systems, the choice of executing the next transition depends both on the timing between the agents that make independent or collaborative interactions available, and on the conflicts (nondeterministic choices) with other transitions. This creates a challenging modeling and implementation problem. When the system needs to make also probabilistic choices, the situation becomes even more complicated. We use the model of Petri nets to demonstrate the modeling and implementation problem. The proposed solution involves adding sequential observers called agents to the Petri net structure. Distributed probabilistic choices are facilitated in the presence of concurrency and nondeterminism, by selecting agents that make the choices, while guaranteeing that their view is temporarily stable. We provide a distributed scheduling algorithm for implementing a system that allows distributed probabilistic choice.
Original languageUndefined
Title of host publicationProceedings of the 22nd European Symposium on Programming (ESOP 2013)
EditorsMatthias Felleisen, Philippa Gardner
Place of PublicationLondon
PublisherSpringer Verlag
Pages411-430
Number of pages20
ISBN (Print)978-3-642-37035-9
DOIs
StatePublished - Mar 2013
Event22nd European Symposium on Programming, ESOP 2013 - Rome, Italy

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
Volume7792
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference22nd European Symposium on Programming, ESOP 2013
Abbreviated titleESOP
CountryItaly
CityRome
Period16/03/1324/03/13

Fingerprint

Petri nets
Scheduling algorithms
Parallel algorithms

Keywords

  • EC Grant Agreement nr.: FP7/295261
  • EC Grant Agreement nr.: FP7/318490
  • METIS-296392
  • IR-85506
  • EC Grant Agreement nr.: FP7/2007-2013
  • EWI-23248

Cite this

Katoen, J. P., & Peled, D. (2013). Taming confusion for modeling and implementing probabilistic concurrent systems. In M. Felleisen, & P. Gardner (Eds.), Proceedings of the 22nd European Symposium on Programming (ESOP 2013) (pp. 411-430). (Lecture Notes in Computer Science; Vol. 7792). London: Springer Verlag. DOI: 10.1007/978-3-642-37036-6_23

Katoen, Joost P.; Peled, Doron / Taming confusion for modeling and implementing probabilistic concurrent systems.

Proceedings of the 22nd European Symposium on Programming (ESOP 2013). ed. / Matthias Felleisen; Philippa Gardner. London : Springer Verlag, 2013. p. 411-430 (Lecture Notes in Computer Science; Vol. 7792).

Research output: Scientific - peer-reviewConference contribution

@inbook{851a242a52c54ff6a839e5187b284d1a,
title = "Taming confusion for modeling and implementing probabilistic concurrent systems",
abstract = "In concurrent systems, the choice of executing the next transition depends both on the timing between the agents that make independent or collaborative interactions available, and on the conflicts (nondeterministic choices) with other transitions. This creates a challenging modeling and implementation problem. When the system needs to make also probabilistic choices, the situation becomes even more complicated. We use the model of Petri nets to demonstrate the modeling and implementation problem. The proposed solution involves adding sequential observers called agents to the Petri net structure. Distributed probabilistic choices are facilitated in the presence of concurrency and nondeterminism, by selecting agents that make the choices, while guaranteeing that their view is temporarily stable. We provide a distributed scheduling algorithm for implementing a system that allows distributed probabilistic choice.",
keywords = "EC Grant Agreement nr.: FP7/295261, EC Grant Agreement nr.: FP7/318490, METIS-296392, IR-85506, EC Grant Agreement nr.: FP7/2007-2013, EWI-23248",
author = "Katoen, {Joost P.} and Doron Peled",
note = "eemcs-eprint-23248",
year = "2013",
month = "3",
doi = "10.1007/978-3-642-37036-6_23",
isbn = "978-3-642-37035-9",
series = "Lecture Notes in Computer Science",
publisher = "Springer Verlag",
pages = "411--430",
editor = "Matthias Felleisen and Philippa Gardner",
booktitle = "Proceedings of the 22nd European Symposium on Programming (ESOP 2013)",

}

Katoen, JP & Peled, D 2013, Taming confusion for modeling and implementing probabilistic concurrent systems. in M Felleisen & P Gardner (eds), Proceedings of the 22nd European Symposium on Programming (ESOP 2013). Lecture Notes in Computer Science, vol. 7792, Springer Verlag, London, pp. 411-430, 22nd European Symposium on Programming, ESOP 2013, Rome, Italy, 16-24 March. DOI: 10.1007/978-3-642-37036-6_23

Taming confusion for modeling and implementing probabilistic concurrent systems. / Katoen, Joost P.; Peled, Doron.

Proceedings of the 22nd European Symposium on Programming (ESOP 2013). ed. / Matthias Felleisen; Philippa Gardner. London : Springer Verlag, 2013. p. 411-430 (Lecture Notes in Computer Science; Vol. 7792).

Research output: Scientific - peer-reviewConference contribution

TY - CHAP

T1 - Taming confusion for modeling and implementing probabilistic concurrent systems

AU - Katoen,Joost P.

AU - Peled,Doron

N1 - eemcs-eprint-23248

PY - 2013/3

Y1 - 2013/3

N2 - In concurrent systems, the choice of executing the next transition depends both on the timing between the agents that make independent or collaborative interactions available, and on the conflicts (nondeterministic choices) with other transitions. This creates a challenging modeling and implementation problem. When the system needs to make also probabilistic choices, the situation becomes even more complicated. We use the model of Petri nets to demonstrate the modeling and implementation problem. The proposed solution involves adding sequential observers called agents to the Petri net structure. Distributed probabilistic choices are facilitated in the presence of concurrency and nondeterminism, by selecting agents that make the choices, while guaranteeing that their view is temporarily stable. We provide a distributed scheduling algorithm for implementing a system that allows distributed probabilistic choice.

AB - In concurrent systems, the choice of executing the next transition depends both on the timing between the agents that make independent or collaborative interactions available, and on the conflicts (nondeterministic choices) with other transitions. This creates a challenging modeling and implementation problem. When the system needs to make also probabilistic choices, the situation becomes even more complicated. We use the model of Petri nets to demonstrate the modeling and implementation problem. The proposed solution involves adding sequential observers called agents to the Petri net structure. Distributed probabilistic choices are facilitated in the presence of concurrency and nondeterminism, by selecting agents that make the choices, while guaranteeing that their view is temporarily stable. We provide a distributed scheduling algorithm for implementing a system that allows distributed probabilistic choice.

KW - EC Grant Agreement nr.: FP7/295261

KW - EC Grant Agreement nr.: FP7/318490

KW - METIS-296392

KW - IR-85506

KW - EC Grant Agreement nr.: FP7/2007-2013

KW - EWI-23248

U2 - 10.1007/978-3-642-37036-6_23

DO - 10.1007/978-3-642-37036-6_23

M3 - Conference contribution

SN - 978-3-642-37035-9

T3 - Lecture Notes in Computer Science

SP - 411

EP - 430

BT - Proceedings of the 22nd European Symposium on Programming (ESOP 2013)

PB - Springer Verlag

ER -

Katoen JP, Peled D. Taming confusion for modeling and implementing probabilistic concurrent systems. In Felleisen M, Gardner P, editors, Proceedings of the 22nd European Symposium on Programming (ESOP 2013). London: Springer Verlag. 2013. p. 411-430. (Lecture Notes in Computer Science). Available from, DOI: 10.1007/978-3-642-37036-6_23