Abstract | ||
---|---|---|
An effective way to assemble partial views of a distributed system is to compute their product. Given two Message Sequence
Graphs, we address the problem of computing a Message Sequence Graph that generates the product of their languages, when possible.
Since all MSCs generated by a Message Sequence Graph G may be run within fixed bounds on the message channels (that is, G is existentially bounded), a subproblem is to decide whether the considered product is existentially bounded. We show that
this question is undecidable, but turns co-NP-complete in the restricted case where all synchronizations belong to the same
process. This is the first positive result on the decision of existential boundedness. We propose sufficient conditions under
which a Message Sequence Graph representing the product can be constructed.
|
Year | DOI | Venue |
---|---|---|
2008 | 10.1007/978-3-540-78499-9_32 | Foundations of Software Science and Computation Structure |
Keywords | Field | DocType |
message sequence graph,restricted case,fixed bound,considered product,twomessage sequence graphs,existential boundedness,positive result,message channel,message sequence graph g,partial view,message sequence chart,distributed system | Graph,Discrete mathematics,Combinatorics,Sequence diagram,Computer science,Communication channel,Bounded function,Undecidable problem | Conference |
Volume | ISSN | ISBN |
4962 | 0302-9743 | 3-540-78497-7 |
Citations | PageRank | References |
3 | 0.44 | 18 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Philippe Darondeau | 1 | 715 | 77.04 |
Blaise Genest | 2 | 304 | 25.09 |
Loïc Hélouët | 3 | 281 | 25.37 |