Experience with a new distributed termination detection algorithm View Full Text


Ontology type: schema:Chapter      Open Access: True


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": true, 
    "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"
    ], 
    "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-05-10T10:41", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/chapter/chapter_212.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.

102 TRIPLES      23 PREDICATES      68 URIs      61 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 N6fe2be687556456da2b04cfed19d1cab
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 N5b11dcca0914421ba88b14daaa225c86
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Nf5a416a558de4d5e9d81d8603f098f46
12 schema:keywords algorithm
13 applications
14 basic principles
15 behavior
16 case behavior
17 cases
18 channels
19 complete network
20 complexity
21 computation
22 constraints
23 control messages
24 control network
25 detection algorithm
26 experience
27 experimental results
28 general model
29 general undirected graphs
30 graph
31 less control messages
32 message complexity
33 messages
34 method
35 model
36 network
37 non-FIFO channels
38 preliminary experimental results
39 principles
40 process
41 results
42 ring
43 star network
44 symmetric version
45 system
46 termination detection algorithm
47 test application
48 test cases
49 trees
50 undirected graph
51 variants
52 version
53 worst-case behavior
54 schema:name Experience with a new distributed termination detection algorithm
55 schema:pagination 127-143
56 schema:productId N326ff8046ff645ad9b944f9f85e8c638
57 Nb4bb1a901dc0401f81cf79c98ab2c4be
58 schema:publisher N6493843b31d04f7fb072afe13a75e42d
59 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021160369
60 https://doi.org/10.1007/bfb0019800
61 schema:sdDatePublished 2022-05-10T10:41
62 schema:sdLicense https://scigraph.springernature.com/explorer/license/
63 schema:sdPublisher N59bb4c72fa6d404f89ba6271ad234df4
64 schema:url https://doi.org/10.1007/bfb0019800
65 sgo:license sg:explorer/license/
66 sgo:sdDataset chapters
67 rdf:type schema:Chapter
68 N326ff8046ff645ad9b944f9f85e8c638 schema:name dimensions_id
69 schema:value pub.1021160369
70 rdf:type schema:PropertyValue
71 N59bb4c72fa6d404f89ba6271ad234df4 schema:name Springer Nature - SN SciGraph project
72 rdf:type schema:Organization
73 N5b11dcca0914421ba88b14daaa225c86 rdf:first N9d6e93dd474a4c489bbe6d5839de9c9d
74 rdf:rest rdf:nil
75 N6493843b31d04f7fb072afe13a75e42d schema:name Springer Nature
76 rdf:type schema:Organisation
77 N6fe2be687556456da2b04cfed19d1cab rdf:first sg:person.012317614157.00
78 rdf:rest rdf:nil
79 N9d6e93dd474a4c489bbe6d5839de9c9d schema:familyName van Leeuwen
80 schema:givenName J.
81 rdf:type schema:Person
82 Nb4bb1a901dc0401f81cf79c98ab2c4be schema:name doi
83 schema:value 10.1007/bfb0019800
84 rdf:type schema:PropertyValue
85 Nf5a416a558de4d5e9d81d8603f098f46 schema:isbn 978-3-540-19366-1
86 978-3-540-39239-2
87 schema:name Distributed Algorithms
88 rdf:type schema:Book
89 anzsrc-for:10 schema:inDefinedTermSet anzsrc-for:
90 schema:name Technology
91 rdf:type schema:DefinedTerm
92 anzsrc-for:1005 schema:inDefinedTermSet anzsrc-for:
93 schema:name Communications Technologies
94 rdf:type schema:DefinedTerm
95 sg:person.012317614157.00 schema:affiliation grid-institutes:grid.7645.0
96 schema:familyName Mattern
97 schema:givenName Friedemann
98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012317614157.00
99 rdf:type schema:Person
100 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
101 schema:name Department of Computer Science, SFB124, University of Kaiserslautern, P.O. Box 3049, D 6750, Kaiserslautern, Federal Republic of Germany
102 rdf:type schema:Organization
 




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


...