Data Stream Verification
Data Stream Verification
复制标题
数据流验证
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
J. Thaler
中科院分区：
文献类型：
--
作者：
J. Thaler
问题与以下设置有关。计算受限的客户端想要计算大量输入的某个属性，但缺乏存储甚至一小部分输入的资源，因此无法在本地执行所需的计算。客户端因此访问强大但不可信的服务提供者（例如，商业云计算服务），其不仅执行所请求的计算，而且还证明答案是正确的。一系列密切相关的模型已被引入来捕捉这种情况。下一节提供了这些模型的统一介绍，在描述它们的差异之前强调它们的共同特征。
The problem is concerned with the following setting. A computationally limited client wants to compute some property of a massive input, but lacks the resources to store even a small fraction of the input, and hence cannot perform the desired computation locally. The client therefore accesses a powerful but untrusted service provider (e.g., a commercial cloud computing service), who not only performs the requested computation but also proves that the answer is correct. An array of closely related models have been introduced to capture this scenario. The following section provides a unified presentation of these models, emphasizing their common features before delineating their differences.