Partial Order Techniques for Distributed Discrete Event Systems: Why You Cannot Avoid Using Them View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2007-09

AUTHORS

Eric Fabre, Albert Benveniste

ABSTRACT

Monitoring or diagnosis of large scale distributed Discrete Event Systems with asynchronous communication is a demanding task. Ensuring that the methods developed for Discrete Event Systems properly scale up to such systems is a challenge. In this paper we explain why the use of partial orders cannot be avoided in order to achieve this objective. To support this claim, we try to push classical techniques (parallel composition of automata and languages) to their limits and we eventually discover that partial order models arise at some point. We focus on on-line techniques, where a key difficulty is the choice of proper data structures to represent the set of all runs of a distributed system, in a modular way. We discuss the use of previously known structures such as execution trees and unfoldings. We propose a novel and more compact data structure called “trellis.” Then, we show how all the above data structures can be used in performing distributed monitoring and diagnosis. The techniques reported here were used in an industrial context for fault management and alarm correlation in telecommunications networks. This paper is an extended and improved version of the plenary address that was given by the second author at WODES’ 2006. More... »

PAGES

355-403

References to SciGraph publications

  • 1993. Using unfoldings to avoid the state explosion problem in the verification of asynchronous circuits in COMPUTER AIDED VERIFICATION
  • 2006. Distributed Unfolding of Petri Nets in FOUNDATIONS OF SOFTWARE SCIENCE AND COMPUTATION STRUCTURES
  • 1993. Symbolic Model Checking in NONE
  • 2000-01. Coordinated Decentralized Protocols for Failure Diagnosis of Discrete Event Systems in DISCRETE EVENT DYNAMIC SYSTEMS
  • 2003-07. On the Effect of Communication Delays in Failure Diagnosis of Decentralized Discrete Event Systems in DISCRETE EVENT DYNAMIC SYSTEMS
  • 2003-05-27. Distributed Diagnosis of Discrete-Event Systems Using Petri Nets in APPLICATIONS AND THEORY OF PETRI NETS 2003
  • 2005. Branching Cells as Local States for Event Structures and Nets: Probabilistic Applications in FOUNDATIONS OF SOFTWARE SCIENCE AND COMPUTATIONAL STRUCTURES
  • 2005-03. Distributed Monitoring of Concurrent and Asynchronous Systems* in DISCRETE EVENT DYNAMIC SYSTEMS
  • 2002-07. A General Architecture for Decentralized Supervisory Control of Discrete-Event Systems in DISCRETE EVENT DYNAMIC SYSTEMS
  • 2004. UML Specification of a Generic Model for Fault Diagnosis of Telecommunication Networks in TELECOMMUNICATIONS AND NETWORKING - ICT 2004
  • 2005. Time Supervision of Concurrent Systems Using Symbolic Unfoldings of Time Petri Nets in FORMAL MODELING AND ANALYSIS OF TIMED SYSTEMS
  • 1985. Categories of models for concurrency in SEMINAR ON CONCURRENCY
  • 2006-01. Hierarchical Fault Diagnosis for Discrete-Event Systems under Global Consistency in DISCRETE EVENT DYNAMIC SYSTEMS
  • 2003. Diagnosis of Active Systems, Principles and Techniques in NONE
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s10626-007-0016-1

    DOI

    http://dx.doi.org/10.1007/s10626-007-0016-1

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1040863856


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0806", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information Systems", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "University of Rennes 1", 
              "id": "https://www.grid.ac/institutes/grid.410368.8", 
              "name": [
                "IRISA-INRIA, Campus de Beaulieu, 35042, Rennes, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Fabre", 
            "givenName": "Eric", 
            "id": "sg:person.011362250353.22", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011362250353.22"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Rennes 1", 
              "id": "https://www.grid.ac/institutes/grid.410368.8", 
              "name": [
                "IRISA-INRIA, Campus de Beaulieu, 35042, Rennes, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Benveniste", 
            "givenName": "Albert", 
            "id": "sg:person.011174600625.42", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011174600625.42"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1016/j.ic.2005.10.001", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005364420"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0004-3702(02)00123-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005538853"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-15670-4_12", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005749967", 
              "https://doi.org/10.1007/3-540-15670-4_12"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://app.dimensions.ai/details/publication/pub.1006790306", 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-94-017-0257-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006790306", 
              "https://doi.org/10.1007/978-94-017-0257-7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-94-017-0257-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006790306", 
              "https://doi.org/10.1007/978-94-017-0257-7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4615-3190-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007275442", 
              "https://doi.org/10.1007/978-1-4615-3190-6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4615-3190-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007275442", 
              "https://doi.org/10.1007/978-1-4615-3190-6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4615-3190-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007275442", 
              "https://doi.org/10.1007/978-1-4615-3190-6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.ipl.2004.01.004", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009384675"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1023/a:1024007808984", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009550342", 
              "https://doi.org/10.1023/a:1024007808984"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0890-5401(87)90032-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010757447"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.3182/20050703-6-cz-1902.00299", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011579293"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-27824-5_111", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012060962", 
              "https://doi.org/10.1007/978-3-540-27824-5_111"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-27824-5_111", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012060962", 
              "https://doi.org/10.1007/978-3-540-27824-5_111"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0004-3702(86)90072-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014162908"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0004-3702(86)90072-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014162908"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.artint.2005.08.002", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014922753"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.artint.2005.08.002", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014922753"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.2514/3.3166", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015705383"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1023/a:1008335115538", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019019323", 
              "https://doi.org/10.1023/a:1008335115538"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-44919-1_21", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1020288080", 
              "https://doi.org/10.1007/3-540-44919-1_21"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-44919-1_21", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1020288080", 
              "https://doi.org/10.1007/3-540-44919-1_21"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11690634_9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1020581321", 
              "https://doi.org/10.1007/11690634_9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11690634_9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1020581321", 
              "https://doi.org/10.1007/11690634_9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10626-005-5238-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022113780", 
              "https://doi.org/10.1007/s10626-005-5238-5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10626-005-5238-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022113780", 
              "https://doi.org/10.1007/s10626-005-5238-5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-56496-9_14", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1034555011", 
              "https://doi.org/10.1007/3-540-56496-9_14"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(81)90112-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035972534"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0004-3702(99)00019-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039253583"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1023/a:1015625600613", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040266495", 
              "https://doi.org/10.1023/a:1015625600613"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11603009_16", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1044832900", 
              "https://doi.org/10.1007/11603009_16"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11603009_16", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1044832900", 
              "https://doi.org/10.1007/11603009_16"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11603009_16", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1044832900", 
              "https://doi.org/10.1007/11603009_16"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10626-006-6178-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045675032", 
              "https://doi.org/10.1007/s10626-006-6178-4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10626-006-6178-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045675032", 
              "https://doi.org/10.1007/s10626-006-6178-4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-31982-5_6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051417327", 
              "https://doi.org/10.1007/978-3-540-31982-5_6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-31982-5_6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051417327", 
              "https://doi.org/10.1007/978-3-540-31982-5_6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/2.84874", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061106260"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/9.412626", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061244618"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tac.2003.811249", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061475291"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tase.2006.879916", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061514739"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tsmca.2005.853503", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061795124"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1142/s0218213002000927", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062964293"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s1474-6670(17)30767-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1085385558"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/wodes.2006.1678445", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1093444582"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/cdc.2005.1583171", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1093517029"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/wodes.2006.1678440", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1093684062"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/acc.2006.1657693", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1094040585"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/cdc.2005.1583176", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1094184955"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/wodes.2002.1167684", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1095203459"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/wodes.2002.1167685", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1095476431"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/acc.2006.1657694", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1095493517"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.5220/0002447200470057", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1099392233"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2007-09", 
        "datePublishedReg": "2007-09-01", 
        "description": "Monitoring or diagnosis of large scale distributed Discrete Event Systems with asynchronous communication is a demanding task. Ensuring that the methods developed for Discrete Event Systems properly scale up to such systems is a challenge. In this paper we explain why the use of partial orders cannot be avoided in order to achieve this objective. To support this claim, we try to push classical techniques (parallel composition of automata and languages) to their limits and we eventually discover that partial order models arise at some point. We focus on on-line techniques, where a key difficulty is the choice of proper data structures to represent the set of all runs of a distributed system, in a modular way. We discuss the use of previously known structures such as execution trees and unfoldings. We propose a novel and more compact data structure called \u201ctrellis.\u201d Then, we show how all the above data structures can be used in performing distributed monitoring and diagnosis. The techniques reported here were used in an industrial context for fault management and alarm correlation in telecommunications networks. This paper is an extended and improved version of the plenary address that was given by the second author at WODES\u2019 2006.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s10626-007-0016-1", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1136419", 
            "issn": [
              "0924-6703", 
              "1573-7594"
            ], 
            "name": "Discrete Event Dynamic Systems", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "3", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "17"
          }
        ], 
        "name": "Partial Order Techniques for Distributed Discrete Event Systems: Why You Cannot Avoid Using Them", 
        "pagination": "355-403", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s10626-007-0016-1"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "c2a8e1443c10dc33e91956f16b3d8123b3d70f0862f712badbd705ff0d177c96"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1040863856"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s10626-007-0016-1", 
          "https://app.dimensions.ai/details/publication/pub.1040863856"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-15T09:16", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000376_0000000376/records_56171_00000001.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007/s10626-007-0016-1"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s10626-007-0016-1'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s10626-007-0016-1'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10626-007-0016-1'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10626-007-0016-1'


     

    This table displays all metadata directly associated to this object as RDF triples.

    204 TRIPLES      21 PREDICATES      68 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s10626-007-0016-1 schema:about anzsrc-for:08
    2 anzsrc-for:0806
    3 schema:author Nea9a84dbfd0b41ef9951c98574257a62
    4 schema:citation sg:pub.10.1007/11603009_16
    5 sg:pub.10.1007/11690634_9
    6 sg:pub.10.1007/3-540-15670-4_12
    7 sg:pub.10.1007/3-540-44919-1_21
    8 sg:pub.10.1007/3-540-56496-9_14
    9 sg:pub.10.1007/978-1-4615-3190-6
    10 sg:pub.10.1007/978-3-540-27824-5_111
    11 sg:pub.10.1007/978-3-540-31982-5_6
    12 sg:pub.10.1007/978-94-017-0257-7
    13 sg:pub.10.1007/s10626-005-5238-5
    14 sg:pub.10.1007/s10626-006-6178-4
    15 sg:pub.10.1023/a:1008335115538
    16 sg:pub.10.1023/a:1015625600613
    17 sg:pub.10.1023/a:1024007808984
    18 https://app.dimensions.ai/details/publication/pub.1006790306
    19 https://doi.org/10.1016/0004-3702(86)90072-x
    20 https://doi.org/10.1016/0304-3975(81)90112-2
    21 https://doi.org/10.1016/0890-5401(87)90032-0
    22 https://doi.org/10.1016/j.artint.2005.08.002
    23 https://doi.org/10.1016/j.ic.2005.10.001
    24 https://doi.org/10.1016/j.ipl.2004.01.004
    25 https://doi.org/10.1016/s0004-3702(02)00123-6
    26 https://doi.org/10.1016/s0004-3702(99)00019-3
    27 https://doi.org/10.1016/s1474-6670(17)30767-x
    28 https://doi.org/10.1109/2.84874
    29 https://doi.org/10.1109/9.412626
    30 https://doi.org/10.1109/acc.2006.1657693
    31 https://doi.org/10.1109/acc.2006.1657694
    32 https://doi.org/10.1109/cdc.2005.1583171
    33 https://doi.org/10.1109/cdc.2005.1583176
    34 https://doi.org/10.1109/tac.2003.811249
    35 https://doi.org/10.1109/tase.2006.879916
    36 https://doi.org/10.1109/tsmca.2005.853503
    37 https://doi.org/10.1109/wodes.2002.1167684
    38 https://doi.org/10.1109/wodes.2002.1167685
    39 https://doi.org/10.1109/wodes.2006.1678440
    40 https://doi.org/10.1109/wodes.2006.1678445
    41 https://doi.org/10.1142/s0218213002000927
    42 https://doi.org/10.2514/3.3166
    43 https://doi.org/10.3182/20050703-6-cz-1902.00299
    44 https://doi.org/10.5220/0002447200470057
    45 schema:datePublished 2007-09
    46 schema:datePublishedReg 2007-09-01
    47 schema:description Monitoring or diagnosis of large scale distributed Discrete Event Systems with asynchronous communication is a demanding task. Ensuring that the methods developed for Discrete Event Systems properly scale up to such systems is a challenge. In this paper we explain why the use of partial orders cannot be avoided in order to achieve this objective. To support this claim, we try to push classical techniques (parallel composition of automata and languages) to their limits and we eventually discover that partial order models arise at some point. We focus on on-line techniques, where a key difficulty is the choice of proper data structures to represent the set of all runs of a distributed system, in a modular way. We discuss the use of previously known structures such as execution trees and unfoldings. We propose a novel and more compact data structure called “trellis.” Then, we show how all the above data structures can be used in performing distributed monitoring and diagnosis. The techniques reported here were used in an industrial context for fault management and alarm correlation in telecommunications networks. This paper is an extended and improved version of the plenary address that was given by the second author at WODES’ 2006.
    48 schema:genre research_article
    49 schema:inLanguage en
    50 schema:isAccessibleForFree false
    51 schema:isPartOf N52a0145814c648619e50c80d5326a957
    52 N607a063081d0469aa9cfd4a73489394b
    53 sg:journal.1136419
    54 schema:name Partial Order Techniques for Distributed Discrete Event Systems: Why You Cannot Avoid Using Them
    55 schema:pagination 355-403
    56 schema:productId N0a87e527770143c2a22790b9d31be9dd
    57 N20826b5f6c2d484693c686e4b8ca260f
    58 N23033b5c964346e3bb5c3017f0542814
    59 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040863856
    60 https://doi.org/10.1007/s10626-007-0016-1
    61 schema:sdDatePublished 2019-04-15T09:16
    62 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    63 schema:sdPublisher Nf162799b5c844d3c86a30a47d8269583
    64 schema:url http://link.springer.com/10.1007/s10626-007-0016-1
    65 sgo:license sg:explorer/license/
    66 sgo:sdDataset articles
    67 rdf:type schema:ScholarlyArticle
    68 N0a87e527770143c2a22790b9d31be9dd schema:name dimensions_id
    69 schema:value pub.1040863856
    70 rdf:type schema:PropertyValue
    71 N20826b5f6c2d484693c686e4b8ca260f schema:name doi
    72 schema:value 10.1007/s10626-007-0016-1
    73 rdf:type schema:PropertyValue
    74 N23033b5c964346e3bb5c3017f0542814 schema:name readcube_id
    75 schema:value c2a8e1443c10dc33e91956f16b3d8123b3d70f0862f712badbd705ff0d177c96
    76 rdf:type schema:PropertyValue
    77 N52a0145814c648619e50c80d5326a957 schema:volumeNumber 17
    78 rdf:type schema:PublicationVolume
    79 N607a063081d0469aa9cfd4a73489394b schema:issueNumber 3
    80 rdf:type schema:PublicationIssue
    81 Nea9a84dbfd0b41ef9951c98574257a62 rdf:first sg:person.011362250353.22
    82 rdf:rest Nf2b4e00b0bc24cd2990b9f3798258c2a
    83 Nf162799b5c844d3c86a30a47d8269583 schema:name Springer Nature - SN SciGraph project
    84 rdf:type schema:Organization
    85 Nf2b4e00b0bc24cd2990b9f3798258c2a rdf:first sg:person.011174600625.42
    86 rdf:rest rdf:nil
    87 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    88 schema:name Information and Computing Sciences
    89 rdf:type schema:DefinedTerm
    90 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
    91 schema:name Information Systems
    92 rdf:type schema:DefinedTerm
    93 sg:journal.1136419 schema:issn 0924-6703
    94 1573-7594
    95 schema:name Discrete Event Dynamic Systems
    96 rdf:type schema:Periodical
    97 sg:person.011174600625.42 schema:affiliation https://www.grid.ac/institutes/grid.410368.8
    98 schema:familyName Benveniste
    99 schema:givenName Albert
    100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011174600625.42
    101 rdf:type schema:Person
    102 sg:person.011362250353.22 schema:affiliation https://www.grid.ac/institutes/grid.410368.8
    103 schema:familyName Fabre
    104 schema:givenName Eric
    105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011362250353.22
    106 rdf:type schema:Person
    107 sg:pub.10.1007/11603009_16 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044832900
    108 https://doi.org/10.1007/11603009_16
    109 rdf:type schema:CreativeWork
    110 sg:pub.10.1007/11690634_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020581321
    111 https://doi.org/10.1007/11690634_9
    112 rdf:type schema:CreativeWork
    113 sg:pub.10.1007/3-540-15670-4_12 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005749967
    114 https://doi.org/10.1007/3-540-15670-4_12
    115 rdf:type schema:CreativeWork
    116 sg:pub.10.1007/3-540-44919-1_21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020288080
    117 https://doi.org/10.1007/3-540-44919-1_21
    118 rdf:type schema:CreativeWork
    119 sg:pub.10.1007/3-540-56496-9_14 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034555011
    120 https://doi.org/10.1007/3-540-56496-9_14
    121 rdf:type schema:CreativeWork
    122 sg:pub.10.1007/978-1-4615-3190-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007275442
    123 https://doi.org/10.1007/978-1-4615-3190-6
    124 rdf:type schema:CreativeWork
    125 sg:pub.10.1007/978-3-540-27824-5_111 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012060962
    126 https://doi.org/10.1007/978-3-540-27824-5_111
    127 rdf:type schema:CreativeWork
    128 sg:pub.10.1007/978-3-540-31982-5_6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051417327
    129 https://doi.org/10.1007/978-3-540-31982-5_6
    130 rdf:type schema:CreativeWork
    131 sg:pub.10.1007/978-94-017-0257-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006790306
    132 https://doi.org/10.1007/978-94-017-0257-7
    133 rdf:type schema:CreativeWork
    134 sg:pub.10.1007/s10626-005-5238-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022113780
    135 https://doi.org/10.1007/s10626-005-5238-5
    136 rdf:type schema:CreativeWork
    137 sg:pub.10.1007/s10626-006-6178-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045675032
    138 https://doi.org/10.1007/s10626-006-6178-4
    139 rdf:type schema:CreativeWork
    140 sg:pub.10.1023/a:1008335115538 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019019323
    141 https://doi.org/10.1023/a:1008335115538
    142 rdf:type schema:CreativeWork
    143 sg:pub.10.1023/a:1015625600613 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040266495
    144 https://doi.org/10.1023/a:1015625600613
    145 rdf:type schema:CreativeWork
    146 sg:pub.10.1023/a:1024007808984 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009550342
    147 https://doi.org/10.1023/a:1024007808984
    148 rdf:type schema:CreativeWork
    149 https://app.dimensions.ai/details/publication/pub.1006790306 schema:CreativeWork
    150 https://doi.org/10.1016/0004-3702(86)90072-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1014162908
    151 rdf:type schema:CreativeWork
    152 https://doi.org/10.1016/0304-3975(81)90112-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035972534
    153 rdf:type schema:CreativeWork
    154 https://doi.org/10.1016/0890-5401(87)90032-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010757447
    155 rdf:type schema:CreativeWork
    156 https://doi.org/10.1016/j.artint.2005.08.002 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014922753
    157 rdf:type schema:CreativeWork
    158 https://doi.org/10.1016/j.ic.2005.10.001 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005364420
    159 rdf:type schema:CreativeWork
    160 https://doi.org/10.1016/j.ipl.2004.01.004 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009384675
    161 rdf:type schema:CreativeWork
    162 https://doi.org/10.1016/s0004-3702(02)00123-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005538853
    163 rdf:type schema:CreativeWork
    164 https://doi.org/10.1016/s0004-3702(99)00019-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039253583
    165 rdf:type schema:CreativeWork
    166 https://doi.org/10.1016/s1474-6670(17)30767-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1085385558
    167 rdf:type schema:CreativeWork
    168 https://doi.org/10.1109/2.84874 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061106260
    169 rdf:type schema:CreativeWork
    170 https://doi.org/10.1109/9.412626 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061244618
    171 rdf:type schema:CreativeWork
    172 https://doi.org/10.1109/acc.2006.1657693 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094040585
    173 rdf:type schema:CreativeWork
    174 https://doi.org/10.1109/acc.2006.1657694 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095493517
    175 rdf:type schema:CreativeWork
    176 https://doi.org/10.1109/cdc.2005.1583171 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093517029
    177 rdf:type schema:CreativeWork
    178 https://doi.org/10.1109/cdc.2005.1583176 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094184955
    179 rdf:type schema:CreativeWork
    180 https://doi.org/10.1109/tac.2003.811249 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061475291
    181 rdf:type schema:CreativeWork
    182 https://doi.org/10.1109/tase.2006.879916 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061514739
    183 rdf:type schema:CreativeWork
    184 https://doi.org/10.1109/tsmca.2005.853503 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061795124
    185 rdf:type schema:CreativeWork
    186 https://doi.org/10.1109/wodes.2002.1167684 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095203459
    187 rdf:type schema:CreativeWork
    188 https://doi.org/10.1109/wodes.2002.1167685 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095476431
    189 rdf:type schema:CreativeWork
    190 https://doi.org/10.1109/wodes.2006.1678440 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093684062
    191 rdf:type schema:CreativeWork
    192 https://doi.org/10.1109/wodes.2006.1678445 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093444582
    193 rdf:type schema:CreativeWork
    194 https://doi.org/10.1142/s0218213002000927 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062964293
    195 rdf:type schema:CreativeWork
    196 https://doi.org/10.2514/3.3166 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015705383
    197 rdf:type schema:CreativeWork
    198 https://doi.org/10.3182/20050703-6-cz-1902.00299 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011579293
    199 rdf:type schema:CreativeWork
    200 https://doi.org/10.5220/0002447200470057 schema:sameAs https://app.dimensions.ai/details/publication/pub.1099392233
    201 rdf:type schema:CreativeWork
    202 https://www.grid.ac/institutes/grid.410368.8 schema:alternateName University of Rennes 1
    203 schema:name IRISA-INRIA, Campus de Beaulieu, 35042, Rennes, France
    204 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...