Asynchronous distributed termination—parallel and symmetric solutions with echo algorithms View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

1990-06

AUTHORS

Friedemann Mattern

ABSTRACT

The principle of message counting is used to detect termination of distributed computations which consist of processes asynchronously communicating over non-FIFO channels. The solution is symmetric and not based on a predefined communication structure. An efficient variant of the echo algorithm, which dynamically builds a spanning tree, allows a parallel and distributed evaluation of the termination predicate in time proportional to the diameter of the communication graph. Concurrent and repeated initiation of the detection algorithm by different processes is possible at any time without prior synchronization due to a subtle method of collision detection and wave extinction, which can be regarded as a distributed election scheme where the average message complexity increases only logarithmically with the number of concurrent initiators. Control messages have a small length and additional communication links are not required. Only a fixed number of simple variables is needed in every process, global knowledge such as the total number of processes or the structure of the network is not used, making the scheme useful for dynamic systems. Several variations of the basic principle are presented, important issues such as message complexity and fault-tolerance are discussed. More... »

PAGES

325-340

References to SciGraph publications

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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, 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, 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/bf00263584", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1049705236", 
          "https://doi.org/10.1007/bf00263584"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01782773", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1030093658", 
          "https://doi.org/10.1007/bf01782773"
        ], 
        "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/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/bf01782776", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1015151993", 
          "https://doi.org/10.1007/bf01782776"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1990-06", 
    "datePublishedReg": "1990-06-01", 
    "description": "The principle of message counting is used to detect termination of distributed computations which consist of processes asynchronously communicating over non-FIFO channels. The solution is symmetric and not based on a predefined communication structure. An efficient variant of the echo algorithm, which dynamically builds a spanning tree, allows a parallel and distributed evaluation of the termination predicate in time proportional to the diameter of the communication graph. Concurrent and repeated initiation of the detection algorithm by different processes is possible at any time without prior synchronization due to a subtle method of collision detection and wave extinction, which can be regarded as a distributed election scheme where the average message complexity increases only logarithmically with the number of concurrent initiators. Control messages have a small length and additional communication links are not required. Only a fixed number of simple variables is needed in every process, global knowledge such as the total number of processes or the structure of the network is not used, making the scheme useful for dynamic systems. Several variations of the basic principle are presented, important issues such as message complexity and fault-tolerance are discussed.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/bf01840392", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1047644", 
        "issn": [
          "0178-4617", 
          "1432-0541"
        ], 
        "name": "Algorithmica", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1-4", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "5"
      }
    ], 
    "keywords": [
      "message complexity", 
      "echo algorithm", 
      "non-FIFO channels", 
      "average message complexity", 
      "additional communication links", 
      "message counting", 
      "communication graph", 
      "distributed evaluation", 
      "detection algorithm", 
      "control messages", 
      "collision detection", 
      "election scheme", 
      "termination predicates", 
      "global knowledge", 
      "communication structure", 
      "efficient variant", 
      "communication links", 
      "prior synchronization", 
      "spanning tree", 
      "concurrent initiators", 
      "algorithm", 
      "dynamic systems", 
      "important issue", 
      "complexity", 
      "scheme", 
      "network", 
      "predicates", 
      "graph", 
      "computation", 
      "messages", 
      "subtle methods", 
      "synchronization", 
      "basic principles", 
      "solution", 
      "simple variables", 
      "system", 
      "process", 
      "number", 
      "detection", 
      "principles", 
      "trees", 
      "issues", 
      "time", 
      "link", 
      "knowledge", 
      "channels", 
      "method", 
      "parallel", 
      "small length", 
      "counting", 
      "different processes", 
      "evaluation", 
      "structure", 
      "total number", 
      "variants", 
      "variables", 
      "termination", 
      "length", 
      "variation", 
      "symmetric solutions", 
      "initiator", 
      "diameter", 
      "extinction", 
      "initiation", 
      "wave extinction"
    ], 
    "name": "Asynchronous distributed termination\u2014parallel and symmetric solutions with echo algorithms", 
    "pagination": "325-340", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1024350945"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf01840392"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf01840392", 
      "https://app.dimensions.ai/details/publication/pub.1024350945"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-01-01T18:06", 
    "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_245.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/bf01840392"
  }
]
 

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

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

Turtle is a human-readable linked data format.

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

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

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


 

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

143 TRIPLES      22 PREDICATES      96 URIs      83 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf01840392 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N362b391e6cff407c8dae551d23422a60
4 schema:citation sg:pub.10.1007/978-3-642-82453-1_11
5 sg:pub.10.1007/978-3-642-95486-3_36
6 sg:pub.10.1007/bf00263584
7 sg:pub.10.1007/bf01782773
8 sg:pub.10.1007/bf01782776
9 schema:datePublished 1990-06
10 schema:datePublishedReg 1990-06-01
11 schema:description The principle of message counting is used to detect termination of distributed computations which consist of processes asynchronously communicating over non-FIFO channels. The solution is symmetric and not based on a predefined communication structure. An efficient variant of the echo algorithm, which dynamically builds a spanning tree, allows a parallel and distributed evaluation of the termination predicate in time proportional to the diameter of the communication graph. Concurrent and repeated initiation of the detection algorithm by different processes is possible at any time without prior synchronization due to a subtle method of collision detection and wave extinction, which can be regarded as a distributed election scheme where the average message complexity increases only logarithmically with the number of concurrent initiators. Control messages have a small length and additional communication links are not required. Only a fixed number of simple variables is needed in every process, global knowledge such as the total number of processes or the structure of the network is not used, making the scheme useful for dynamic systems. Several variations of the basic principle are presented, important issues such as message complexity and fault-tolerance are discussed.
12 schema:genre article
13 schema:inLanguage en
14 schema:isAccessibleForFree true
15 schema:isPartOf N131c439d6e8143489127b78432b69e2a
16 Na38b73e38ea2485c8a301bf636ec8054
17 sg:journal.1047644
18 schema:keywords additional communication links
19 algorithm
20 average message complexity
21 basic principles
22 channels
23 collision detection
24 communication graph
25 communication links
26 communication structure
27 complexity
28 computation
29 concurrent initiators
30 control messages
31 counting
32 detection
33 detection algorithm
34 diameter
35 different processes
36 distributed evaluation
37 dynamic systems
38 echo algorithm
39 efficient variant
40 election scheme
41 evaluation
42 extinction
43 global knowledge
44 graph
45 important issue
46 initiation
47 initiator
48 issues
49 knowledge
50 length
51 link
52 message complexity
53 message counting
54 messages
55 method
56 network
57 non-FIFO channels
58 number
59 parallel
60 predicates
61 principles
62 prior synchronization
63 process
64 scheme
65 simple variables
66 small length
67 solution
68 spanning tree
69 structure
70 subtle methods
71 symmetric solutions
72 synchronization
73 system
74 termination
75 termination predicates
76 time
77 total number
78 trees
79 variables
80 variants
81 variation
82 wave extinction
83 schema:name Asynchronous distributed termination—parallel and symmetric solutions with echo algorithms
84 schema:pagination 325-340
85 schema:productId Nb3a9b8811a274200976b3c55f4af0b9e
86 Nbbc1ba70e1f1464181a2f38452ffd16f
87 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024350945
88 https://doi.org/10.1007/bf01840392
89 schema:sdDatePublished 2022-01-01T18:06
90 schema:sdLicense https://scigraph.springernature.com/explorer/license/
91 schema:sdPublisher N4edb03d582064668ad764a7b217d5f7f
92 schema:url https://doi.org/10.1007/bf01840392
93 sgo:license sg:explorer/license/
94 sgo:sdDataset articles
95 rdf:type schema:ScholarlyArticle
96 N131c439d6e8143489127b78432b69e2a schema:volumeNumber 5
97 rdf:type schema:PublicationVolume
98 N362b391e6cff407c8dae551d23422a60 rdf:first sg:person.012317614157.00
99 rdf:rest rdf:nil
100 N4edb03d582064668ad764a7b217d5f7f schema:name Springer Nature - SN SciGraph project
101 rdf:type schema:Organization
102 Na38b73e38ea2485c8a301bf636ec8054 schema:issueNumber 1-4
103 rdf:type schema:PublicationIssue
104 Nb3a9b8811a274200976b3c55f4af0b9e schema:name doi
105 schema:value 10.1007/bf01840392
106 rdf:type schema:PropertyValue
107 Nbbc1ba70e1f1464181a2f38452ffd16f schema:name dimensions_id
108 schema:value pub.1024350945
109 rdf:type schema:PropertyValue
110 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
111 schema:name Information and Computing Sciences
112 rdf:type schema:DefinedTerm
113 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
114 schema:name Computation Theory and Mathematics
115 rdf:type schema:DefinedTerm
116 sg:journal.1047644 schema:issn 0178-4617
117 1432-0541
118 schema:name Algorithmica
119 schema:publisher Springer Nature
120 rdf:type schema:Periodical
121 sg:person.012317614157.00 schema:affiliation grid-institutes:grid.7645.0
122 schema:familyName Mattern
123 schema:givenName Friedemann
124 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012317614157.00
125 rdf:type schema:Person
126 sg:pub.10.1007/978-3-642-82453-1_11 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022937288
127 https://doi.org/10.1007/978-3-642-82453-1_11
128 rdf:type schema:CreativeWork
129 sg:pub.10.1007/978-3-642-95486-3_36 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008436408
130 https://doi.org/10.1007/978-3-642-95486-3_36
131 rdf:type schema:CreativeWork
132 sg:pub.10.1007/bf00263584 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049705236
133 https://doi.org/10.1007/bf00263584
134 rdf:type schema:CreativeWork
135 sg:pub.10.1007/bf01782773 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030093658
136 https://doi.org/10.1007/bf01782773
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 grid-institutes:grid.7645.0 schema:alternateName Department of Computer Science, University of Kaiserslautern, P.O. Box 3049, D-6750, Kaiserslautern, Federal Republic of Germany
142 schema:name Department of Computer Science, University of Kaiserslautern, P.O. Box 3049, D-6750, Kaiserslautern, Federal Republic of Germany
143 rdf:type schema:Organization
 




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


...