How Efficient Can Memory Checking Be? View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2009

AUTHORS

Cynthia Dwork , Moni Naor , Guy N. Rothblum , Vinod Vaikuntanathan

ABSTRACT

We consider the problem of memory checking, where a user wants to maintain a large database on a remote server but has only limited local storage. The user wants to use the small (but trusted and secret) local storage to detect faults in the large (but public and untrusted) remote storage. A memory checker receives from the user store and retrieve operations to the large database. The checker makes its own requests to the (untrusted) remote storage and receives answers to these requests. It then uses these responses, together with its small private and reliable local memory, to ascertain that all requests were answered correctly, or to report faults in the remote storage (the public memory).A fruitful line of research investigates the complexity of memory checking in terms of the number of queries the checker issues per user request (query complexity) and the size of the reliable local memory (space complexity). Blum et al., who first formalized the question, distinguished between online checkers (that report faults as soon as they occur) and offline checkers (that report faults only at the end of a long sequence of operations). In this work we revisit the question of memory checking, asking how efficient can memory checking be?For online checkers, Blum et al. provided a checker with logarithmic query complexity in n, the database size. Our main result is a lower bound: we show that for checkers that access the remote storage in a deterministic and non-adaptive manner (as do all known memory checkers), their query complexity must be at least Ω(logn /loglogn). To cope with this negative result, we show how to trade off the read and write complexity of online memory checkers: for any desired logarithm base d, we construct an online checker where either reading or writing is inexpensive and has query complexity O(logdn). The price for this is that the other operation (write or read respectively) has query complexity O(d ·logdn). Finally, if even this performance is unacceptable, offline memory checking may be an inexpensive alternative. We provide a scheme with O(1) amortized query complexity, improving Blum et al.’s construction, which only had such performance for long sequences of at least n operations. More... »

PAGES

503-520

Book

TITLE

Theory of Cryptography

ISBN

978-3-642-00456-8
978-3-642-00457-5

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-00457-5_30

DOI

http://dx.doi.org/10.1007/978-3-642-00457-5_30

DIMENSIONS

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


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/0806", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information Systems", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Microsoft Research, USA", 
          "id": "http://www.grid.ac/institutes/grid.419815.0", 
          "name": [
            "Microsoft Research, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Dwork", 
        "givenName": "Cynthia", 
        "id": "sg:person.016065712157.59", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016065712157.59"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "The Weizmann Institute of Science, Israel", 
          "id": "http://www.grid.ac/institutes/grid.13992.30", 
          "name": [
            "The Weizmann Institute of Science, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Naor", 
        "givenName": "Moni", 
        "id": "sg:person.07776170271.83", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07776170271.83"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "MIT, USA", 
          "id": "http://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "MIT, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Rothblum", 
        "givenName": "Guy N.", 
        "id": "sg:person.014351474277.34", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014351474277.34"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "IBM Research, USA", 
          "id": "http://www.grid.ac/institutes/grid.481554.9", 
          "name": [
            "IBM Research, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Vaikuntanathan", 
        "givenName": "Vinod", 
        "id": "sg:person.010511407257.61", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010511407257.61"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2009", 
    "datePublishedReg": "2009-01-01", 
    "description": "We consider the problem of memory checking, where a user wants to maintain a large database on a remote server but has only limited local storage. The user wants to use the small (but trusted and secret) local storage to detect faults in the large (but public and untrusted) remote storage. A memory checker receives from the user store and retrieve operations to the large database. The checker makes its own requests to the (untrusted) remote storage and receives answers to these requests. It then uses these responses, together with its small private and reliable local memory, to ascertain that all requests were answered correctly, or to report faults in the remote storage (the public memory).A fruitful line of research investigates the complexity of memory checking in terms of the number of queries the checker issues per user request (query complexity) and the size of the reliable local memory (space complexity). Blum et al., who first formalized the question, distinguished between online checkers (that report faults as soon as they occur) and offline checkers (that report faults only at the end of a long sequence of operations). In this work we revisit the question of memory checking, asking how efficient can memory checking be?For online checkers, Blum et al. provided a checker with logarithmic query complexity in n, the database size. Our main result is a lower bound: we show that for checkers that access the remote storage in a deterministic and non-adaptive manner (as do all known memory checkers), their query complexity must be at least \u03a9(logn /loglogn). To cope with this negative result, we show how to trade off the read and write complexity of online memory checkers: for any desired logarithm base d, we construct an online checker where either reading or writing is inexpensive and has query complexity O(logdn). The price for this is that the other operation (write or read respectively) has query complexity O(d \u00b7logdn). Finally, if even this performance is unacceptable, offline memory checking may be an inexpensive alternative. We provide a scheme with O(1) amortized query complexity, improving Blum et al.\u2019s construction, which only had such performance for long sequences of at least n operations.", 
    "editor": [
      {
        "familyName": "Reingold", 
        "givenName": "Omer", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-00457-5_30", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-00456-8", 
        "978-3-642-00457-5"
      ], 
      "name": "Theory of Cryptography", 
      "type": "Book"
    }, 
    "keywords": [
      "memory checking", 
      "remote storage", 
      "query complexity", 
      "online checkers", 
      "memory checkers", 
      "local storage", 
      "local memory", 
      "large database", 
      "small local storage", 
      "number of queries", 
      "user stores", 
      "remote server", 
      "user requests", 
      "database size", 
      "non-adaptive manner", 
      "checker", 
      "Blum et al", 
      "checking", 
      "complexity of memory", 
      "requests", 
      "complexity", 
      "users", 
      "base d", 
      "long sequences", 
      "queries", 
      "server", 
      "database", 
      "Blum", 
      "operation", 
      "memory", 
      "faults", 
      "performance", 
      "such performance", 
      "storage", 
      "Efficient", 
      "scheme", 
      "issues", 
      "stores", 
      "inexpensive alternative", 
      "work", 
      "answers", 
      "reads", 
      "own request", 
      "construction", 
      "results", 
      "et al", 
      "research", 
      "terms", 
      "number", 
      "manner", 
      "sequence", 
      "size", 
      "main results", 
      "alternative", 
      "questions", 
      "reading", 
      "prices", 
      "al", 
      "lines", 
      "fruitful lines", 
      "writing", 
      "negative results", 
      "response", 
      "problem", 
      "large (but public and untrusted) remote storage", 
      "reliable local memory", 
      "checker issues", 
      "offline checkers", 
      "logarithmic query complexity", 
      "online memory checkers", 
      "logarithm base d", 
      "offline memory checking"
    ], 
    "name": "How Efficient Can Memory Checking Be?", 
    "pagination": "503-520", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1026351297"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-00457-5_30"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-00457-5_30", 
      "https://app.dimensions.ai/details/publication/pub.1026351297"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:12", 
    "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_208.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-00457-5_30"
  }
]
 

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-642-00457-5_30'

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-642-00457-5_30'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-00457-5_30'

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-642-00457-5_30'


 

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

162 TRIPLES      23 PREDICATES      98 URIs      91 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-00457-5_30 schema:about anzsrc-for:08
2 anzsrc-for:0806
3 schema:author N255e830a32a04b808cc78af8aa91dafe
4 schema:datePublished 2009
5 schema:datePublishedReg 2009-01-01
6 schema:description We consider the problem of memory checking, where a user wants to maintain a large database on a remote server but has only limited local storage. The user wants to use the small (but trusted and secret) local storage to detect faults in the large (but public and untrusted) remote storage. A memory checker receives from the user store and retrieve operations to the large database. The checker makes its own requests to the (untrusted) remote storage and receives answers to these requests. It then uses these responses, together with its small private and reliable local memory, to ascertain that all requests were answered correctly, or to report faults in the remote storage (the public memory).A fruitful line of research investigates the complexity of memory checking in terms of the number of queries the checker issues per user request (query complexity) and the size of the reliable local memory (space complexity). Blum et al., who first formalized the question, distinguished between online checkers (that report faults as soon as they occur) and offline checkers (that report faults only at the end of a long sequence of operations). In this work we revisit the question of memory checking, asking how efficient can memory checking be?For online checkers, Blum et al. provided a checker with logarithmic query complexity in n, the database size. Our main result is a lower bound: we show that for checkers that access the remote storage in a deterministic and non-adaptive manner (as do all known memory checkers), their query complexity must be at least Ω(logn /loglogn). To cope with this negative result, we show how to trade off the read and write complexity of online memory checkers: for any desired logarithm base d, we construct an online checker where either reading or writing is inexpensive and has query complexity O(logdn). The price for this is that the other operation (write or read respectively) has query complexity O(d ·logdn). Finally, if even this performance is unacceptable, offline memory checking may be an inexpensive alternative. We provide a scheme with O(1) amortized query complexity, improving Blum et al.’s construction, which only had such performance for long sequences of at least n operations.
7 schema:editor Nbc413c42f24043079317c11e7c414120
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Nb66ac5307dfe480ea66cbeda5868e43c
12 schema:keywords Blum
13 Blum et al
14 Efficient
15 al
16 alternative
17 answers
18 base d
19 checker
20 checker issues
21 checking
22 complexity
23 complexity of memory
24 construction
25 database
26 database size
27 et al
28 faults
29 fruitful lines
30 inexpensive alternative
31 issues
32 large (but public and untrusted) remote storage
33 large database
34 lines
35 local memory
36 local storage
37 logarithm base d
38 logarithmic query complexity
39 long sequences
40 main results
41 manner
42 memory
43 memory checkers
44 memory checking
45 negative results
46 non-adaptive manner
47 number
48 number of queries
49 offline checkers
50 offline memory checking
51 online checkers
52 online memory checkers
53 operation
54 own request
55 performance
56 prices
57 problem
58 queries
59 query complexity
60 questions
61 reading
62 reads
63 reliable local memory
64 remote server
65 remote storage
66 requests
67 research
68 response
69 results
70 scheme
71 sequence
72 server
73 size
74 small local storage
75 storage
76 stores
77 such performance
78 terms
79 user requests
80 user stores
81 users
82 work
83 writing
84 schema:name How Efficient Can Memory Checking Be?
85 schema:pagination 503-520
86 schema:productId Nb69bf3d4b51c4ab0b8c44b210b9dd6d9
87 Ne0b59e3ad6f4441c89caa0d8ca20a72b
88 schema:publisher Nb71ba73095e44800a95c994310071e5a
89 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026351297
90 https://doi.org/10.1007/978-3-642-00457-5_30
91 schema:sdDatePublished 2022-01-01T19:12
92 schema:sdLicense https://scigraph.springernature.com/explorer/license/
93 schema:sdPublisher N9a09362b7dfc452c89272ce07ccfa050
94 schema:url https://doi.org/10.1007/978-3-642-00457-5_30
95 sgo:license sg:explorer/license/
96 sgo:sdDataset chapters
97 rdf:type schema:Chapter
98 N1175df53e72f4923b1ed47769014ae16 rdf:first sg:person.014351474277.34
99 rdf:rest N6401f6f8c9ae46e0970bfb054f8fd6f9
100 N255e830a32a04b808cc78af8aa91dafe rdf:first sg:person.016065712157.59
101 rdf:rest Nf30a263c916e4806a13da985cabca0c4
102 N6401f6f8c9ae46e0970bfb054f8fd6f9 rdf:first sg:person.010511407257.61
103 rdf:rest rdf:nil
104 N97150ccd2d514ccdbf9bce526c24a6a3 schema:familyName Reingold
105 schema:givenName Omer
106 rdf:type schema:Person
107 N9a09362b7dfc452c89272ce07ccfa050 schema:name Springer Nature - SN SciGraph project
108 rdf:type schema:Organization
109 Nb66ac5307dfe480ea66cbeda5868e43c schema:isbn 978-3-642-00456-8
110 978-3-642-00457-5
111 schema:name Theory of Cryptography
112 rdf:type schema:Book
113 Nb69bf3d4b51c4ab0b8c44b210b9dd6d9 schema:name dimensions_id
114 schema:value pub.1026351297
115 rdf:type schema:PropertyValue
116 Nb71ba73095e44800a95c994310071e5a schema:name Springer Nature
117 rdf:type schema:Organisation
118 Nbc413c42f24043079317c11e7c414120 rdf:first N97150ccd2d514ccdbf9bce526c24a6a3
119 rdf:rest rdf:nil
120 Ne0b59e3ad6f4441c89caa0d8ca20a72b schema:name doi
121 schema:value 10.1007/978-3-642-00457-5_30
122 rdf:type schema:PropertyValue
123 Nf30a263c916e4806a13da985cabca0c4 rdf:first sg:person.07776170271.83
124 rdf:rest N1175df53e72f4923b1ed47769014ae16
125 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
126 schema:name Information and Computing Sciences
127 rdf:type schema:DefinedTerm
128 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
129 schema:name Information Systems
130 rdf:type schema:DefinedTerm
131 sg:person.010511407257.61 schema:affiliation grid-institutes:grid.481554.9
132 schema:familyName Vaikuntanathan
133 schema:givenName Vinod
134 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010511407257.61
135 rdf:type schema:Person
136 sg:person.014351474277.34 schema:affiliation grid-institutes:grid.116068.8
137 schema:familyName Rothblum
138 schema:givenName Guy N.
139 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014351474277.34
140 rdf:type schema:Person
141 sg:person.016065712157.59 schema:affiliation grid-institutes:grid.419815.0
142 schema:familyName Dwork
143 schema:givenName Cynthia
144 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016065712157.59
145 rdf:type schema:Person
146 sg:person.07776170271.83 schema:affiliation grid-institutes:grid.13992.30
147 schema:familyName Naor
148 schema:givenName Moni
149 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07776170271.83
150 rdf:type schema:Person
151 grid-institutes:grid.116068.8 schema:alternateName MIT, USA
152 schema:name MIT, USA
153 rdf:type schema:Organization
154 grid-institutes:grid.13992.30 schema:alternateName The Weizmann Institute of Science, Israel
155 schema:name The Weizmann Institute of Science, Israel
156 rdf:type schema:Organization
157 grid-institutes:grid.419815.0 schema:alternateName Microsoft Research, USA
158 schema:name Microsoft Research, USA
159 rdf:type schema:Organization
160 grid-institutes:grid.481554.9 schema:alternateName IBM Research, USA
161 schema:name IBM Research, USA
162 rdf:type schema:Organization
 




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


...