Controllable-choice Message Sequence Graphs
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F13%3A00065934" target="_blank" >RIV/00216224:14330/13:00065934 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1007/978-3-642-36046-6_12" target="_blank" >http://dx.doi.org/10.1007/978-3-642-36046-6_12</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-642-36046-6_12" target="_blank" >10.1007/978-3-642-36046-6_12</a>
Alternative languages
Result language
angličtina
Original language name
Controllable-choice Message Sequence Graphs
Original language description
We focus on the realizability problem of Message Sequence Graphs (MSG), i.e. the problem whether a given MSG specification is correctly distributable among parallel components communicating via messages. This fundamental problem of MSG is known to be undecidable. We introduce a well motivated restricted class of MSG, so called controllable-choice MSG, and show that all its models are realizable and moreover it is decidable whether a given MSG model is a member of this class. In more detail, this class of MSG specifications admits a deadlock-free realization by overloading existing messages with additional bounded control data. We also show that the presented class is the largest known subclass of MSG that allows for deadlock-free realization.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Center of excellence - Institute for theoretical computer science (CE-ITI)</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2013
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of Mathematical and Engineering Methods in Computer Science, 8th Doctoral Workshop (MEMICS 2012), Selected Papers
ISBN
9783642360442
ISSN
0302-9743
e-ISSN
—
Number of pages
13
Pages from-to
118-130
Publisher name
Springer
Place of publication
Berlin Heidelberg
Event location
Znojmo
Event date
Jan 1, 2012
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—