Coordinated Decentralized Protocols for Failure Diagnosis of Discrete Event Systems View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2000-01

AUTHORS

Rami Debouk, Stéphane Lafortune, Demosthenis Teneketzis

ABSTRACT

We address the problem of failure diagnosis in discrete event systems with decentralized information. We propose a coordinated decentralized architecture consisting of local sites communicating with a coordinator that is responsible for diagnosing the failures occurring in the system. We extend the notion of diagnosability, originally introduced in Sampath et al. (1995) for centralized systems, to the proposed coordinated decentralized architecture. We specify three protocols that realize the proposed architecture; each protocol is defined by the diagnostic information generated at the local sites, the communication rules used by the local sites, and the coordinator's decision rule. We analyze the diagnostic properties of each protocol. We also state and prove conditions for a language to be diagnosable under each protocol. These conditions are checkable off-line. The on-line diagnostic process is carried out using the diagnosers introduced in Sampath et al. (1995) or a slight variation of these diagnosers. The key features of the proposed protocols are: (i) they achieve, each under a set of assumptions, the same diagnostic performance as the centralized diagnoser; and (ii) they highlight the “performance vs. complexity” tradeoff that arises in coordinated decentralized architectures. The correctness of two of the protocols relies on some stringent global ordering assumptions on message reception at the coordinator's site, the relaxation of which is briefly discussed. More... »

PAGES

33-86

References to SciGraph publications

  • 1994-05. Diagnosability of discrete event systems and its applications in DISCRETE EVENT DYNAMIC SYSTEMS
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1023/a:1008335115538

    DOI

    http://dx.doi.org/10.1023/a:1008335115538

    DIMENSIONS

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


    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": [
          {
            "familyName": "Debouk", 
            "givenName": "Rami", 
            "id": "sg:person.014465223505.00", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014465223505.00"
            ], 
            "type": "Person"
          }, 
          {
            "familyName": "Lafortune", 
            "givenName": "St\u00e9phane", 
            "id": "sg:person.01131403760.98", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01131403760.98"
            ], 
            "type": "Person"
          }, 
          {
            "familyName": "Teneketzis", 
            "givenName": "Demosthenis", 
            "id": "sg:person.014462715775.20", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014462715775.20"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1016/0005-1098(76)90041-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000971875"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0005-1098(76)90041-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000971875"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01441211", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002375852", 
              "https://doi.org/10.1007/bf01441211"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01441211", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002375852", 
              "https://doi.org/10.1007/bf01441211"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1214/aos/1176343654", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012552178"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0005-1098(90)90018-d", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012826977"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0005-1098(90)90018-d", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012826977"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1080/17442508408833313", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042094818"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/b978-0-08-034922-0.50005-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1046293096"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/5.21072", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061178998"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/87.486338", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061241589"
            ], 
            "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/9.701089", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061245629"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tac.1979.1101973", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061472529"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tac.1982.1103019", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061473497"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tac.1985.1103972", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061474249"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tr.1977.5215060", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061781453"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.21236/ada201614", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1091735914"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/isic.1994.367815", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1093323866"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/acc.1994.751830", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1094015748"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/acc.1994.751830", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1094015748"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/cdc.1997.650720", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1094629410"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2000-01", 
        "datePublishedReg": "2000-01-01", 
        "description": "We address the problem of failure diagnosis in discrete event systems with decentralized information. We propose a coordinated decentralized architecture consisting of local sites communicating with a coordinator that is responsible for diagnosing the failures occurring in the system. We extend the notion of diagnosability, originally introduced in Sampath et al. (1995) for centralized systems, to the proposed coordinated decentralized architecture. We specify three protocols that realize the proposed architecture; each protocol is defined by the diagnostic information generated at the local sites, the communication rules used by the local sites, and the coordinator's decision rule. We analyze the diagnostic properties of each protocol. We also state and prove conditions for a language to be diagnosable under each protocol. These conditions are checkable off-line. The on-line diagnostic process is carried out using the diagnosers introduced in Sampath et al. (1995) or a slight variation of these diagnosers. The key features of the proposed protocols are: (i) they achieve, each under a set of assumptions, the same diagnostic performance as the centralized diagnoser; and (ii) they highlight the \u201cperformance vs. complexity\u201d tradeoff that arises in coordinated decentralized architectures. The correctness of two of the protocols relies on some stringent global ordering assumptions on message reception at the coordinator's site, the relaxation of which is briefly discussed.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1023/a:1008335115538", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1136419", 
            "issn": [
              "0924-6703", 
              "1573-7594"
            ], 
            "name": "Discrete Event Dynamic Systems", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1-2", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "10"
          }
        ], 
        "name": "Coordinated Decentralized Protocols for Failure Diagnosis of Discrete Event Systems", 
        "pagination": "33-86", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "5a9eddba694f77209591af3c233526eb12c2f1e6a7a7b27ff83c06b67c53592c"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1023/a:1008335115538"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1019019323"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1023/a:1008335115538", 
          "https://app.dimensions.ai/details/publication/pub.1019019323"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-10T15:48", 
        "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/0000000001_0000000264/records_8664_00000499.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1023/A:1008335115538"
      }
    ]
     

    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.1023/a:1008335115538'

    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.1023/a:1008335115538'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1023/a:1008335115538'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1023/a:1008335115538'


     

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

    124 TRIPLES      21 PREDICATES      45 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1023/a:1008335115538 schema:about anzsrc-for:08
    2 anzsrc-for:0806
    3 schema:author N2a7132d0c8244a1383efc25bace9ffd8
    4 schema:citation sg:pub.10.1007/bf01441211
    5 https://doi.org/10.1016/0005-1098(76)90041-8
    6 https://doi.org/10.1016/0005-1098(90)90018-d
    7 https://doi.org/10.1016/b978-0-08-034922-0.50005-4
    8 https://doi.org/10.1080/17442508408833313
    9 https://doi.org/10.1109/5.21072
    10 https://doi.org/10.1109/87.486338
    11 https://doi.org/10.1109/9.412626
    12 https://doi.org/10.1109/9.701089
    13 https://doi.org/10.1109/acc.1994.751830
    14 https://doi.org/10.1109/cdc.1997.650720
    15 https://doi.org/10.1109/isic.1994.367815
    16 https://doi.org/10.1109/tac.1979.1101973
    17 https://doi.org/10.1109/tac.1982.1103019
    18 https://doi.org/10.1109/tac.1985.1103972
    19 https://doi.org/10.1109/tr.1977.5215060
    20 https://doi.org/10.1214/aos/1176343654
    21 https://doi.org/10.21236/ada201614
    22 schema:datePublished 2000-01
    23 schema:datePublishedReg 2000-01-01
    24 schema:description We address the problem of failure diagnosis in discrete event systems with decentralized information. We propose a coordinated decentralized architecture consisting of local sites communicating with a coordinator that is responsible for diagnosing the failures occurring in the system. We extend the notion of diagnosability, originally introduced in Sampath et al. (1995) for centralized systems, to the proposed coordinated decentralized architecture. We specify three protocols that realize the proposed architecture; each protocol is defined by the diagnostic information generated at the local sites, the communication rules used by the local sites, and the coordinator's decision rule. We analyze the diagnostic properties of each protocol. We also state and prove conditions for a language to be diagnosable under each protocol. These conditions are checkable off-line. The on-line diagnostic process is carried out using the diagnosers introduced in Sampath et al. (1995) or a slight variation of these diagnosers. The key features of the proposed protocols are: (i) they achieve, each under a set of assumptions, the same diagnostic performance as the centralized diagnoser; and (ii) they highlight the “performance vs. complexity” tradeoff that arises in coordinated decentralized architectures. The correctness of two of the protocols relies on some stringent global ordering assumptions on message reception at the coordinator's site, the relaxation of which is briefly discussed.
    25 schema:genre research_article
    26 schema:inLanguage en
    27 schema:isAccessibleForFree false
    28 schema:isPartOf N638a86c3a58c4eeaa0b9e4ca629d1556
    29 Nd21851544a3a4775b0d69efa7db27750
    30 sg:journal.1136419
    31 schema:name Coordinated Decentralized Protocols for Failure Diagnosis of Discrete Event Systems
    32 schema:pagination 33-86
    33 schema:productId Naa3c4c35b6254874a4b34894dcc0090d
    34 Nd602deb1bd6e4e9bbb4e5fb8d8e19212
    35 Nf2fa2af45e054bb0a1139d9c9a330c3e
    36 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019019323
    37 https://doi.org/10.1023/a:1008335115538
    38 schema:sdDatePublished 2019-04-10T15:48
    39 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    40 schema:sdPublisher Ne5a2c6837443477fb26e6d69d56faf27
    41 schema:url http://link.springer.com/10.1023/A:1008335115538
    42 sgo:license sg:explorer/license/
    43 sgo:sdDataset articles
    44 rdf:type schema:ScholarlyArticle
    45 N122f886d8b6446b38b7e08c93ecabf28 rdf:first sg:person.01131403760.98
    46 rdf:rest N9cb0a233b22f45b7bb7f41bad50e855c
    47 N2a7132d0c8244a1383efc25bace9ffd8 rdf:first sg:person.014465223505.00
    48 rdf:rest N122f886d8b6446b38b7e08c93ecabf28
    49 N638a86c3a58c4eeaa0b9e4ca629d1556 schema:issueNumber 1-2
    50 rdf:type schema:PublicationIssue
    51 N9cb0a233b22f45b7bb7f41bad50e855c rdf:first sg:person.014462715775.20
    52 rdf:rest rdf:nil
    53 Naa3c4c35b6254874a4b34894dcc0090d schema:name dimensions_id
    54 schema:value pub.1019019323
    55 rdf:type schema:PropertyValue
    56 Nd21851544a3a4775b0d69efa7db27750 schema:volumeNumber 10
    57 rdf:type schema:PublicationVolume
    58 Nd602deb1bd6e4e9bbb4e5fb8d8e19212 schema:name doi
    59 schema:value 10.1023/a:1008335115538
    60 rdf:type schema:PropertyValue
    61 Ne5a2c6837443477fb26e6d69d56faf27 schema:name Springer Nature - SN SciGraph project
    62 rdf:type schema:Organization
    63 Nf2fa2af45e054bb0a1139d9c9a330c3e schema:name readcube_id
    64 schema:value 5a9eddba694f77209591af3c233526eb12c2f1e6a7a7b27ff83c06b67c53592c
    65 rdf:type schema:PropertyValue
    66 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    67 schema:name Information and Computing Sciences
    68 rdf:type schema:DefinedTerm
    69 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
    70 schema:name Information Systems
    71 rdf:type schema:DefinedTerm
    72 sg:journal.1136419 schema:issn 0924-6703
    73 1573-7594
    74 schema:name Discrete Event Dynamic Systems
    75 rdf:type schema:Periodical
    76 sg:person.01131403760.98 schema:familyName Lafortune
    77 schema:givenName Stéphane
    78 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01131403760.98
    79 rdf:type schema:Person
    80 sg:person.014462715775.20 schema:familyName Teneketzis
    81 schema:givenName Demosthenis
    82 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014462715775.20
    83 rdf:type schema:Person
    84 sg:person.014465223505.00 schema:familyName Debouk
    85 schema:givenName Rami
    86 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014465223505.00
    87 rdf:type schema:Person
    88 sg:pub.10.1007/bf01441211 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002375852
    89 https://doi.org/10.1007/bf01441211
    90 rdf:type schema:CreativeWork
    91 https://doi.org/10.1016/0005-1098(76)90041-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000971875
    92 rdf:type schema:CreativeWork
    93 https://doi.org/10.1016/0005-1098(90)90018-d schema:sameAs https://app.dimensions.ai/details/publication/pub.1012826977
    94 rdf:type schema:CreativeWork
    95 https://doi.org/10.1016/b978-0-08-034922-0.50005-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046293096
    96 rdf:type schema:CreativeWork
    97 https://doi.org/10.1080/17442508408833313 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042094818
    98 rdf:type schema:CreativeWork
    99 https://doi.org/10.1109/5.21072 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061178998
    100 rdf:type schema:CreativeWork
    101 https://doi.org/10.1109/87.486338 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061241589
    102 rdf:type schema:CreativeWork
    103 https://doi.org/10.1109/9.412626 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061244618
    104 rdf:type schema:CreativeWork
    105 https://doi.org/10.1109/9.701089 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061245629
    106 rdf:type schema:CreativeWork
    107 https://doi.org/10.1109/acc.1994.751830 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094015748
    108 rdf:type schema:CreativeWork
    109 https://doi.org/10.1109/cdc.1997.650720 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094629410
    110 rdf:type schema:CreativeWork
    111 https://doi.org/10.1109/isic.1994.367815 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093323866
    112 rdf:type schema:CreativeWork
    113 https://doi.org/10.1109/tac.1979.1101973 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061472529
    114 rdf:type schema:CreativeWork
    115 https://doi.org/10.1109/tac.1982.1103019 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061473497
    116 rdf:type schema:CreativeWork
    117 https://doi.org/10.1109/tac.1985.1103972 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061474249
    118 rdf:type schema:CreativeWork
    119 https://doi.org/10.1109/tr.1977.5215060 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061781453
    120 rdf:type schema:CreativeWork
    121 https://doi.org/10.1214/aos/1176343654 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012552178
    122 rdf:type schema:CreativeWork
    123 https://doi.org/10.21236/ada201614 schema:sameAs https://app.dimensions.ai/details/publication/pub.1091735914
    124 rdf:type schema:CreativeWork
     




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


    ...