Synchronous, asynchronous, and causally ordered communication View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1996-02

AUTHORS

Bernadette Charron-Bost, Friedemann Mattern, Gerard Tel

ABSTRACT

This article studies characteristic properties of synchronous and asynchronous message communications in distributed systems. Based on the causality relation between events in computations with asynchronous communications, we characterize computations which are realizable with synchronous communications, which respect causal order, or where messages between two processes are always received in the order sent. It is shown that the corresponding computation classes form a strict hierarchy. Furthermore, an axiomatic definition of distributed computations with synchronous communications is given, and it is shown that several informal characterizations of such computations are equivalent when they are formalized appropriately. As an application, we use our results to show that the distributed termination detection algorithm by Dijkstra et al. is correct under a weaker synchrony assumption than originally stated. More... »

PAGES

173-191

References to SciGraph publications

  • 1990. From Synchronous to Asynchronous Communication in SPECIFICATION AND VERIFICATION OF CONCURRENT SYSTEMS
  • 1995. A non-blocking lightweight implementation of causal order message delivery in THEORY AND PRACTICE IN DISTRIBUTED SYSTEMS
  • 1989. The Calculation of Invariants for Ordered Sets in ALGORITHMS AND ORDER
  • 1994. The MPI standard for message passing in HIGH-PERFORMANCE COMPUTING AND NETWORKING
  • 1980. A Calculus of Communicating Systems in NONE
  • 1989. A new algorithm to implement causal ordering in DISTRIBUTED ALGORITHMS
  • 1992. Causal memory in DISTRIBUTED ALGORITHMS
  • 1987-09. Algorithms for distributed termination detection in DISTRIBUTED COMPUTING
  • 1981-10. An axiomatic definition of synchronization primitives in ACTA INFORMATICA
  • Identifiers

    URI

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

    DOI

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

    DIMENSIONS

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


    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/0805", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Distributed Computing", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Laboratoire d\u2019Informatique, Ecole Polytechnique, F-91128, Palaiseau Cedex, France", 
              "id": "http://www.grid.ac/institutes/grid.10877.39", 
              "name": [
                "Laboratoire d\u2019Informatique, Ecole Polytechnique, F-91128, Palaiseau Cedex, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Charron-Bost", 
            "givenName": "Bernadette", 
            "id": "sg:person.015617712663.70", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015617712663.70"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Computer Science, Technical University of Darmstadt, Alexanderstrasse 10, D-64283, Darmstadt, Germany", 
              "id": "http://www.grid.ac/institutes/grid.6546.1", 
              "name": [
                "Department of Computer Science, Technical University of Darmstadt, Alexanderstrasse 10, D-64283, Darmstadt, 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"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Computer Science, University of Utrecht, P.O. Box 80.089, 3508, TB Utrecht, The Netherlands", 
              "id": "http://www.grid.ac/institutes/grid.5477.1", 
              "name": [
                "Department of Computer Science, University of Utrecht, P.O. Box 80.089, 3508, TB Utrecht, The Netherlands"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Tel", 
            "givenName": "Gerard", 
            "id": "sg:person.016642327761.12", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016642327761.12"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/bf01782776", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015151993", 
              "https://doi.org/10.1007/bf01782776"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-57981-8_126", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017661071", 
              "https://doi.org/10.1007/3-540-57981-8_126"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0022435", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050291902", 
              "https://doi.org/10.1007/bfb0022435"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-10235-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1109702119", 
              "https://doi.org/10.1007/3-540-10235-3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00261260", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023285363", 
              "https://doi.org/10.1007/bf00261260"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-94-009-2639-4_6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051607934", 
              "https://doi.org/10.1007/978-94-009-2639-4_6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-51687-5_45", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033523963", 
              "https://doi.org/10.1007/3-540-51687-5_45"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-60042-6_14", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008008964", 
              "https://doi.org/10.1007/3-540-60042-6_14"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4471-3534-0_18", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037846204", 
              "https://doi.org/10.1007/978-1-4471-3534-0_18"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1996-02", 
        "datePublishedReg": "1996-02-01", 
        "description": "This article studies characteristic properties of synchronous and asynchronous message communications in distributed systems. Based on the causality relation between events in computations with asynchronous communications, we characterize computations which are realizable with synchronous communications, which respect causal order, or where messages between two processes are always received in the order sent. It is shown that the corresponding computation classes form a strict hierarchy. Furthermore, an axiomatic definition of distributed computations with synchronous communications is given, and it is shown that several informal characterizations of such computations are equivalent when they are formalized appropriately. As an application, we use our results to show that the distributed termination detection algorithm by Dijkstra et al. is correct under a weaker synchrony assumption than originally stated.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s004460050018", 
        "inLanguage": "en", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1052621", 
            "issn": [
              "0178-2770", 
              "1432-0452"
            ], 
            "name": "Distributed Computing", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "4", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "9"
          }
        ], 
        "keywords": [
          "message communication", 
          "communication", 
          "synchronous communication", 
          "asynchronous communication", 
          "detection algorithm", 
          "messages", 
          "such computations", 
          "synchrony assumptions", 
          "system", 
          "computation", 
          "order", 
          "applications", 
          "algorithm", 
          "characteristic properties", 
          "properties", 
          "class", 
          "hierarchy", 
          "characterization", 
          "results", 
          "article", 
          "causal order", 
          "process", 
          "definition", 
          "et al", 
          "al", 
          "assumption", 
          "asynchronous message communication", 
          "relation", 
          "events", 
          "strict hierarchy", 
          "axiomatic definition", 
          "informal characterization", 
          "termination detection algorithm", 
          "causality relation", 
          "corresponding computation classes", 
          "computation classes", 
          "Dijkstra et al", 
          "weaker synchrony assumption"
        ], 
        "name": "Synchronous, asynchronous, and causally ordered communication", 
        "pagination": "173-191", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1040571573"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s004460050018"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s004460050018", 
          "https://app.dimensions.ai/details/publication/pub.1040571573"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-01-01T18:07", 
        "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_264.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s004460050018"
      }
    ]
     

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

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

    Turtle is a human-readable linked data format.

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

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

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


     

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

    152 TRIPLES      22 PREDICATES      72 URIs      55 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s004460050018 schema:about anzsrc-for:08
    2 anzsrc-for:0805
    3 schema:author N6882ee0e7021453b872bac4857238b66
    4 schema:citation sg:pub.10.1007/3-540-10235-3
    5 sg:pub.10.1007/3-540-51687-5_45
    6 sg:pub.10.1007/3-540-57981-8_126
    7 sg:pub.10.1007/3-540-60042-6_14
    8 sg:pub.10.1007/978-1-4471-3534-0_18
    9 sg:pub.10.1007/978-94-009-2639-4_6
    10 sg:pub.10.1007/bf00261260
    11 sg:pub.10.1007/bf01782776
    12 sg:pub.10.1007/bfb0022435
    13 schema:datePublished 1996-02
    14 schema:datePublishedReg 1996-02-01
    15 schema:description This article studies characteristic properties of synchronous and asynchronous message communications in distributed systems. Based on the causality relation between events in computations with asynchronous communications, we characterize computations which are realizable with synchronous communications, which respect causal order, or where messages between two processes are always received in the order sent. It is shown that the corresponding computation classes form a strict hierarchy. Furthermore, an axiomatic definition of distributed computations with synchronous communications is given, and it is shown that several informal characterizations of such computations are equivalent when they are formalized appropriately. As an application, we use our results to show that the distributed termination detection algorithm by Dijkstra et al. is correct under a weaker synchrony assumption than originally stated.
    16 schema:genre article
    17 schema:inLanguage en
    18 schema:isAccessibleForFree false
    19 schema:isPartOf Ne4421328b3144ce0a02619d137e46a0a
    20 Nef561b7017a3413ea69256dcb615af03
    21 sg:journal.1052621
    22 schema:keywords Dijkstra et al
    23 al
    24 algorithm
    25 applications
    26 article
    27 assumption
    28 asynchronous communication
    29 asynchronous message communication
    30 axiomatic definition
    31 causal order
    32 causality relation
    33 characteristic properties
    34 characterization
    35 class
    36 communication
    37 computation
    38 computation classes
    39 corresponding computation classes
    40 definition
    41 detection algorithm
    42 et al
    43 events
    44 hierarchy
    45 informal characterization
    46 message communication
    47 messages
    48 order
    49 process
    50 properties
    51 relation
    52 results
    53 strict hierarchy
    54 such computations
    55 synchronous communication
    56 synchrony assumptions
    57 system
    58 termination detection algorithm
    59 weaker synchrony assumption
    60 schema:name Synchronous, asynchronous, and causally ordered communication
    61 schema:pagination 173-191
    62 schema:productId N921f4fc013024e6c8786d15af6a783a5
    63 Nadc172a95fe341d4b6618fb640c430ed
    64 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040571573
    65 https://doi.org/10.1007/s004460050018
    66 schema:sdDatePublished 2022-01-01T18:07
    67 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    68 schema:sdPublisher Nbdd4803ed20a4939974db52a28965bd0
    69 schema:url https://doi.org/10.1007/s004460050018
    70 sgo:license sg:explorer/license/
    71 sgo:sdDataset articles
    72 rdf:type schema:ScholarlyArticle
    73 N62e36b7caeaf4469884d994303b37641 rdf:first sg:person.012317614157.00
    74 rdf:rest Nf3257f70da5b4beaa44da724120cf431
    75 N6882ee0e7021453b872bac4857238b66 rdf:first sg:person.015617712663.70
    76 rdf:rest N62e36b7caeaf4469884d994303b37641
    77 N921f4fc013024e6c8786d15af6a783a5 schema:name dimensions_id
    78 schema:value pub.1040571573
    79 rdf:type schema:PropertyValue
    80 Nadc172a95fe341d4b6618fb640c430ed schema:name doi
    81 schema:value 10.1007/s004460050018
    82 rdf:type schema:PropertyValue
    83 Nbdd4803ed20a4939974db52a28965bd0 schema:name Springer Nature - SN SciGraph project
    84 rdf:type schema:Organization
    85 Ne4421328b3144ce0a02619d137e46a0a schema:issueNumber 4
    86 rdf:type schema:PublicationIssue
    87 Nef561b7017a3413ea69256dcb615af03 schema:volumeNumber 9
    88 rdf:type schema:PublicationVolume
    89 Nf3257f70da5b4beaa44da724120cf431 rdf:first sg:person.016642327761.12
    90 rdf:rest rdf:nil
    91 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    92 schema:name Information and Computing Sciences
    93 rdf:type schema:DefinedTerm
    94 anzsrc-for:0805 schema:inDefinedTermSet anzsrc-for:
    95 schema:name Distributed Computing
    96 rdf:type schema:DefinedTerm
    97 sg:journal.1052621 schema:issn 0178-2770
    98 1432-0452
    99 schema:name Distributed Computing
    100 schema:publisher Springer Nature
    101 rdf:type schema:Periodical
    102 sg:person.012317614157.00 schema:affiliation grid-institutes:grid.6546.1
    103 schema:familyName Mattern
    104 schema:givenName Friedemann
    105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012317614157.00
    106 rdf:type schema:Person
    107 sg:person.015617712663.70 schema:affiliation grid-institutes:grid.10877.39
    108 schema:familyName Charron-Bost
    109 schema:givenName Bernadette
    110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015617712663.70
    111 rdf:type schema:Person
    112 sg:person.016642327761.12 schema:affiliation grid-institutes:grid.5477.1
    113 schema:familyName Tel
    114 schema:givenName Gerard
    115 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016642327761.12
    116 rdf:type schema:Person
    117 sg:pub.10.1007/3-540-10235-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1109702119
    118 https://doi.org/10.1007/3-540-10235-3
    119 rdf:type schema:CreativeWork
    120 sg:pub.10.1007/3-540-51687-5_45 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033523963
    121 https://doi.org/10.1007/3-540-51687-5_45
    122 rdf:type schema:CreativeWork
    123 sg:pub.10.1007/3-540-57981-8_126 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017661071
    124 https://doi.org/10.1007/3-540-57981-8_126
    125 rdf:type schema:CreativeWork
    126 sg:pub.10.1007/3-540-60042-6_14 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008008964
    127 https://doi.org/10.1007/3-540-60042-6_14
    128 rdf:type schema:CreativeWork
    129 sg:pub.10.1007/978-1-4471-3534-0_18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037846204
    130 https://doi.org/10.1007/978-1-4471-3534-0_18
    131 rdf:type schema:CreativeWork
    132 sg:pub.10.1007/978-94-009-2639-4_6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051607934
    133 https://doi.org/10.1007/978-94-009-2639-4_6
    134 rdf:type schema:CreativeWork
    135 sg:pub.10.1007/bf00261260 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023285363
    136 https://doi.org/10.1007/bf00261260
    137 rdf:type schema:CreativeWork
    138 sg:pub.10.1007/bf01782776 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015151993
    139 https://doi.org/10.1007/bf01782776
    140 rdf:type schema:CreativeWork
    141 sg:pub.10.1007/bfb0022435 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050291902
    142 https://doi.org/10.1007/bfb0022435
    143 rdf:type schema:CreativeWork
    144 grid-institutes:grid.10877.39 schema:alternateName Laboratoire d’Informatique, Ecole Polytechnique, F-91128, Palaiseau Cedex, France
    145 schema:name Laboratoire d’Informatique, Ecole Polytechnique, F-91128, Palaiseau Cedex, France
    146 rdf:type schema:Organization
    147 grid-institutes:grid.5477.1 schema:alternateName Department of Computer Science, University of Utrecht, P.O. Box 80.089, 3508, TB Utrecht, The Netherlands
    148 schema:name Department of Computer Science, University of Utrecht, P.O. Box 80.089, 3508, TB Utrecht, The Netherlands
    149 rdf:type schema:Organization
    150 grid-institutes:grid.6546.1 schema:alternateName Department of Computer Science, Technical University of Darmstadt, Alexanderstrasse 10, D-64283, Darmstadt, Germany
    151 schema:name Department of Computer Science, Technical University of Darmstadt, Alexanderstrasse 10, D-64283, Darmstadt, Germany
    152 rdf:type schema:Organization
     




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


    ...