Algorithms for distributed termination detection View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1987-09

AUTHORS

Friedemann Mattern

ABSTRACT

The termination problem for distributed computations is analyzed in the general context of asynchronous communication. In the underlying computational model it is assumed that messages take an arbitrary but finite time and do not necessarily obey the FIFO rule. Time diagrams are used as a graphic means of representing the overall communication scheme, giving a clear insight into the difficulties involved (e.g., lack of global state or time, inconsistent time cuts) and suggesting possible solutions.Several efficient algorithms for the solution of the termination problem are presented. They are all based on the idea of message counting but have a number of different characteristics. The methods are discussed and compared with other known solutions. More... »

PAGES

161-175

References to SciGraph publications

  • 1985. A class of termination detection algorithms for distributed computations in FOUNDATIONS OF SOFTWARE TECHNOLOGY AND THEORETICAL COMPUTER SCIENCE
  • 1986. A termination detector for static and dynamic distributed systems with asynchronous non-first-in-first-out communication in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 1986. A new approach to detection of locally indicative stability in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 1986-06. Distributed termination on a ring in BIT NUMERICAL MATHEMATICS
  • 1988. Experience with a new distributed termination detection algorithm in DISTRIBUTED ALGORITHMS
  • 1987. On the Construction of Distributed Programs in DISTRIBUTED OPERATING SYSTEMS
  • 1987. High Level Petri Nets and Distributed Termination in CONCURRENCY AND NETS
  • 1981. Distributed termination with interval assertions in FORMALIZATION OF PROGRAMMING CONCEPTS
  • 1986. Model and complexity of termination for distributed computations in MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 1986
  • 1986. Real Time Clocks Versus Virtual Clocks in CONTROL FLOW AND DATA FLOW: CONCEPTS OF DISTRIBUTED PROGRAMMING
  • 1986. Symmetric Distributed Termination in THE BOOK OF L
  • 1985. Repeated synchronous snapshots and their implementation in CSP in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 1987. Solutions for the distributed termination problem in PARALLEL ALGORITHMS AND ARCHITECTURES
  • 1985. Distributed termination in CSP symmetric solutions with minimal storage in STACS 85
  • 1985. A Paradigm for Detecting Quiescent Properties in Distributed Computations in LOGICS AND MODELS OF CONCURRENT SYSTEMS
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/bf01782776

    DOI

    http://dx.doi.org/10.1007/bf01782776

    DIMENSIONS

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


    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/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computation Theory and Mathematics", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Department of Computer Science, SFB124, University of Kaiserslautern, P. O. Box 3049, D-6750, Kaiserslautern, Federal Republic of Germany", 
              "id": "http://www.grid.ac/institutes/grid.7645.0", 
              "name": [
                "Department of Computer Science, SFB124, University of Kaiserslautern, P. O. Box 3049, D-6750, Kaiserslautern, Federal Republic of Germany"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Mattern", 
            "givenName": "Friedemann", 
            "id": "sg:person.012317614157.00", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012317614157.00"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/bfb0024015", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029202210", 
              "https://doi.org/10.1007/bfb0024015"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-46604-5_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013155542", 
              "https://doi.org/10.1007/978-3-642-46604-5_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0015731", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005156719", 
              "https://doi.org/10.1007/bfb0015731"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-72822-8_23", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022750733", 
              "https://doi.org/10.1007/978-3-642-72822-8_23"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0019800", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021160369", 
              "https://doi.org/10.1007/bfb0019800"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-16042-6_4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043309568", 
              "https://doi.org/10.1007/3-540-16042-6_4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-18099-0_36", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023724458", 
              "https://doi.org/10.1007/3-540-18099-0_36"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-82453-1_11", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022937288", 
              "https://doi.org/10.1007/978-3-642-82453-1_11"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-95486-3_36", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008436408", 
              "https://doi.org/10.1007/978-3-642-95486-3_36"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-10699-5_105", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003373304", 
              "https://doi.org/10.1007/3-540-10699-5_105"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-82921-5_11", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033545694", 
              "https://doi.org/10.1007/978-3-642-82921-5_11"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-16761-7_69", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1044561461", 
              "https://doi.org/10.1007/3-540-16761-7_69"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01933744", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011597530", 
              "https://doi.org/10.1007/bf01933744"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0016283", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049484158", 
              "https://doi.org/10.1007/bfb0016283"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-16761-7_84", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003441718", 
              "https://doi.org/10.1007/3-540-16761-7_84"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1987-09", 
        "datePublishedReg": "1987-09-01", 
        "description": "The termination problem for distributed computations is analyzed in the general context of asynchronous communication. In the underlying computational model it is assumed that messages take an arbitrary but finite time and do not necessarily obey the FIFO rule. Time diagrams are used as a graphic means of representing the overall communication scheme, giving a clear insight into the difficulties involved (e.g., lack of global state or time, inconsistent time cuts) and suggesting possible solutions.Several efficient algorithms for the solution of the termination problem are presented. They are all based on the idea of message counting but have a number of different characteristics. The methods are discussed and compared with other known solutions.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/bf01782776", 
        "inLanguage": "en", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1052621", 
            "issn": [
              "0178-2770", 
              "1432-0452"
            ], 
            "name": "Distributed Computing", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "3", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "2"
          }
        ], 
        "keywords": [
          "termination problem", 
          "message counting", 
          "termination detection", 
          "asynchronous communication", 
          "efficient algorithm", 
          "communication scheme", 
          "computational model", 
          "algorithm", 
          "possible solutions", 
          "FIFO rule", 
          "graphic means", 
          "different characteristics", 
          "finite time", 
          "time diagrams", 
          "computation", 
          "messages", 
          "communication", 
          "scheme", 
          "solution", 
          "general context", 
          "rules", 
          "detection", 
          "idea", 
          "context", 
          "clear insight", 
          "method", 
          "model", 
          "counting", 
          "difficulties", 
          "number", 
          "diagram", 
          "time", 
          "means", 
          "characteristics", 
          "insights", 
          "problem", 
          "overall communication scheme"
        ], 
        "name": "Algorithms for distributed termination detection", 
        "pagination": "161-175", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1015151993"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/bf01782776"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/bf01782776", 
          "https://app.dimensions.ai/details/publication/pub.1015151993"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-01-01T18:03", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/article/article_189.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/bf01782776"
      }
    ]
     

    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/bf01782776'

    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/bf01782776'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf01782776'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf01782776'


     

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

    155 TRIPLES      22 PREDICATES      78 URIs      55 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/bf01782776 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author Nfe22abe7e3e64d0cb76d56464822428a
    4 schema:citation sg:pub.10.1007/3-540-10699-5_105
    5 sg:pub.10.1007/3-540-16042-6_4
    6 sg:pub.10.1007/3-540-16761-7_69
    7 sg:pub.10.1007/3-540-16761-7_84
    8 sg:pub.10.1007/3-540-18099-0_36
    9 sg:pub.10.1007/978-3-642-46604-5_2
    10 sg:pub.10.1007/978-3-642-72822-8_23
    11 sg:pub.10.1007/978-3-642-82453-1_11
    12 sg:pub.10.1007/978-3-642-82921-5_11
    13 sg:pub.10.1007/978-3-642-95486-3_36
    14 sg:pub.10.1007/bf01933744
    15 sg:pub.10.1007/bfb0015731
    16 sg:pub.10.1007/bfb0016283
    17 sg:pub.10.1007/bfb0019800
    18 sg:pub.10.1007/bfb0024015
    19 schema:datePublished 1987-09
    20 schema:datePublishedReg 1987-09-01
    21 schema:description The termination problem for distributed computations is analyzed in the general context of asynchronous communication. In the underlying computational model it is assumed that messages take an arbitrary but finite time and do not necessarily obey the FIFO rule. Time diagrams are used as a graphic means of representing the overall communication scheme, giving a clear insight into the difficulties involved (e.g., lack of global state or time, inconsistent time cuts) and suggesting possible solutions.Several efficient algorithms for the solution of the termination problem are presented. They are all based on the idea of message counting but have a number of different characteristics. The methods are discussed and compared with other known solutions.
    22 schema:genre article
    23 schema:inLanguage en
    24 schema:isAccessibleForFree false
    25 schema:isPartOf N14c7c763dd80434da1e99d40cdaaa00b
    26 N714d159562eb418987d54c28891ceafe
    27 sg:journal.1052621
    28 schema:keywords FIFO rule
    29 algorithm
    30 asynchronous communication
    31 characteristics
    32 clear insight
    33 communication
    34 communication scheme
    35 computation
    36 computational model
    37 context
    38 counting
    39 detection
    40 diagram
    41 different characteristics
    42 difficulties
    43 efficient algorithm
    44 finite time
    45 general context
    46 graphic means
    47 idea
    48 insights
    49 means
    50 message counting
    51 messages
    52 method
    53 model
    54 number
    55 overall communication scheme
    56 possible solutions
    57 problem
    58 rules
    59 scheme
    60 solution
    61 termination detection
    62 termination problem
    63 time
    64 time diagrams
    65 schema:name Algorithms for distributed termination detection
    66 schema:pagination 161-175
    67 schema:productId N567ba9e20a67476ea51c80562b024d1b
    68 Naaa0afa1a9ce4c929e4aa2201dc81639
    69 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015151993
    70 https://doi.org/10.1007/bf01782776
    71 schema:sdDatePublished 2022-01-01T18:03
    72 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    73 schema:sdPublisher N26f04256d32d46088aeecd8c29462500
    74 schema:url https://doi.org/10.1007/bf01782776
    75 sgo:license sg:explorer/license/
    76 sgo:sdDataset articles
    77 rdf:type schema:ScholarlyArticle
    78 N14c7c763dd80434da1e99d40cdaaa00b schema:volumeNumber 2
    79 rdf:type schema:PublicationVolume
    80 N26f04256d32d46088aeecd8c29462500 schema:name Springer Nature - SN SciGraph project
    81 rdf:type schema:Organization
    82 N567ba9e20a67476ea51c80562b024d1b schema:name dimensions_id
    83 schema:value pub.1015151993
    84 rdf:type schema:PropertyValue
    85 N714d159562eb418987d54c28891ceafe schema:issueNumber 3
    86 rdf:type schema:PublicationIssue
    87 Naaa0afa1a9ce4c929e4aa2201dc81639 schema:name doi
    88 schema:value 10.1007/bf01782776
    89 rdf:type schema:PropertyValue
    90 Nfe22abe7e3e64d0cb76d56464822428a rdf:first sg:person.012317614157.00
    91 rdf:rest rdf:nil
    92 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    93 schema:name Information and Computing Sciences
    94 rdf:type schema:DefinedTerm
    95 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    96 schema:name Computation Theory and Mathematics
    97 rdf:type schema:DefinedTerm
    98 sg:journal.1052621 schema:issn 0178-2770
    99 1432-0452
    100 schema:name Distributed Computing
    101 schema:publisher Springer Nature
    102 rdf:type schema:Periodical
    103 sg:person.012317614157.00 schema:affiliation grid-institutes:grid.7645.0
    104 schema:familyName Mattern
    105 schema:givenName Friedemann
    106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012317614157.00
    107 rdf:type schema:Person
    108 sg:pub.10.1007/3-540-10699-5_105 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003373304
    109 https://doi.org/10.1007/3-540-10699-5_105
    110 rdf:type schema:CreativeWork
    111 sg:pub.10.1007/3-540-16042-6_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043309568
    112 https://doi.org/10.1007/3-540-16042-6_4
    113 rdf:type schema:CreativeWork
    114 sg:pub.10.1007/3-540-16761-7_69 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044561461
    115 https://doi.org/10.1007/3-540-16761-7_69
    116 rdf:type schema:CreativeWork
    117 sg:pub.10.1007/3-540-16761-7_84 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003441718
    118 https://doi.org/10.1007/3-540-16761-7_84
    119 rdf:type schema:CreativeWork
    120 sg:pub.10.1007/3-540-18099-0_36 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023724458
    121 https://doi.org/10.1007/3-540-18099-0_36
    122 rdf:type schema:CreativeWork
    123 sg:pub.10.1007/978-3-642-46604-5_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013155542
    124 https://doi.org/10.1007/978-3-642-46604-5_2
    125 rdf:type schema:CreativeWork
    126 sg:pub.10.1007/978-3-642-72822-8_23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022750733
    127 https://doi.org/10.1007/978-3-642-72822-8_23
    128 rdf:type schema:CreativeWork
    129 sg:pub.10.1007/978-3-642-82453-1_11 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022937288
    130 https://doi.org/10.1007/978-3-642-82453-1_11
    131 rdf:type schema:CreativeWork
    132 sg:pub.10.1007/978-3-642-82921-5_11 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033545694
    133 https://doi.org/10.1007/978-3-642-82921-5_11
    134 rdf:type schema:CreativeWork
    135 sg:pub.10.1007/978-3-642-95486-3_36 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008436408
    136 https://doi.org/10.1007/978-3-642-95486-3_36
    137 rdf:type schema:CreativeWork
    138 sg:pub.10.1007/bf01933744 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011597530
    139 https://doi.org/10.1007/bf01933744
    140 rdf:type schema:CreativeWork
    141 sg:pub.10.1007/bfb0015731 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005156719
    142 https://doi.org/10.1007/bfb0015731
    143 rdf:type schema:CreativeWork
    144 sg:pub.10.1007/bfb0016283 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049484158
    145 https://doi.org/10.1007/bfb0016283
    146 rdf:type schema:CreativeWork
    147 sg:pub.10.1007/bfb0019800 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021160369
    148 https://doi.org/10.1007/bfb0019800
    149 rdf:type schema:CreativeWork
    150 sg:pub.10.1007/bfb0024015 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029202210
    151 https://doi.org/10.1007/bfb0024015
    152 rdf:type schema:CreativeWork
    153 grid-institutes:grid.7645.0 schema:alternateName Department of Computer Science, SFB124, University of Kaiserslautern, P. O. Box 3049, D-6750, Kaiserslautern, Federal Republic of Germany
    154 schema:name Department of Computer Science, SFB124, University of Kaiserslautern, P. O. Box 3049, D-6750, Kaiserslautern, Federal Republic of Germany
    155 rdf:type schema:Organization
     




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


    ...