On Liveness of Dynamic Storage View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2017-12-30

AUTHORS

Alexander Spiegelman , Idit Keidar

ABSTRACT

Dynamic distributed storage algorithms such as DynaStore, Reconfigurable Paxos, RAMBO, and RDS, do not ensure liveness (wait-freedom) in asynchronous runs with infinitely many reconfigurations. We prove that this is inherent for asynchronous dynamic storage algorithms. Our result holds even if only one process may fail, provided that machines that were successfully removed from the system’s configuration can be switched off by a system administrator. To circumvent this result, we define a dynamic eventually perfect failure detector, and present an algorithm that uses it to emulate wait-free dynamic atomic storage. Though some of the previous algorithms have been designed for eventually synchronous models, to the best of our knowledge, our algorithm is the first to ensure liveness for all operations without restricting the reconfiguration rate. More... »

PAGES

356-376

Book

TITLE

Structural Information and Communication Complexity

ISBN

978-3-319-72049-4
978-3-319-72050-0

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-72050-0_21

DOI

http://dx.doi.org/10.1007/978-3-319-72050-0_21

DIMENSIONS

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


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": "Viterbi EE Department, Technion, Haifa, Israel", 
          "id": "http://www.grid.ac/institutes/grid.6451.6", 
          "name": [
            "Viterbi EE Department, Technion, Haifa, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Spiegelman", 
        "givenName": "Alexander", 
        "id": "sg:person.010661345305.24", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010661345305.24"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Viterbi EE Department, Technion, Haifa, Israel", 
          "id": "http://www.grid.ac/institutes/grid.6451.6", 
          "name": [
            "Viterbi EE Department, Technion, 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"
      }
    ], 
    "datePublished": "2017-12-30", 
    "datePublishedReg": "2017-12-30", 
    "description": "Dynamic distributed storage algorithms such as DynaStore, Reconfigurable Paxos, RAMBO, and RDS, do not ensure liveness (wait-freedom) in asynchronous runs with infinitely many reconfigurations. We prove that this is inherent for asynchronous dynamic storage algorithms. Our result holds even if only one process may fail, provided that machines that were successfully removed from the system\u2019s configuration can be switched off by a system administrator. To circumvent this result, we define a dynamic eventually perfect failure detector, and present an algorithm that uses it to emulate wait-free dynamic atomic storage. Though some of the previous algorithms have been designed for eventually synchronous models, to the best of our knowledge, our algorithm is the first to ensure liveness for all operations without restricting the reconfiguration rate.", 
    "editor": [
      {
        "familyName": "Das", 
        "givenName": "Shantanu", 
        "type": "Person"
      }, 
      {
        "familyName": "Tixeuil", 
        "givenName": "Sebastien", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-72050-0_21", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-319-72049-4", 
        "978-3-319-72050-0"
      ], 
      "name": "Structural Information and Communication Complexity", 
      "type": "Book"
    }, 
    "keywords": [
      "storage algorithm", 
      "system administrators", 
      "previous algorithms", 
      "synchronous model", 
      "algorithm", 
      "liveness", 
      "failure detector", 
      "system configuration", 
      "perfect failure detector", 
      "reconfiguration rate", 
      "dynamic storage", 
      "Paxos", 
      "reconfiguration", 
      "machine", 
      "storage", 
      "administrators", 
      "operation", 
      "configuration", 
      "DynaStore", 
      "knowledge", 
      "results", 
      "atomic storage", 
      "model", 
      "detector", 
      "run", 
      "process", 
      "dynamics", 
      "RDS", 
      "rate", 
      "Rambo", 
      "Reconfigurable Paxos", 
      "asynchronous runs", 
      "asynchronous dynamic storage algorithms", 
      "dynamic storage algorithms", 
      "wait-free dynamic atomic storage", 
      "dynamic atomic storage"
    ], 
    "name": "On Liveness of Dynamic Storage", 
    "pagination": "356-376", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1100110744"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-72050-0_21"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-72050-0_21", 
      "https://app.dimensions.ai/details/publication/pub.1100110744"
    ], 
    "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/978-3-319-72050-0_21"
  }
]
 

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/978-3-319-72050-0_21'

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/978-3-319-72050-0_21'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-72050-0_21'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-72050-0_21'


 

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

108 TRIPLES      23 PREDICATES      61 URIs      54 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-72050-0_21 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N683f24a8237744e3b266bdbe8f5da2d7
4 schema:datePublished 2017-12-30
5 schema:datePublishedReg 2017-12-30
6 schema:description Dynamic distributed storage algorithms such as DynaStore, Reconfigurable Paxos, RAMBO, and RDS, do not ensure liveness (wait-freedom) in asynchronous runs with infinitely many reconfigurations. We prove that this is inherent for asynchronous dynamic storage algorithms. Our result holds even if only one process may fail, provided that machines that were successfully removed from the system’s configuration can be switched off by a system administrator. To circumvent this result, we define a dynamic eventually perfect failure detector, and present an algorithm that uses it to emulate wait-free dynamic atomic storage. Though some of the previous algorithms have been designed for eventually synchronous models, to the best of our knowledge, our algorithm is the first to ensure liveness for all operations without restricting the reconfiguration rate.
7 schema:editor N323b3f2197ab4c97956cf5b57bde001f
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Nbbc6874163af4e03a105ae6571f9958b
12 schema:keywords DynaStore
13 Paxos
14 RDS
15 Rambo
16 Reconfigurable Paxos
17 administrators
18 algorithm
19 asynchronous dynamic storage algorithms
20 asynchronous runs
21 atomic storage
22 configuration
23 detector
24 dynamic atomic storage
25 dynamic storage
26 dynamic storage algorithms
27 dynamics
28 failure detector
29 knowledge
30 liveness
31 machine
32 model
33 operation
34 perfect failure detector
35 previous algorithms
36 process
37 rate
38 reconfiguration
39 reconfiguration rate
40 results
41 run
42 storage
43 storage algorithm
44 synchronous model
45 system administrators
46 system configuration
47 wait-free dynamic atomic storage
48 schema:name On Liveness of Dynamic Storage
49 schema:pagination 356-376
50 schema:productId Nb8f126a5ef00437a81a13305c6279456
51 Nc31a7384d221492596f77dc3654d6894
52 schema:publisher Nfef89c10a5ad4214a3c0bbaa023ce250
53 schema:sameAs https://app.dimensions.ai/details/publication/pub.1100110744
54 https://doi.org/10.1007/978-3-319-72050-0_21
55 schema:sdDatePublished 2022-01-01T19:15
56 schema:sdLicense https://scigraph.springernature.com/explorer/license/
57 schema:sdPublisher Nf6335b432c174be4a4aa4b9153ab8eed
58 schema:url https://doi.org/10.1007/978-3-319-72050-0_21
59 sgo:license sg:explorer/license/
60 sgo:sdDataset chapters
61 rdf:type schema:Chapter
62 N2f9e2c622de54409bf7b39a47cbfe4e5 schema:familyName Tixeuil
63 schema:givenName Sebastien
64 rdf:type schema:Person
65 N323b3f2197ab4c97956cf5b57bde001f rdf:first Nde4e0c378f464e63ba370498c9d9b1de
66 rdf:rest N86bb9b24a95b474c859008c661585283
67 N683f24a8237744e3b266bdbe8f5da2d7 rdf:first sg:person.010661345305.24
68 rdf:rest Nb61d78420eea4814a963aac0812b6722
69 N86bb9b24a95b474c859008c661585283 rdf:first N2f9e2c622de54409bf7b39a47cbfe4e5
70 rdf:rest rdf:nil
71 Nb61d78420eea4814a963aac0812b6722 rdf:first sg:person.07674464077.03
72 rdf:rest rdf:nil
73 Nb8f126a5ef00437a81a13305c6279456 schema:name doi
74 schema:value 10.1007/978-3-319-72050-0_21
75 rdf:type schema:PropertyValue
76 Nbbc6874163af4e03a105ae6571f9958b schema:isbn 978-3-319-72049-4
77 978-3-319-72050-0
78 schema:name Structural Information and Communication Complexity
79 rdf:type schema:Book
80 Nc31a7384d221492596f77dc3654d6894 schema:name dimensions_id
81 schema:value pub.1100110744
82 rdf:type schema:PropertyValue
83 Nde4e0c378f464e63ba370498c9d9b1de schema:familyName Das
84 schema:givenName Shantanu
85 rdf:type schema:Person
86 Nf6335b432c174be4a4aa4b9153ab8eed schema:name Springer Nature - SN SciGraph project
87 rdf:type schema:Organization
88 Nfef89c10a5ad4214a3c0bbaa023ce250 schema:name Springer Nature
89 rdf:type schema:Organisation
90 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
91 schema:name Information and Computing Sciences
92 rdf:type schema:DefinedTerm
93 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
94 schema:name Computation Theory and Mathematics
95 rdf:type schema:DefinedTerm
96 sg:person.010661345305.24 schema:affiliation grid-institutes:grid.6451.6
97 schema:familyName Spiegelman
98 schema:givenName Alexander
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010661345305.24
100 rdf:type schema:Person
101 sg:person.07674464077.03 schema:affiliation grid-institutes:grid.6451.6
102 schema:familyName Keidar
103 schema:givenName Idit
104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07674464077.03
105 rdf:type schema:Person
106 grid-institutes:grid.6451.6 schema:alternateName Viterbi EE Department, Technion, Haifa, Israel
107 schema:name Viterbi EE Department, Technion, Haifa, Israel
108 rdf:type schema:Organization
 




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


...