Open Questions on Consensus Performance inWell-Behaved Runs View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2003-03-14

AUTHORS

Idit Keidar , Sergio Rajsbaum

ABSTRACT

We consider the consensus problem in a message-passing system where processes can crash: Each process has an input, and each correct process must decide on an output, such that all correct processes decide on the same output, and this output is the input of one of the processes. Consensus is an important building block for fault-tolerant systems. It is well-known that consensus is not solvable in an asynchronous model even if only one process can crash [7.13]. However, real systems are not completely asynchronous. Some partially synchronous models [7.12], [7.10] where consensus is solvable better approximate real systems.We consider a partial synchronymodel defined as follows [7.12]1: (1) processes have bounded drift clocks; (2) there are known bounds on processing times and message delays; and (3) less than half of the processes can crash. In addition, this model allows the system to be unstable, where the bounds in (2) do not hold for an unbounded but finite period, but it must eventually enter a stableperiod where the bounds do hold.A consensus algorithm for the partial synchrony model never violates safety, and guarantees liveness once the system becomes stable. Algorithms for this model are called indulgent in [7.16]. What can we say about the running time of consensus algorithms in a partial synchrony model? Unfortunately, even in the absence of failures, any consensus algorithm in this model is bound to have unbounded running times, by [7.13]. More... »

PAGES

35-39

Book

TITLE

Future Directions in Distributed Computing

ISBN

978-3-540-00912-2
978-3-540-37795-5

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-37795-6_7

DOI

http://dx.doi.org/10.1007/3-540-37795-6_7

DIMENSIONS

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


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/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0102", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Applied Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Electrical Engineering, The Technion, 32000, Haifa, Israel", 
          "id": "http://www.grid.ac/institutes/grid.6451.6", 
          "name": [
            "Department of Electrical Engineering, The Technion, 32000, Haifa, Israel"
          ], 
          "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": "UNAM, Instituto de Matem\u00e1ticas, Mexico", 
          "id": "http://www.grid.ac/institutes/grid.9486.3", 
          "name": [
            "UNAM, Instituto de Matem\u00e1ticas, Mexico"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Rajsbaum", 
        "givenName": "Sergio", 
        "id": "sg:person.015677075060.35", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015677075060.35"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2003-03-14", 
    "datePublishedReg": "2003-03-14", 
    "description": "We consider the consensus problem in a message-passing system where processes can crash: Each process has an input, and each correct process must decide on an output, such that all correct processes decide on the same output, and this output is the input of one of the processes. Consensus is an important building block for fault-tolerant systems. It is well-known that consensus is not solvable in an asynchronous model even if only one process can crash [7.13]. However, real systems are not completely asynchronous. Some partially synchronous models [7.12], [7.10] where consensus is solvable better approximate real systems.We consider a partial synchronymodel defined as follows [7.12]1: (1) processes have bounded drift clocks; (2) there are known bounds on processing times and message delays; and (3) less than half of the processes can crash. In addition, this model allows the system to be unstable, where the bounds in (2) do not hold for an unbounded but finite period, but it must eventually enter a stableperiod where the bounds do hold.A consensus algorithm for the partial synchrony model never violates safety, and guarantees liveness once the system becomes stable. Algorithms for this model are called indulgent in [7.16]. What can we say about the running time of consensus algorithms in a partial synchrony model? Unfortunately, even in the absence of failures, any consensus algorithm in this model is bound to have unbounded running times, by [7.13].", 
    "editor": [
      {
        "familyName": "Schiper", 
        "givenName": "Andr\u00e9", 
        "type": "Person"
      }, 
      {
        "familyName": "Shvartsman", 
        "givenName": "Alex A.", 
        "type": "Person"
      }, 
      {
        "familyName": "Weatherspoon", 
        "givenName": "Hakim", 
        "type": "Person"
      }, 
      {
        "familyName": "Zhao", 
        "givenName": "Ben Y.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-37795-6_7", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-00912-2", 
        "978-3-540-37795-5"
      ], 
      "name": "Future Directions in Distributed Computing", 
      "type": "Book"
    }, 
    "keywords": [
      "consensus algorithm", 
      "real system", 
      "running time", 
      "consensus problem", 
      "bounds", 
      "finite period", 
      "message delay", 
      "asynchronous model", 
      "fault-tolerant systems", 
      "algorithm", 
      "same output", 
      "synchrony model", 
      "model", 
      "message-passing systems", 
      "system", 
      "input", 
      "output", 
      "problem", 
      "synchronous model", 
      "delay", 
      "process", 
      "liveness", 
      "time", 
      "absence of failures", 
      "run", 
      "consensus", 
      "building blocks", 
      "important building blocks", 
      "questions", 
      "block", 
      "addition", 
      "clock", 
      "correct processes", 
      "failure", 
      "period", 
      "safety", 
      "absence", 
      "half", 
      "partial synchrony model", 
      "solvable better approximate real systems", 
      "better approximate real systems", 
      "approximate real systems", 
      "partial synchronymodel", 
      "synchronymodel", 
      "drift clocks", 
      "stableperiod", 
      "unbounded running times", 
      "Consensus Performance inWell", 
      "Performance inWell", 
      "inWell"
    ], 
    "name": "Open Questions on Consensus Performance inWell-Behaved Runs", 
    "pagination": "35-39", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1012746036"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-37795-6_7"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-37795-6_7", 
      "https://app.dimensions.ai/details/publication/pub.1012746036"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:27", 
    "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_84.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-37795-6_7"
  }
]
 

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-37795-6_7'

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-37795-6_7'

Turtle is a human-readable linked data format.

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

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-37795-6_7'


 

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

135 TRIPLES      23 PREDICATES      75 URIs      68 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-37795-6_7 schema:about anzsrc-for:01
2 anzsrc-for:0102
3 schema:author N4f8d5352142f47efa73742c83c0ffad3
4 schema:datePublished 2003-03-14
5 schema:datePublishedReg 2003-03-14
6 schema:description We consider the consensus problem in a message-passing system where processes can crash: Each process has an input, and each correct process must decide on an output, such that all correct processes decide on the same output, and this output is the input of one of the processes. Consensus is an important building block for fault-tolerant systems. It is well-known that consensus is not solvable in an asynchronous model even if only one process can crash [7.13]. However, real systems are not completely asynchronous. Some partially synchronous models [7.12], [7.10] where consensus is solvable better approximate real systems.We consider a partial synchronymodel defined as follows [7.12]1: (1) processes have bounded drift clocks; (2) there are known bounds on processing times and message delays; and (3) less than half of the processes can crash. In addition, this model allows the system to be unstable, where the bounds in (2) do not hold for an unbounded but finite period, but it must eventually enter a stableperiod where the bounds do hold.A consensus algorithm for the partial synchrony model never violates safety, and guarantees liveness once the system becomes stable. Algorithms for this model are called indulgent in [7.16]. What can we say about the running time of consensus algorithms in a partial synchrony model? Unfortunately, even in the absence of failures, any consensus algorithm in this model is bound to have unbounded running times, by [7.13].
7 schema:editor Na4fd19a5c9834a19bdf87a9db2789bbb
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N961ae351f9f246aa95dc5813f2fa792c
12 schema:keywords Consensus Performance inWell
13 Performance inWell
14 absence
15 absence of failures
16 addition
17 algorithm
18 approximate real systems
19 asynchronous model
20 better approximate real systems
21 block
22 bounds
23 building blocks
24 clock
25 consensus
26 consensus algorithm
27 consensus problem
28 correct processes
29 delay
30 drift clocks
31 failure
32 fault-tolerant systems
33 finite period
34 half
35 important building blocks
36 inWell
37 input
38 liveness
39 message delay
40 message-passing systems
41 model
42 output
43 partial synchrony model
44 partial synchronymodel
45 period
46 problem
47 process
48 questions
49 real system
50 run
51 running time
52 safety
53 same output
54 solvable better approximate real systems
55 stableperiod
56 synchronous model
57 synchrony model
58 synchronymodel
59 system
60 time
61 unbounded running times
62 schema:name Open Questions on Consensus Performance inWell-Behaved Runs
63 schema:pagination 35-39
64 schema:productId Na265d3a1ef0443639a0b0ab04aeafaf1
65 Ne49626b834784a12bbac83984e4db273
66 schema:publisher N8b96b12e8da44e55a8ef6cd6e0f0f050
67 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012746036
68 https://doi.org/10.1007/3-540-37795-6_7
69 schema:sdDatePublished 2022-01-01T19:27
70 schema:sdLicense https://scigraph.springernature.com/explorer/license/
71 schema:sdPublisher N2f466c1dab8248fb894c23b6a678f88c
72 schema:url https://doi.org/10.1007/3-540-37795-6_7
73 sgo:license sg:explorer/license/
74 sgo:sdDataset chapters
75 rdf:type schema:Chapter
76 N11c0b6c3e7b446448399e2163d406dcf rdf:first Nf73302285f2344a9b256da1ae313d993
77 rdf:rest N8f67b90762e945babdfd1e49f0956933
78 N2f466c1dab8248fb894c23b6a678f88c schema:name Springer Nature - SN SciGraph project
79 rdf:type schema:Organization
80 N4b08e8a249f64095a1e3cf18a8bc3f93 schema:familyName Zhao
81 schema:givenName Ben Y.
82 rdf:type schema:Person
83 N4f8d5352142f47efa73742c83c0ffad3 rdf:first sg:person.07674464077.03
84 rdf:rest Nced3b2a181d54166acf619ef09a18626
85 N8b96b12e8da44e55a8ef6cd6e0f0f050 schema:name Springer Nature
86 rdf:type schema:Organisation
87 N8f67b90762e945babdfd1e49f0956933 rdf:first N4b08e8a249f64095a1e3cf18a8bc3f93
88 rdf:rest rdf:nil
89 N961ae351f9f246aa95dc5813f2fa792c schema:isbn 978-3-540-00912-2
90 978-3-540-37795-5
91 schema:name Future Directions in Distributed Computing
92 rdf:type schema:Book
93 Na265d3a1ef0443639a0b0ab04aeafaf1 schema:name doi
94 schema:value 10.1007/3-540-37795-6_7
95 rdf:type schema:PropertyValue
96 Na4fd19a5c9834a19bdf87a9db2789bbb rdf:first Nf46a788b65744a4684dc167522c83148
97 rdf:rest Nd4f91c67300d450886c27bf41637e06c
98 Nced3b2a181d54166acf619ef09a18626 rdf:first sg:person.015677075060.35
99 rdf:rest rdf:nil
100 Ncf1223c39e7b470fbf8c93f6f4df9cc2 schema:familyName Shvartsman
101 schema:givenName Alex A.
102 rdf:type schema:Person
103 Nd4f91c67300d450886c27bf41637e06c rdf:first Ncf1223c39e7b470fbf8c93f6f4df9cc2
104 rdf:rest N11c0b6c3e7b446448399e2163d406dcf
105 Ne49626b834784a12bbac83984e4db273 schema:name dimensions_id
106 schema:value pub.1012746036
107 rdf:type schema:PropertyValue
108 Nf46a788b65744a4684dc167522c83148 schema:familyName Schiper
109 schema:givenName André
110 rdf:type schema:Person
111 Nf73302285f2344a9b256da1ae313d993 schema:familyName Weatherspoon
112 schema:givenName Hakim
113 rdf:type schema:Person
114 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
115 schema:name Mathematical Sciences
116 rdf:type schema:DefinedTerm
117 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
118 schema:name Applied Mathematics
119 rdf:type schema:DefinedTerm
120 sg:person.015677075060.35 schema:affiliation grid-institutes:grid.9486.3
121 schema:familyName Rajsbaum
122 schema:givenName Sergio
123 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015677075060.35
124 rdf:type schema:Person
125 sg:person.07674464077.03 schema:affiliation grid-institutes:grid.6451.6
126 schema:familyName Keidar
127 schema:givenName Idit
128 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07674464077.03
129 rdf:type schema:Person
130 grid-institutes:grid.6451.6 schema:alternateName Department of Electrical Engineering, The Technion, 32000, Haifa, Israel
131 schema:name Department of Electrical Engineering, The Technion, 32000, Haifa, Israel
132 rdf:type schema:Organization
133 grid-institutes:grid.9486.3 schema:alternateName UNAM, Instituto de Matemáticas, Mexico
134 schema:name UNAM, Instituto de Matemáticas, Mexico
135 rdf:type schema:Organization
 




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


...