Paper Info
Title
Quantifying the Discord: Order Discrepancies in Message Sequence Charts
Abstract
Message Sequence Charts (MSCs) and High-level Message Sequence Charts (HMSCs) are formalisms used to describe scenarios of message passing protocols. We propose using Allen's logic to represent the t emporal order of the messages. We introduce the concept of discord to quantify the discrepancies be- tween the intuition and the semantics of the ordering between messages in d- ifferent nodes of an HMSC. We study its algorithmic properties: we show that while the discord of a pair of messages is hard to compute in general, the prob- lem becomes polynomial-time computable if the number of nodes of the HMSC or the number of processes is constant. Moreover, for a given HMSC, it is always computationally easy to identify a pair of messages that exhibits the worst-case discord and compute the discord of this pair.
Year
DOI
Venue
2010
10.1007/978-3-540-75596-8_27
International Journal of Foundations of Computer Science
Keywords
Field
DocType
temporal order,high-level message sequence charts,polynomial-time computable,different node,order discrepancy,worst-case discord,message sequence chart,algorithmic property,message sequence charts
Race condition,Path (graph theory),Computer science,Algorithm,Theoretical computer science,Transitive closure,Rotation formalisms in three dimensions,Message passing
Journal
Volume
Issue
ISSN
21
2
0302-9743
ISBN
Citations 
PageRank 
3-540-75595-0
2
0.38
References 
Authors
17
4
Name
Order
Citations
PageRank
Edith Elkind11340120.81
Blaise Genest230425.09
Doron Peled33357273.18
Paola Spoletini459044.88