Experience with a new distributed termination detection algorithm View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1988

AUTHORS

Friedemann Mattern

ABSTRACT

A termination detection algorithm for a general model of distributed computations where processes communicate over asynchronous non-FIFO channels is presented. It has O(mn) message complexity if the control network is a ring, a (spanning) tree, or a general undirected graph and O(m) message complexity on star networks and complete networks. Several variants of the basic principle are discussed, one of which is a symmetric version where any process can start the algorithm independently from the other processes. Preliminary experimental results show that far less control messages than indicated by the worst case behavior are usually generated. In a distributed puzzle-solving system used as a test application only about √m control messages have been counted. The constraint based puzzle-solving method is explained and several test cases are reported. More... »

PAGES

127-143

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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/10", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Technology", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1005", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Communications Technologies", 
        "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"
      }
    ], 
    "datePublished": "1988", 
    "datePublishedReg": "1988-01-01", 
    "description": "A termination detection algorithm for a general model of distributed computations where processes communicate over asynchronous non-FIFO channels is presented. It has O(mn) message complexity if the control network is a ring, a (spanning) tree, or a general undirected graph and O(m) message complexity on star networks and complete networks. Several variants of the basic principle are discussed, one of which is a symmetric version where any process can start the algorithm independently from the other processes. Preliminary experimental results show that far less control messages than indicated by the worst case behavior are usually generated. In a distributed puzzle-solving system used as a test application only about \u221am control messages have been counted. The constraint based puzzle-solving method is explained and several test cases are reported.", 
    "editor": [
      {
        "familyName": "van Leeuwen", 
        "givenName": "J.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/bfb0019800", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-19366-1", 
        "978-3-540-39239-2"
      ], 
      "name": "Distributed Algorithms", 
      "type": "Book"
    }, 
    "keywords": [
      "termination detection algorithm", 
      "message complexity", 
      "control messages", 
      "detection algorithm", 
      "less control messages", 
      "non-FIFO channels", 
      "worst-case behavior", 
      "general undirected graphs", 
      "preliminary experimental results", 
      "case behavior", 
      "star network", 
      "undirected graph", 
      "algorithm", 
      "complete network", 
      "test application", 
      "test cases", 
      "network", 
      "control network", 
      "experimental results", 
      "messages", 
      "complexity", 
      "general model", 
      "graph", 
      "computation", 
      "basic principles", 
      "constraints", 
      "applications", 
      "trees", 
      "symmetric version", 
      "process", 
      "system", 
      "version", 
      "model", 
      "method", 
      "channels", 
      "principles", 
      "experience", 
      "results", 
      "variants", 
      "behavior", 
      "cases", 
      "ring", 
      "asynchronous non-FIFO channels", 
      "distributed puzzle-solving system", 
      "puzzle-solving system", 
      "puzzle-solving method"
    ], 
    "name": "Experience with a new distributed termination detection algorithm", 
    "pagination": "127-143", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1021160369"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bfb0019800"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/bfb0019800", 
      "https://app.dimensions.ai/details/publication/pub.1021160369"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19: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/chapter/chapter_117.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/bfb0019800"
  }
]
 

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

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

Turtle is a human-readable linked data format.

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

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

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


 

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

106 TRIPLES      23 PREDICATES      72 URIs      65 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bfb0019800 schema:about anzsrc-for:10
2 anzsrc-for:1005
3 schema:author Nb568d55be8df4608b6e4ed068b9c9cd5
4 schema:datePublished 1988
5 schema:datePublishedReg 1988-01-01
6 schema:description A termination detection algorithm for a general model of distributed computations where processes communicate over asynchronous non-FIFO channels is presented. It has O(mn) message complexity if the control network is a ring, a (spanning) tree, or a general undirected graph and O(m) message complexity on star networks and complete networks. Several variants of the basic principle are discussed, one of which is a symmetric version where any process can start the algorithm independently from the other processes. Preliminary experimental results show that far less control messages than indicated by the worst case behavior are usually generated. In a distributed puzzle-solving system used as a test application only about √m control messages have been counted. The constraint based puzzle-solving method is explained and several test cases are reported.
7 schema:editor Nb8ba1dbb34be44058c19839a2eb986b6
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Nc27685514b544376b3a8dae215b8b948
12 schema:keywords algorithm
13 applications
14 asynchronous non-FIFO channels
15 basic principles
16 behavior
17 case behavior
18 cases
19 channels
20 complete network
21 complexity
22 computation
23 constraints
24 control messages
25 control network
26 detection algorithm
27 distributed puzzle-solving system
28 experience
29 experimental results
30 general model
31 general undirected graphs
32 graph
33 less control messages
34 message complexity
35 messages
36 method
37 model
38 network
39 non-FIFO channels
40 preliminary experimental results
41 principles
42 process
43 puzzle-solving method
44 puzzle-solving system
45 results
46 ring
47 star network
48 symmetric version
49 system
50 termination detection algorithm
51 test application
52 test cases
53 trees
54 undirected graph
55 variants
56 version
57 worst-case behavior
58 schema:name Experience with a new distributed termination detection algorithm
59 schema:pagination 127-143
60 schema:productId N5c598baf4c6a4b5d9631740f36ab06b6
61 Nb051708ea0bf445e9184b289cd1717e2
62 schema:publisher N674d018b538f46d09492df6659571a26
63 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021160369
64 https://doi.org/10.1007/bfb0019800
65 schema:sdDatePublished 2022-01-01T19:07
66 schema:sdLicense https://scigraph.springernature.com/explorer/license/
67 schema:sdPublisher Nf6696fa441084d8f979117d28a665044
68 schema:url https://doi.org/10.1007/bfb0019800
69 sgo:license sg:explorer/license/
70 sgo:sdDataset chapters
71 rdf:type schema:Chapter
72 N5c598baf4c6a4b5d9631740f36ab06b6 schema:name dimensions_id
73 schema:value pub.1021160369
74 rdf:type schema:PropertyValue
75 N674d018b538f46d09492df6659571a26 schema:name Springer Nature
76 rdf:type schema:Organisation
77 N6f7e9339b47840f2b305870b68d880b7 schema:familyName van Leeuwen
78 schema:givenName J.
79 rdf:type schema:Person
80 Nb051708ea0bf445e9184b289cd1717e2 schema:name doi
81 schema:value 10.1007/bfb0019800
82 rdf:type schema:PropertyValue
83 Nb568d55be8df4608b6e4ed068b9c9cd5 rdf:first sg:person.012317614157.00
84 rdf:rest rdf:nil
85 Nb8ba1dbb34be44058c19839a2eb986b6 rdf:first N6f7e9339b47840f2b305870b68d880b7
86 rdf:rest rdf:nil
87 Nc27685514b544376b3a8dae215b8b948 schema:isbn 978-3-540-19366-1
88 978-3-540-39239-2
89 schema:name Distributed Algorithms
90 rdf:type schema:Book
91 Nf6696fa441084d8f979117d28a665044 schema:name Springer Nature - SN SciGraph project
92 rdf:type schema:Organization
93 anzsrc-for:10 schema:inDefinedTermSet anzsrc-for:
94 schema:name Technology
95 rdf:type schema:DefinedTerm
96 anzsrc-for:1005 schema:inDefinedTermSet anzsrc-for:
97 schema:name Communications Technologies
98 rdf:type schema:DefinedTerm
99 sg:person.012317614157.00 schema:affiliation grid-institutes:grid.7645.0
100 schema:familyName Mattern
101 schema:givenName Friedemann
102 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012317614157.00
103 rdf:type schema:Person
104 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
105 schema:name Department of Computer Science, SFB124, University of Kaiserslautern, P.O. Box 3049, D 6750, Kaiserslautern, Federal Republic of Germany
106 rdf:type schema:Organization
 




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


...