Search

Your search keyword '"order discrepancies"' showing total 2 results
Start Over Descriptor "order discrepancies"
2 results on '"order discrepancies"'

1. QUANTIFYING THE DISCORD:: ORDER DISCREPANCIES IN MESSAGE SEQUENCE CHARTS.

Author

ELKIND, EDITH, GENEST, BLAISE, PELED, DORON, and SPOLETINI, PAOLA

Subjects
*FORMALISM (Literary analysis), *COMPUTER network protocols, *MESSAGE design logic theory, *SEQUENCE (Linguistics), *ORDER-disorder models, *TELECOMMUNICATION systems, *SEMANTICS, *INTUITION (Computer system)
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 temporal order of the messages. We introduce the concept of discord to quantify the discrepancies between the intuition and the semantics of the ordering between messages in different nodes of an HMSC. We study the algorithmic properties of this concept: we show that while the discord of a pair of messages is hard to compute in general, the problem 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. [ABSTRACT FROM AUTHOR]

Published
2010
Full Text
View/download PDF

2. Quantifying the discord: Order discrepancies in Message Sequence Charts

Author

Paola Spoletini, Doron Peled, Edith Elkind, Blaise Genest, Nanayang Technological University (NTU), Distributed and Iterative Algorithms for the Management of Telecommunications Systems (DISTRIBCOM), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria), Image & Pervasive Access Lab (IPAL), National University of Singapore (NUS)-Agency for science, technology and research [Singapore] (A*STAR)-Centre National de la Recherche Scientifique (CNRS)-Institute for Infocomm Research - I²R [Singapore], Department of Computer Science [Bar Ilan], Bar-Ilan University [Israël], Department of the Sciences of Culture, Politics and Information (DSCPI), Universitá degli Studi dell’Insubria = University of Insubria [Varese] (Uninsubria), Nanayang Technological University, Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Rennes – Bretagne Atlantique, National University of Singapore (NUS)-MATHEMATIQUES, SCIENCES ET TECHNOLOGIES DE L'INFORMATION ET DE LA COMMUNICATION (UJF)-Agency for science, technology and research [Singapore] (A*STAR)-Centre National de la Recherche Scientifique (CNRS)-Institute for Infocomm Research - I²R [Singapore], and Universitá degli Studi dell’Insubria

Subjects
Sequence, Theoretical computer science, Computer science, discord, message sequence charts, order discrepancies, Message passing, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], Order (ring theory), Transitive closure, 020207 software engineering, order discrepancies, 0102 computer and information sciences, 02 engineering and technology, 16. Peace & justice, message sequence charts, 01 natural sciences, Rotation formalisms in three dimensions, Race condition, Constant (computer programming), discord, 010201 computation theory & mathematics, Computer Science (miscellaneous), 0202 electrical engineering, electronic engineering, information engineering, Order (group theory), Algorithm
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 temporal order of the messages. We introduce the concept of discord to quantify the discrepancies between the intuition and the semantics of the ordering between messages in different nodes of an HMSC. We study the algorithmic properties of this concept: we show that while the discord of a pair of messages is hard to compute in general, the problem 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.

Published
2010

Catalog

Books, media, physical & digital resources
See catalog results