QUANTIFYING THE DISCORD: ORDER DISCREPANCIES IN MESSAGE SEQUENCE CHARTS

摘要

Message Sequence Charts (MSCs) and High-level Message Sequence Charts (HMSCs) are formalismsnused to describe scenarios of message passing protocols. We propose using Allen’s logic to representnthe temporal order of the messages. We introduce the concept of discord to quantify the discrepanciesnbetween the intuition and the semantics of the ordering between messages in different nodes of annHMSC. We study the algorithmic properties of this concept: we show that while the discord of a pairnof messages is hard to compute in general, the problem becomes polynomial-time computable if thennumber of nodes of the HMSC or the number of processes is constant. Moreover, for a given HMSC,nit is always computationally easy to identify a pair of messages that exhibits the worst-case discordnand compute the discord of this pair.