A non-blocking lightweight implementation of causal order message delivery View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1995

AUTHORS

Friedemann Mattern , Stefan Fünfrocken

ABSTRACT

This paper presents an algorithm to implement point-topoint causal order message delivery in distributed systems which does not force the sender to wait and which does not piggyback control information (such as timestamps) on messages. The algorithm is based on a message transmission protocol using low-level acknowledgements between FIFO buffers. We show that on the one hand causal order can easily and efficiently be realized in that way, but that on the other hand the loss of knowledge—induced by not using dependency matrices as in previously known protocols—leads to a slight restriction with respect to the applicability of the new protocol. The advantages of our scheme, however, are obvious because it is non-blocking and the piggybacking of huge control information on messages is avoided. Furthermore, the new algorithm is easily implementable since many distributed systems and low-level transmission protocols already provide message buffers and explicit or implicit message acknowledgements. More... »

PAGES

197-213

Book

TITLE

Theory and Practice in Distributed Systems

ISBN

978-3-540-60042-8
978-3-540-49409-6

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-60042-6_14

DOI

http://dx.doi.org/10.1007/3-540-60042-6_14

DIMENSIONS

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


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, Technical University of Darmstadt, Alexanderstr. 10, D 64283, Darmstadt, Germany", 
          "id": "http://www.grid.ac/institutes/grid.6546.1", 
          "name": [
            "Department of Computer Science, Technical University of Darmstadt, Alexanderstr. 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, Technical University of Darmstadt, Alexanderstr. 10, D 64283, Darmstadt, Germany", 
          "id": "http://www.grid.ac/institutes/grid.6546.1", 
          "name": [
            "Department of Computer Science, Technical University of Darmstadt, Alexanderstr. 10, D 64283, Darmstadt, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "F\u00fcnfrocken", 
        "givenName": "Stefan", 
        "id": "sg:person.015577004545.85", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015577004545.85"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1995", 
    "datePublishedReg": "1995-01-01", 
    "description": "This paper presents an algorithm to implement point-topoint causal order message delivery in distributed systems which does not force the sender to wait and which does not piggyback control information (such as timestamps) on messages. The algorithm is based on a message transmission protocol using low-level acknowledgements between FIFO buffers. We show that on the one hand causal order can easily and efficiently be realized in that way, but that on the other hand the loss of knowledge\u2014induced by not using dependency matrices as in previously known protocols\u2014leads to a slight restriction with respect to the applicability of the new protocol. The advantages of our scheme, however, are obvious because it is non-blocking and the piggybacking of huge control information on messages is avoided. Furthermore, the new algorithm is easily implementable since many distributed systems and low-level transmission protocols already provide message buffers and explicit or implicit message acknowledgements.", 
    "editor": [
      {
        "familyName": "Birman", 
        "givenName": "Kenneth P.", 
        "type": "Person"
      }, 
      {
        "familyName": "Mattern", 
        "givenName": "Friedemann", 
        "type": "Person"
      }, 
      {
        "familyName": "Schiper", 
        "givenName": "Andr\u00e9", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-60042-6_14", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-60042-8", 
        "978-3-540-49409-6"
      ], 
      "name": "Theory and Practice in Distributed Systems", 
      "type": "Book"
    }, 
    "keywords": [
      "order message delivery", 
      "message delivery", 
      "transmission protocol", 
      "control information", 
      "message transmission protocol", 
      "message acknowledgements", 
      "lightweight implementation", 
      "message buffers", 
      "new algorithm", 
      "FIFO buffers", 
      "dependency matrix", 
      "algorithm", 
      "new protocol", 
      "messages", 
      "causal order", 
      "protocol", 
      "information", 
      "piggybacking", 
      "sender", 
      "implementation", 
      "system", 
      "scheme", 
      "advantages", 
      "applicability", 
      "way", 
      "acknowledgement", 
      "order", 
      "hand", 
      "slight restriction", 
      "delivery", 
      "restriction", 
      "buffer", 
      "matrix", 
      "respect", 
      "loss", 
      "paper", 
      "point-topoint causal order message delivery", 
      "causal order message delivery", 
      "low-level acknowledgements", 
      "hand causal order", 
      "huge control information", 
      "low-level transmission protocols", 
      "implicit message acknowledgements", 
      "non-blocking lightweight implementation"
    ], 
    "name": "A non-blocking lightweight implementation of causal order message delivery", 
    "pagination": "197-213", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1008008964"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-60042-6_14"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-60042-6_14", 
      "https://app.dimensions.ai/details/publication/pub.1008008964"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:20", 
    "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_35.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-60042-6_14"
  }
]
 

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/3-540-60042-6_14'

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/3-540-60042-6_14'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-60042-6_14'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-60042-6_14'


 

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

121 TRIPLES      23 PREDICATES      70 URIs      63 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-60042-6_14 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N661d0ec02d2d4280ba62bc0db9e75e5c
4 schema:datePublished 1995
5 schema:datePublishedReg 1995-01-01
6 schema:description This paper presents an algorithm to implement point-topoint causal order message delivery in distributed systems which does not force the sender to wait and which does not piggyback control information (such as timestamps) on messages. The algorithm is based on a message transmission protocol using low-level acknowledgements between FIFO buffers. We show that on the one hand causal order can easily and efficiently be realized in that way, but that on the other hand the loss of knowledge—induced by not using dependency matrices as in previously known protocols—leads to a slight restriction with respect to the applicability of the new protocol. The advantages of our scheme, however, are obvious because it is non-blocking and the piggybacking of huge control information on messages is avoided. Furthermore, the new algorithm is easily implementable since many distributed systems and low-level transmission protocols already provide message buffers and explicit or implicit message acknowledgements.
7 schema:editor N8d0968be7c02443c8e340e0702156e41
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N7679042308a24b83a9c620c62fb22540
12 schema:keywords FIFO buffers
13 acknowledgement
14 advantages
15 algorithm
16 applicability
17 buffer
18 causal order
19 causal order message delivery
20 control information
21 delivery
22 dependency matrix
23 hand
24 hand causal order
25 huge control information
26 implementation
27 implicit message acknowledgements
28 information
29 lightweight implementation
30 loss
31 low-level acknowledgements
32 low-level transmission protocols
33 matrix
34 message acknowledgements
35 message buffers
36 message delivery
37 message transmission protocol
38 messages
39 new algorithm
40 new protocol
41 non-blocking lightweight implementation
42 order
43 order message delivery
44 paper
45 piggybacking
46 point-topoint causal order message delivery
47 protocol
48 respect
49 restriction
50 scheme
51 sender
52 slight restriction
53 system
54 transmission protocol
55 way
56 schema:name A non-blocking lightweight implementation of causal order message delivery
57 schema:pagination 197-213
58 schema:productId N1fad89a7c4064822a27b417ae9679450
59 Nc8271d3de34e49379e35d5d50fdaa17e
60 schema:publisher N3adf803c1e104298b379b04f13b9ee76
61 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008008964
62 https://doi.org/10.1007/3-540-60042-6_14
63 schema:sdDatePublished 2022-01-01T19:20
64 schema:sdLicense https://scigraph.springernature.com/explorer/license/
65 schema:sdPublisher Na11aa423bf3d4692ba4035d8d1e0280a
66 schema:url https://doi.org/10.1007/3-540-60042-6_14
67 sgo:license sg:explorer/license/
68 sgo:sdDataset chapters
69 rdf:type schema:Chapter
70 N1fad89a7c4064822a27b417ae9679450 schema:name doi
71 schema:value 10.1007/3-540-60042-6_14
72 rdf:type schema:PropertyValue
73 N3adf803c1e104298b379b04f13b9ee76 schema:name Springer Nature
74 rdf:type schema:Organisation
75 N51203859972643619a40c8b7a20462be rdf:first Nf260780b2e7a4d2190605f6bb4d8330d
76 rdf:rest N7b390e45a92942d2902ab8e279554820
77 N661d0ec02d2d4280ba62bc0db9e75e5c rdf:first sg:person.012317614157.00
78 rdf:rest N892b506a065a4e6ebc1e71b4fa85fefd
79 N7679042308a24b83a9c620c62fb22540 schema:isbn 978-3-540-49409-6
80 978-3-540-60042-8
81 schema:name Theory and Practice in Distributed Systems
82 rdf:type schema:Book
83 N76f0c35626ab466fb9e71f7d71066acc schema:familyName Schiper
84 schema:givenName André
85 rdf:type schema:Person
86 N79ca7f4f00064b8f888ad71bbba64b77 schema:familyName Birman
87 schema:givenName Kenneth P.
88 rdf:type schema:Person
89 N7b390e45a92942d2902ab8e279554820 rdf:first N76f0c35626ab466fb9e71f7d71066acc
90 rdf:rest rdf:nil
91 N892b506a065a4e6ebc1e71b4fa85fefd rdf:first sg:person.015577004545.85
92 rdf:rest rdf:nil
93 N8d0968be7c02443c8e340e0702156e41 rdf:first N79ca7f4f00064b8f888ad71bbba64b77
94 rdf:rest N51203859972643619a40c8b7a20462be
95 Na11aa423bf3d4692ba4035d8d1e0280a schema:name Springer Nature - SN SciGraph project
96 rdf:type schema:Organization
97 Nc8271d3de34e49379e35d5d50fdaa17e schema:name dimensions_id
98 schema:value pub.1008008964
99 rdf:type schema:PropertyValue
100 Nf260780b2e7a4d2190605f6bb4d8330d schema:familyName Mattern
101 schema:givenName Friedemann
102 rdf:type schema:Person
103 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
104 schema:name Information and Computing Sciences
105 rdf:type schema:DefinedTerm
106 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
107 schema:name Computation Theory and Mathematics
108 rdf:type schema:DefinedTerm
109 sg:person.012317614157.00 schema:affiliation grid-institutes:grid.6546.1
110 schema:familyName Mattern
111 schema:givenName Friedemann
112 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012317614157.00
113 rdf:type schema:Person
114 sg:person.015577004545.85 schema:affiliation grid-institutes:grid.6546.1
115 schema:familyName Fünfrocken
116 schema:givenName Stefan
117 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015577004545.85
118 rdf:type schema:Person
119 grid-institutes:grid.6546.1 schema:alternateName Department of Computer Science, Technical University of Darmstadt, Alexanderstr. 10, D 64283, Darmstadt, Germany
120 schema:name Department of Computer Science, Technical University of Darmstadt, Alexanderstr. 10, D 64283, Darmstadt, Germany
121 rdf:type schema:Organization
 




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


...