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", 
      "fault-tolerant systems", 
      "message delay", 
      "algorithm", 
      "asynchronous model", 
      "synchrony model", 
      "same output", 
      "model", 
      "synchronous model", 
      "system", 
      "output", 
      "message-passing systems", 
      "input", 
      "problem", 
      "delay", 
      "important building blocks", 
      "process", 
      "time", 
      "building blocks", 
      "liveness", 
      "run", 
      "consensus", 
      "clock", 
      "correct processes", 
      "block", 
      "questions", 
      "addition", 
      "absence of failures", 
      "absence", 
      "failure", 
      "period", 
      "half", 
      "safety"
    ], 
    "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-05-20T07:42", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_165.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.

123 TRIPLES      23 PREDICATES      63 URIs      56 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 Nd72c9973d75b4c22bf98eff7318beb8c
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 Ne31b29b2195844669e543d4d6cb1bd10
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N0a57c605ae6c4d3d8943b7f2d1633545
12 schema:keywords absence
13 absence of failures
14 addition
15 algorithm
16 asynchronous model
17 block
18 bounds
19 building blocks
20 clock
21 consensus
22 consensus algorithm
23 consensus problem
24 correct processes
25 delay
26 failure
27 fault-tolerant systems
28 finite period
29 half
30 important building blocks
31 input
32 liveness
33 message delay
34 message-passing systems
35 model
36 output
37 period
38 problem
39 process
40 questions
41 real system
42 run
43 running time
44 safety
45 same output
46 synchronous model
47 synchrony model
48 system
49 time
50 schema:name Open Questions on Consensus Performance inWell-Behaved Runs
51 schema:pagination 35-39
52 schema:productId N98ad7212beac4c2eadc51e6501d1c462
53 Ndff2caa0c9354aebab93927b2eef9907
54 schema:publisher N3ee5bcc0c5954af589f9520d6c52b985
55 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012746036
56 https://doi.org/10.1007/3-540-37795-6_7
57 schema:sdDatePublished 2022-05-20T07:42
58 schema:sdLicense https://scigraph.springernature.com/explorer/license/
59 schema:sdPublisher N427b24c10e5c40a287812874f96bacf5
60 schema:url https://doi.org/10.1007/3-540-37795-6_7
61 sgo:license sg:explorer/license/
62 sgo:sdDataset chapters
63 rdf:type schema:Chapter
64 N0872da6664db46348e1dac52c62fbb53 schema:familyName Weatherspoon
65 schema:givenName Hakim
66 rdf:type schema:Person
67 N0a57c605ae6c4d3d8943b7f2d1633545 schema:isbn 978-3-540-00912-2
68 978-3-540-37795-5
69 schema:name Future Directions in Distributed Computing
70 rdf:type schema:Book
71 N13ff7898a5fe45389f6091daf7c052ba rdf:first N0872da6664db46348e1dac52c62fbb53
72 rdf:rest Nbd40ae78572946b2936be3f7e02f2fa5
73 N3ee5bcc0c5954af589f9520d6c52b985 schema:name Springer Nature
74 rdf:type schema:Organisation
75 N427b24c10e5c40a287812874f96bacf5 schema:name Springer Nature - SN SciGraph project
76 rdf:type schema:Organization
77 N4920386df3c542018e4e1c47ffd04561 rdf:first Nbf9ac9c033c64e8ea8f6255ad9059d94
78 rdf:rest N13ff7898a5fe45389f6091daf7c052ba
79 N56bdb42ed6f945fcb008db1f89d16e33 schema:familyName Zhao
80 schema:givenName Ben Y.
81 rdf:type schema:Person
82 N7e4c75e102dc48b0b358475b7cf372b5 schema:familyName Schiper
83 schema:givenName André
84 rdf:type schema:Person
85 N98ad7212beac4c2eadc51e6501d1c462 schema:name doi
86 schema:value 10.1007/3-540-37795-6_7
87 rdf:type schema:PropertyValue
88 Nbd40ae78572946b2936be3f7e02f2fa5 rdf:first N56bdb42ed6f945fcb008db1f89d16e33
89 rdf:rest rdf:nil
90 Nbf9ac9c033c64e8ea8f6255ad9059d94 schema:familyName Shvartsman
91 schema:givenName Alex A.
92 rdf:type schema:Person
93 Nd72c9973d75b4c22bf98eff7318beb8c rdf:first sg:person.07674464077.03
94 rdf:rest Ne414f06c220e4c70b196a220d0b60d3b
95 Ndff2caa0c9354aebab93927b2eef9907 schema:name dimensions_id
96 schema:value pub.1012746036
97 rdf:type schema:PropertyValue
98 Ne31b29b2195844669e543d4d6cb1bd10 rdf:first N7e4c75e102dc48b0b358475b7cf372b5
99 rdf:rest N4920386df3c542018e4e1c47ffd04561
100 Ne414f06c220e4c70b196a220d0b60d3b rdf:first sg:person.015677075060.35
101 rdf:rest rdf:nil
102 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
103 schema:name Mathematical Sciences
104 rdf:type schema:DefinedTerm
105 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
106 schema:name Applied Mathematics
107 rdf:type schema:DefinedTerm
108 sg:person.015677075060.35 schema:affiliation grid-institutes:grid.9486.3
109 schema:familyName Rajsbaum
110 schema:givenName Sergio
111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015677075060.35
112 rdf:type schema:Person
113 sg:person.07674464077.03 schema:affiliation grid-institutes:grid.6451.6
114 schema:familyName Keidar
115 schema:givenName Idit
116 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07674464077.03
117 rdf:type schema:Person
118 grid-institutes:grid.6451.6 schema:alternateName Department of Electrical Engineering, The Technion, 32000, Haifa, Israel
119 schema:name Department of Electrical Engineering, The Technion, 32000, Haifa, Israel
120 rdf:type schema:Organization
121 grid-institutes:grid.9486.3 schema:alternateName UNAM, Instituto de Matemáticas, Mexico
122 schema:name UNAM, Instituto de Matemáticas, Mexico
123 rdf:type schema:Organization
 




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


...