CRII: CIF: Multi-version Distributed Storage - from Instantaneous to Evolving Information

CRII：CIF：多版本分布式存储——从瞬时信息到演化信息

• 批准号: 1566587
• 负责人: Zhiying Wang
• 金额: $ 17.5万
• 依托单位: University of California-Irvine
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-05-15 至 2019-04-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1566587&HistoricalAwards=false
• 关键词: CRII; CIF; Multi; version; Distributed

The research objective of this project is to study the fundamental problem of storing evolving information in distributed networks through coding-based distributed computing. When multiple versions of a message are to be written to a storage network, the project studies how to use erasure codes and distributed algorithms to tolerate communication and storage node failures and obtain consistent storage, while maintaining a low cost in terms of storage and communication sizes. Storing evolving information in a consistent way is one of the critical problems in multi-processor programming, sensor networks, distributed databases, and cloud storage. Schemes produced in this project seek solutions to reduce storage and communication cost, both in theory and in practical distributed systems. The project leverages coding theory and distributed computing, combined with information-theoretic and algorithmic arguments, of use in understanding other distributed algorithms as well. The project will educate students through research and graduate course development, and will provide online materials for a non-expert audience.Under standard assumptions of coding for distributed storage, a static message is to be written and read, with the operations completed instantaneously. As a result, temporal aspects of the information access processes are not considered. On the other hand, shared memory in an asynchronous and unreliable message-passing network results in many read and write operations with delays that are not known a priori, and each write operation has a potentially different version of the dynamic message. An information-theoretic assessment of this setting is presently lacking. This project addresses several basic problems in storing evolving information in distributed networks. First, multi-version coding with a changing message is proposed. This is a new framework of error-correcting codes, which allows multiple versions of a message to be present in the storage network, and different subsets of versions to be written at different storage nodes, such that the newest possible version can be decoded despite node failures. Second, multi-version storage with synchronous communication is studied, where a possibly infinite series of write and read operations communicates to the storage nodes in synchronous rounds, such that every read can recover the newest possible message version. Third, multi-version storage in asynchronous networks is studied, such that a write or a read can access the nodes many times and the decoded message version satisfy a given consistency condition. The project will study these different settings, construct achievable coding and algorithmic schemes, and prove information-theoretic outer bounds for the storage and communication cost.

该项目的研究目标是研究通过基于编码的分布式计算将不断发展的信息存储在分布式网络中的基本问题。当要将多个消息写入存储网络时，该项目研究如何使用擦除代码和分布式算法来容忍通信和存储节点故障并获得一致的存储，同时在存储和通信大小方面保持低成本。以一致的方式存储不断发展的信息是多处理器编程，传感器网络，分布式数据库和云存储的关键问题之一。该项目中生产的计划寻求解决方案，以降低理论和实用分布式系统中的存储和通信成本。该项目利用编码理论和分布式计算，以及信息理论和算法论证，用于理解其他分布式算法。该项目将通过研究和研究生课程的开发对学生进行教育，并将为非专家受众提供在线材料。在编码分布式存储的标准假设下，要编写和阅读的静态信息，操作即时完成。结果，不考虑信息访问过程的时间方面。另一方面，在异步和不可靠的消息网络中共享内存会导致许多读取和写入操作，而延迟的延迟却不为先验，并且每个写操作都具有动态消息的潜在不同版本。目前缺乏对此环境的信息理论评估。该项目解决了将不断发展的信息存储在分布式网络中的几个基本问​​题。首先，提出了带有不断变化的消息的多元版本编码。这是一个新的校正校正代码的新框架，它允许在存储网络中存在多个版本的消息，并且要在不同的存储节点上写入的不同版本的子集，因此，尽管节点失败，但可以解码最新可能的版本。其次，研究了带有同步通信的多元转换存储，其中一系列无限的写入和读取操作在同步回合中通信与存储节点通信，因此每个读取都可以恢复最新的可能的消息版本。 第三，研究了异步网络中的多反转存储，因此写入或读取可以多次访问节点，而解码的消息版本满足给定的一致性条件。该项目将研究这些不同的设置，构建可实现的编码和算法方案，并证明了存储和通信成本的信息理论外部边界。