Early-Delivery Dynamic Atomic Broadcast View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2002-10-24

AUTHORS

Ziv Bar-Joseph , Idit Keidar , Nancy Lynch

ABSTRACT

We consider a problem of atomic broadcast in a dynamic setting where processes may join, leave voluntarily, or fail (by stopping) during the course of computation. We provide a formal definition of the Dynamic Atomic Broadcast problem and present and analyze a new algorithm for its solution in a variant of a synchronous model, where processes have approximately synchronized clocks.Our algorithm exhibits constant message delivery latency in the absence of failures, even during periods when participants join or leave. To the best of our knowledge, this is the first algorithm for totally ordered multicast in a dynamic setting to achieve constant latency bounds in the presence of joins and leaves. When failures occur, the latency bound is linear in the number of actual failures. Our algorithm uses a solution to a variation on the standard distributed consensus problem, in which participants do not know a priori who the other participants are. We define the new problem, which we call Consensus with Uncertain Participants, and give an early-deciding algorithm to solve it. More... »

PAGES

1-16

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-36108-1_1

DOI

http://dx.doi.org/10.1007/3-540-36108-1_1

DIMENSIONS

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


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": "MIT Laboratory for Computer Science, USA", 
          "id": "http://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "MIT Laboratory for Computer Science, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Bar-Joseph", 
        "givenName": "Ziv", 
        "id": "sg:person.0642257765.73", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0642257765.73"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Technion Department of Electrical Engineering, USA", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Technion Department of Electrical Engineering, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Keidar", 
        "givenName": "Idit", 
        "id": "sg:person.07674464077.03", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07674464077.03"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "MIT Laboratory for Computer Science, USA", 
          "id": "http://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "MIT Laboratory for Computer Science, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lynch", 
        "givenName": "Nancy", 
        "id": "sg:person.016211762423.01", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016211762423.01"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2002-10-24", 
    "datePublishedReg": "2002-10-24", 
    "description": "We consider a problem of atomic broadcast in a dynamic setting where processes may join, leave voluntarily, or fail (by stopping) during the course of computation. We provide a formal definition of the Dynamic Atomic Broadcast problem and present and analyze a new algorithm for its solution in a variant of a synchronous model, where processes have approximately synchronized clocks.Our algorithm exhibits constant message delivery latency in the absence of failures, even during periods when participants join or leave. To the best of our knowledge, this is the first algorithm for totally ordered multicast in a dynamic setting to achieve constant latency bounds in the presence of joins and leaves. When failures occur, the latency bound is linear in the number of actual failures. Our algorithm uses a solution to a variation on the standard distributed consensus problem, in which participants do not know a priori who the other participants are. We define the new problem, which we call Consensus with Uncertain Participants, and give an early-deciding algorithm to solve it.", 
    "editor": [
      {
        "familyName": "Malkhi", 
        "givenName": "Dahlia", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-36108-1_1", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-00073-0", 
        "978-3-540-36108-4"
      ], 
      "name": "Distributed Computing", 
      "type": "Book"
    }, 
    "keywords": [
      "failure", 
      "participants", 
      "setting", 
      "course", 
      "latency", 
      "variants", 
      "absence", 
      "period", 
      "presence", 
      "number", 
      "consensus", 
      "problem", 
      "process", 
      "definition", 
      "model", 
      "absence of failures", 
      "knowledge", 
      "course of computation", 
      "clock", 
      "actual failure", 
      "variation", 
      "new problems", 
      "dynamic setting", 
      "computation", 
      "broadcast problem", 
      "algorithm", 
      "solution", 
      "message delivery latency", 
      "delivery latency", 
      "latency bounds", 
      "bounds", 
      "leaves", 
      "uncertain participants", 
      "atomic broadcast", 
      "broadcast", 
      "formal definition", 
      "new algorithm", 
      "synchronous model", 
      "first algorithm", 
      "multicast", 
      "presence of joins", 
      "join", 
      "consensus problem", 
      "Dynamic Atomic Broadcast problem", 
      "Atomic Broadcast problem", 
      "constant message delivery latency", 
      "constant latency bounds", 
      "Delivery Dynamic Atomic Broadcast", 
      "Dynamic Atomic Broadcast"
    ], 
    "name": "Early-Delivery Dynamic Atomic Broadcast", 
    "pagination": "1-16", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1049755264"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-36108-1_1"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-36108-1_1", 
      "https://app.dimensions.ai/details/publication/pub.1049755264"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:15", 
    "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_253.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-36108-1_1"
  }
]
 

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-36108-1_1'

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-36108-1_1'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-36108-1_1'

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-36108-1_1'


 

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

126 TRIPLES      23 PREDICATES      74 URIs      67 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-36108-1_1 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nf42e08460b144e0bbc2e6f46a8a55a8f
4 schema:datePublished 2002-10-24
5 schema:datePublishedReg 2002-10-24
6 schema:description We consider a problem of atomic broadcast in a dynamic setting where processes may join, leave voluntarily, or fail (by stopping) during the course of computation. We provide a formal definition of the Dynamic Atomic Broadcast problem and present and analyze a new algorithm for its solution in a variant of a synchronous model, where processes have approximately synchronized clocks.Our algorithm exhibits constant message delivery latency in the absence of failures, even during periods when participants join or leave. To the best of our knowledge, this is the first algorithm for totally ordered multicast in a dynamic setting to achieve constant latency bounds in the presence of joins and leaves. When failures occur, the latency bound is linear in the number of actual failures. Our algorithm uses a solution to a variation on the standard distributed consensus problem, in which participants do not know a priori who the other participants are. We define the new problem, which we call Consensus with Uncertain Participants, and give an early-deciding algorithm to solve it.
7 schema:editor N5c313194a2f5408ca50a52a585f9d0ab
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Ne3fb4fee97cd4226838dc89574dd1b00
12 schema:keywords Atomic Broadcast problem
13 Delivery Dynamic Atomic Broadcast
14 Dynamic Atomic Broadcast
15 Dynamic Atomic Broadcast problem
16 absence
17 absence of failures
18 actual failure
19 algorithm
20 atomic broadcast
21 bounds
22 broadcast
23 broadcast problem
24 clock
25 computation
26 consensus
27 consensus problem
28 constant latency bounds
29 constant message delivery latency
30 course
31 course of computation
32 definition
33 delivery latency
34 dynamic setting
35 failure
36 first algorithm
37 formal definition
38 join
39 knowledge
40 latency
41 latency bounds
42 leaves
43 message delivery latency
44 model
45 multicast
46 new algorithm
47 new problems
48 number
49 participants
50 period
51 presence
52 presence of joins
53 problem
54 process
55 setting
56 solution
57 synchronous model
58 uncertain participants
59 variants
60 variation
61 schema:name Early-Delivery Dynamic Atomic Broadcast
62 schema:pagination 1-16
63 schema:productId N6634747336af4bec9e9700c41c4eab58
64 Nb8b166a694fc4833afec61fbe261ee98
65 schema:publisher Na4fe15c83f8e478190ac8ad92a702f56
66 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049755264
67 https://doi.org/10.1007/3-540-36108-1_1
68 schema:sdDatePublished 2022-01-01T19:15
69 schema:sdLicense https://scigraph.springernature.com/explorer/license/
70 schema:sdPublisher Nc3ee9f63887f4d23acc1c72af3a432e3
71 schema:url https://doi.org/10.1007/3-540-36108-1_1
72 sgo:license sg:explorer/license/
73 sgo:sdDataset chapters
74 rdf:type schema:Chapter
75 N21fff97993d5426eac21f8e364cffc19 schema:familyName Malkhi
76 schema:givenName Dahlia
77 rdf:type schema:Person
78 N5c313194a2f5408ca50a52a585f9d0ab rdf:first N21fff97993d5426eac21f8e364cffc19
79 rdf:rest rdf:nil
80 N6634747336af4bec9e9700c41c4eab58 schema:name doi
81 schema:value 10.1007/3-540-36108-1_1
82 rdf:type schema:PropertyValue
83 N6b33f4ae8d3b42128cc649687ef313b1 rdf:first sg:person.07674464077.03
84 rdf:rest Ne1d4c463e9244ead83574f06f31d96c7
85 Na4fe15c83f8e478190ac8ad92a702f56 schema:name Springer Nature
86 rdf:type schema:Organisation
87 Nb8b166a694fc4833afec61fbe261ee98 schema:name dimensions_id
88 schema:value pub.1049755264
89 rdf:type schema:PropertyValue
90 Nc3ee9f63887f4d23acc1c72af3a432e3 schema:name Springer Nature - SN SciGraph project
91 rdf:type schema:Organization
92 Ne1d4c463e9244ead83574f06f31d96c7 rdf:first sg:person.016211762423.01
93 rdf:rest rdf:nil
94 Ne3fb4fee97cd4226838dc89574dd1b00 schema:isbn 978-3-540-00073-0
95 978-3-540-36108-4
96 schema:name Distributed Computing
97 rdf:type schema:Book
98 Nf42e08460b144e0bbc2e6f46a8a55a8f rdf:first sg:person.0642257765.73
99 rdf:rest N6b33f4ae8d3b42128cc649687ef313b1
100 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
101 schema:name Information and Computing Sciences
102 rdf:type schema:DefinedTerm
103 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
104 schema:name Computation Theory and Mathematics
105 rdf:type schema:DefinedTerm
106 sg:person.016211762423.01 schema:affiliation grid-institutes:grid.116068.8
107 schema:familyName Lynch
108 schema:givenName Nancy
109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016211762423.01
110 rdf:type schema:Person
111 sg:person.0642257765.73 schema:affiliation grid-institutes:grid.116068.8
112 schema:familyName Bar-Joseph
113 schema:givenName Ziv
114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0642257765.73
115 rdf:type schema:Person
116 sg:person.07674464077.03 schema:affiliation grid-institutes:None
117 schema:familyName Keidar
118 schema:givenName Idit
119 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07674464077.03
120 rdf:type schema:Person
121 grid-institutes:None schema:alternateName Technion Department of Electrical Engineering, USA
122 schema:name Technion Department of Electrical Engineering, USA
123 rdf:type schema:Organization
124 grid-institutes:grid.116068.8 schema:alternateName MIT Laboratory for Computer Science, USA
125 schema:name MIT Laboratory for Computer Science, USA
126 rdf:type schema:Organization
 




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


...