The Experts below are selected from a list of 15705 Experts worldwide ranked by ideXlab platform

Doron Peled - One of the best experts on this subject based on the ideXlab platform.

  • QUANTIFYING THE DISCORD: ORDER DISCREPANCIES IN Message Sequence CHARTS
    International Journal of Foundations of Computer Science, 2010
    Co-Authors: Edith Elkind, Blaise Genest, Doron Peled, Paola Spoletini
    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.

  • Quantifying the discord: Order discrepancies in Message Sequence Charts
    International Journal of Foundations of Computer Science, 2010
    Co-Authors: Edith Elkind, Blaise Genest, Doron Peled, Paola Spoletini
    Abstract:

    Edith Elkind, Blaise Genest, Doron Peled, and Paola Spoletini. \newblock Quantifying the discord: Order discrepancies in Message Sequence Charts, special issue of ATVA 2007. \newblock {\em International Journal of Foundations of Computer Science (IJFCS)} 21(2): 211-233, WorldSciNet, 2010.

  • quantifying the discord order discrepancies in Message Sequence charts
    Automated Technology for Verification and Analysis, 2007
    Co-Authors: Edith Elkind, Blaise Genest, Doron Peled, Paola Spoletini
    Abstract:

    Message Sequence Charts (MSCs) and High-level Message Sequence Charts (HMSC) are formalisms used to describe scenarios of Message passing protocols. We propose using Allen's logic to study the temporal order of the Messages. We introduce the concept of discord to quantify the order discrepancies between Messages in different nodes of an HMSC and study its algorithmic properties. We show that while 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.

  • ATVA - Quantifying the discord: order discrepancies in Message Sequence charts
    Automated Technology for Verification and Analysis, 2007
    Co-Authors: Edith Elkind, Blaise Genest, Doron Peled, Paola Spoletini
    Abstract:

    Message Sequence Charts (MSCs) and High-level Message Sequence Charts (HMSC) are formalisms used to describe scenarios of Message passing protocols. We propose using Allen's logic to study the temporal order of the Messages. We introduce the concept of discord to quantify the order discrepancies between Messages in different nodes of an HMSC and study its algorithmic properties. We show that while 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.

  • Lectures on Concurrency and Petri Nets - Message Sequence Charts
    Lectures on Concurrency and Petri Nets, 2004
    Co-Authors: Blaise Genest, Anca Muscholl, Doron Peled
    Abstract:

    Message Sequence charts (MSC) are a graphical notation standardized by the ITU and used for the description of communication scenarios between asynchronous processes. This survey compares MSCs and communicating finite-state automata, presenting two fundamental validation problems on MSCs, model-checking and implementability.

P S Thiagarajan - One of the best experts on this subject based on the ideXlab platform.

  • causal Message Sequence charts
    Theoretical Computer Science, 2009
    Co-Authors: Thomas Gazagnaire, Loic Helouet, Blaise Genest, P S Thiagarajan, Shaofa Yang
    Abstract:

    Scenario languages based on Message Sequence Charts (MSCs) have been widely studied in the last decade. The high expressive power of MSCs renders many basic problems concerning these languages undecidable. However, several of these problems are decidable for languages that possess a behavioral property called ''existentially bounded''. Unfortunately, collections of scenarios outside this class are frequently exhibited by systems such as sliding window protocols. We propose here an extension of MSCs called causal Message Sequence Charts and a natural mechanism for defining languages of causal MSCs called causal HMSCs (CaHMSCs). These languages preserve decidable properties without requiring existential bounds. Further, they can model collections of scenarios generated by sliding window protocols. We establish here the basic theory of CaHMSCs as well as the expressive power and complexity of decision procedures for various subclasses of CaHMSCs. We also illustrate the modeling power of our formalism with the help of a realistic example based on the TCP sliding window feature.

  • causal Message Sequence charts
    International Conference on Concurrency Theory, 2007
    Co-Authors: Thomas Gazagnaire, Loic Helouet, Blaise Genest, P S Thiagarajan, Shaofa Yang
    Abstract:

    Scenario languages based on Message Sequence Charts (MSCs) and related notations have been widely studied in the last decade [14,13,2,9,6,12,8]. The high expressive power of scenarios renders many basic problems concerning these languages undecidable. The most expressive class for which several problems are known to be decidable is one which possesses a behavioral property called "existentially bounded". However, scenarios outside this class are frequently exhibited by asynchronous distributed systems such as sliding window protocols. We propose here an extension of MSCs called Causal Message Sequence Charts, which preserves decidability without requiring existential bounds. Interestingly, it can also model scenarios from sliding window protocols. We establish the expressive power and complexity of decision procedures for various subclasses of Causal Message Sequence Charts.

  • Causal Message Sequence charts
    2007
    Co-Authors: Thomas Gazagnaire, Loic Helouet, Blaise Genest, Shaofa Yang, P S Thiagarajan
    Abstract:

    Properties of scenario languages (Message Sequence Charts, Live Sequence Charts, UML's Sequence diagrams) have been widely studied in the last decade. Scenario languages embed the expressive power of Mazurkiewicz traces, and consequently, several problems such as model checking are undecidable for these languages. Despite their expressive power, most of scenario languages can only model finitely generated behaviors that can be described as the concatenation of patterns from a finite set. However, non-finitely generated behaviors such as sliding windows frequently occur in asynchronous distributed systems. Several extensions of Message Sequence Charts have been proposed to capture non-finitely generated behaviors, but these variants embed the expressive power of automata communicating via unbounded channels (and thus of Turing Machines), making their analysis even more intractable. We propose a new extension of Message Sequence Charts that can model non-finitely generated MSC languages without embedding the expressive power of communicating automata, and study its properties.

  • Message Sequence charts
    UML for real, 2003
    Co-Authors: David Harel, P S Thiagarajan
    Abstract:

    Message Sequence charts (MSCs) constitute an attractive visual formalism that is widely used to capture system requirements during the early design stages in domains such as telecommunication software. A version of MSCs called Sequence diagrams is one of the behavioral diagram types adopted in the UML. In this chapter we survey MSCs and their extensions. In particular, we discuss high level MSCs, which allow MSCs to be combined in various regular ways, and the more recent mechanism of communicating transaction processes, which can be used to structure Sequence charts to capture system behaviors more directly. We also discuss in some detail live Sequence charts (LSCs), a multi-modal extension of MSCs with considerably richer expressive power, and the play-in/out method that makes it possible to use LSCs directly as an executable specification.

  • on Message Sequence graphs and finitely generated regular msc languages
    International Colloquium on Automata Languages and Programming, 2000
    Co-Authors: Jesper G. Henriksen, Madhavan Mukund, Narayan K Kumar, P S Thiagarajan
    Abstract:

    Message Sequence Charts (MSCs) are an attractive visual formalism widely used to capture system requirements during the early design stages in domains such as telecommunication software. A standard method to describe multiple communication scenarios is to use Message Sequence graphs (MSGs). A Message Sequence graph allows the protocol designer to write a finite specification which combines MSCs using basic operations such as branching choice, composition and iteration. The MSC languages described by MSGs are not necessarily regular in the sense of [HM+99]. We characterize here the class of regular MSC languages that are MSG-definable in terms of a notion called finitely generated MSC languages. We show that a regular MSC language is MSG-definable if and only if it is finitely generated. In fact we show that the subclass of "bounded" MSGs defined in [AY99] exactly capture the class of finitely generated regular MSC languages.

Bikram Sengupta - One of the best experts on this subject based on the ideXlab platform.

  • symbolic Message Sequence charts
    ACM Transactions on Software Engineering and Methodology, 2012
    Co-Authors: Abhik Roychoudhury, Ankit Goel, Bikram Sengupta
    Abstract:

    Message Sequence charts (MSCs) are a widely used visual formalism for scenario-based specifications of distributed reactive systems. In its conventional usage, an MSC captures an interaction snippet between concrete objects in the system. This leads to voluminous specifications when the system contains several objects that are behaviorally similar. MSCs also play an important role in the model-based testing of reactive systems, where they may be used for specifying (partial) system behaviors, describing test generation criteria, or representing test cases. However, since the number of processes in a MSC specification are fixed, model-based testing of systems consisting of process classes may involve a significant amount of rework: for example, reconstructing system models, or regenerating test cases for systems differing only in the number of processes of various types. In this article we propose a scenario-based notation, called symbolic Message Sequence charts (SMSCs), for modeling, simulation, and testing of process classes. SMSCs are a lightweight syntactic and semantic extension of MSCs where, unlike MSCs, a SMSC lifeline can denote some/all objects from a collection. Our extensions give us substantially more modeling power. Moreover, we present an abstract execution semantics for (structured collections of) SMSCs. This allows us to validate MSC-based system models capturing interactions between large, or even unbounded, number of objects. Finally, we describe a SMSC-based testing methodology for process classes, which allows generation of test cases for new object configurations with minimal rework. Since our SMSC extensions are only concerned with MSC lifelines, we believe that they can be integrated into existing standards such as UML 2.0. We illustrate our SMSC-based framework for modeling, simulation, and testing of process classes using a weather-update controller case-study from NASA.

  • symbolic Message Sequence charts
    Foundations of Software Engineering, 2007
    Co-Authors: Abhik Roychoudhury, Ankit Goel, Bikram Sengupta
    Abstract:

    Message Sequence Charts (MSCs) are a widely used visual formalism for scenario-based specifications of distributed reactive systems. In its conventional usage, an MSC captures an interaction snippet between concrete objects in the system. This leads to voluminous specifications when the system contains several objectsthat are behaviorally similar. In this paper, we propose a lightweight syntactic and semantic extension of MSCs, called Symbolic MSCs or SMSCs, where an MSC lifeline can denote some/all objects from a collection. Our extensions give us substantially more modeling power. Moreover, we present a symbolic execution semantics for (structured collections of) our extended MSCs. This allows us to validate MSC-based system models capturing interactions between large, or even unbounded, number of objects. Since our extensions are only concerned with MSC lifelines, we believe that they can be integrated into existing standards such as UML 2.0.

  • Triggered Message Sequence Charts
    IEEE Transactions on Software Engineering, 2006
    Co-Authors: Bikram Sengupta, Rance Cleaveland
    Abstract:

    This paper introduces triggered Message Sequence charts (TMSCs), a graphical, mathematically well-founded framework for capturing scenario-based system requirements of distributed systems. Like Message Sequence charts (MSCs), TMSCs are graphical depictions of scenarios, or exchanges of Messages between processes in a distributed system. Unlike MSCs, however, TMSCs are equipped with a notion of trigger that permits requirements to be made conditional, a notion of partiality indicating that a scenario may be subsequently extended, and a notion of refinement for assessing whether or not a more detailed specification correctly elaborates on a less detailed one. The TMSC notation also includes a collection of composition operators allowing structure to be introduced into scenario specifications so that interactions among different scenarios may be studied. In the first part of this paper, TMSCs are introduced and their use in support of requirements modeling is illustrated via two extended examples. The second part develops the mathematical underpinnings of the language

  • ICDCIT - Secure requirements elicitation through triggered Message Sequence charts
    Distributed Computing and Internet Technology, 2004
    Co-Authors: Arnab Ray, Bikram Sengupta, Rance Cleaveland
    Abstract:

    This paper argues for performing information-flow-based securityanalysis in the first phase of the software development life cycle itself ie in the requirements elicitation phase Message Sequence Charts (MSC)s have been widely accepted as a formal scenario-based visual notation for writing down requirements In this paper, we discuss a method for checking if a TMSC (Triggered Message Sequence Chart), a recently propsed enhancement to classical MSCs, satisifes one of the most important information flow properties namely non-interference.

  • TRIM: A tool for Triggered Message Sequence Charts
    Lecture Notes in Computer Science, 2003
    Co-Authors: Bikram Sengupta, Rance Cleaveland
    Abstract:

    TRIM is a tool for analyzing system requirements expressed using Triggered Message Sequence Charts (TMSCs). TMSCs enhance MSCs with capabilities for expressing conditional and partial behavior and with a refinement ordering. This paper shows how the Concurrency Workbench of the New Century may be adapted to check refinements between TMSC specifications.

Rance Cleaveland - One of the best experts on this subject based on the ideXlab platform.

  • Triggered Message Sequence Charts
    IEEE Transactions on Software Engineering, 2006
    Co-Authors: Bikram Sengupta, Rance Cleaveland
    Abstract:

    This paper introduces triggered Message Sequence charts (TMSCs), a graphical, mathematically well-founded framework for capturing scenario-based system requirements of distributed systems. Like Message Sequence charts (MSCs), TMSCs are graphical depictions of scenarios, or exchanges of Messages between processes in a distributed system. Unlike MSCs, however, TMSCs are equipped with a notion of trigger that permits requirements to be made conditional, a notion of partiality indicating that a scenario may be subsequently extended, and a notion of refinement for assessing whether or not a more detailed specification correctly elaborates on a less detailed one. The TMSC notation also includes a collection of composition operators allowing structure to be introduced into scenario specifications so that interactions among different scenarios may be studied. In the first part of this paper, TMSCs are introduced and their use in support of requirements modeling is illustrated via two extended examples. The second part develops the mathematical underpinnings of the language

  • ICDCIT - Secure requirements elicitation through triggered Message Sequence charts
    Distributed Computing and Internet Technology, 2004
    Co-Authors: Arnab Ray, Bikram Sengupta, Rance Cleaveland
    Abstract:

    This paper argues for performing information-flow-based securityanalysis in the first phase of the software development life cycle itself ie in the requirements elicitation phase Message Sequence Charts (MSC)s have been widely accepted as a formal scenario-based visual notation for writing down requirements In this paper, we discuss a method for checking if a TMSC (Triggered Message Sequence Chart), a recently propsed enhancement to classical MSCs, satisifes one of the most important information flow properties namely non-interference.

  • TRIM: A tool for Triggered Message Sequence Charts
    Lecture Notes in Computer Science, 2003
    Co-Authors: Bikram Sengupta, Rance Cleaveland
    Abstract:

    TRIM is a tool for analyzing system requirements expressed using Triggered Message Sequence Charts (TMSCs). TMSCs enhance MSCs with capabilities for expressing conditional and partial behavior and with a refinement ordering. This paper shows how the Concurrency Workbench of the New Century may be adapted to check refinements between TMSC specifications.

  • CAV - TRIM: A Tool for Triggered Message Sequence Charts
    Computer Aided Verification, 2003
    Co-Authors: Bikram Sengupta, Rance Cleaveland
    Abstract:

    TRIM is a tool for analyzing system requirements expressed using Triggered Message Sequence Charts (TMSCs). TMSCs enhance MSCs with capabilities for expressing conditional and partial behavior and with a refinement ordering. This paper shows how the Concurrency Workbench of the New Century may be adapted to check refinements between TMSC specifications.

  • Triggered Message Sequence charts
    ACM SIGSOFT Software Engineering Notes, 2002
    Co-Authors: Bikram Sengupta, Rance Cleaveland
    Abstract:

    We propose an extension to Message Sequence Charts called Triggered Message Sequence Charts (TMSCs) that are intended to capture system specifications involving nondeterminism in the form of conditional scenarios. The visual syntax of TMSCs closely resembles that of MSCs; the semantics allows us to translate a TMSC specification into a framework that supports a notion of refinement based on Denicola's and Hennessy's must preorder. A simple but non-trivial example illustrates the utility of our extension to MSCs.

P. Madhusudan - One of the best experts on this subject based on the ideXlab platform.

  • FSTTCS - Dynamic Message Sequence Charts
    FST TCS 2002: Foundations of Software Technology and Theoretical Computer Science, 2002
    Co-Authors: Martin Leucker, P. Madhusudan, Supratik Mukhopadhyay
    Abstract:

    We introduce a formalism to specify classes of MSCs over an unbounded number of processes. The formalism can describe many interesting behaviours of dynamically changing networks of processes. Moreover, it strictly includes the formalism of Message Sequence Graphs studied in the literature to describe MSCs over a fixed finite set of processes. Our main result is that model-checking of MSCs described in this formalism against a suitable monadic-second order logic is decidable.

  • dynamic Message Sequence charts
    Foundations of Software Technology and Theoretical Computer Science, 2002
    Co-Authors: P. Madhusudan, Martin Leucker, Supratik Mukhopadhyay
    Abstract:

    We introduce a formalism to specify classes of MSCs over an unbounded number of processes. The formalism can describe many interesting behaviours of dynamically changing networks of processes. Moreover, it strictly includes the formalism of Message Sequence Graphs studied in the literature to describe MSCs over a fixed finite set of processes. Our main result is that model-checking of MSCs described in this formalism against a suitable monadic-second order logic is decidable.

  • beyond Message Sequence graphs
    Foundations of Software Technology and Theoretical Computer Science, 2001
    Co-Authors: P. Madhusudan, B. Meenakshi
    Abstract:

    We study the model-checking problem for classes of Message Sequence charts (MSCs) defined by two extensions of Message Sequence graphs (MSGs). These classes subsume the class of regular MSC languages. We show that the model checking problem for these extended Message Sequence graphs against monadic second-order specifications is decidable. Moreover, we present two ways to model-check the extended classes -- one extends the proof for MSGs while the other extends the proof for regular MSC languages.

  • FSTTCS - Beyond Message Sequence Graphs
    FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science, 2001
    Co-Authors: P. Madhusudan, B. Meenakshi
    Abstract:

    We study the model-checking problem for classes of Message Sequence charts (MSCs) defined by two extensions of Message Sequence graphs (MSGs). These classes subsume the class of regular MSC languages. We show that the model checking problem for these extended Message Sequence graphs against monadic second-order specifications is decidable. Moreover, we present two ways to model-check the extended classes -- one extends the proof for MSGs while the other extends the proof for regular MSC languages.

  • reasoning about sequential and branching behaviours of Message Sequence graphs
    International Colloquium on Automata Languages and Programming, 2001
    Co-Authors: P. Madhusudan
    Abstract:

    We study the model-checking problem of Message-Sequence graphs (MSGs). In the sequential setting, we consider the set of Message-Sequence charts (MSCs) represented by an MSG and tackle specifications given in monadic second-order logic. We show that this problem, without any restrictions on the MSGs, is decidable. We then turn to branching behaviours of MSGs, define a notion of an unfolding of an MSG, and show that the model-checking problem on unfoldings is also decidable. Our results are stronger and imply that, over an appropriate universe, satisfiability and synthesis of MSCs and MSGs, respectively, are decidable.