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

本项目的研究目标是通过基于编码的分布式计算来研究在分布式网络中存储演化信息的基本问题。当一个消息的多个版本被写入存储网络时，该项目研究如何使用擦除码和分布式算法来容忍通信和存储节点故障并获得一致的存储，同时在存储和通信大小方面保持低成本。以一致的方式存储不断变化的信息是多处理器编程、传感器网络、分布式数据库和云存储中的关键问题之一。本计画所提出的方案，在理论上与实际的分散式系统中，寻求降低储存与通讯成本的解决方案。该项目利用编码理论和分布式计算，结合信息理论和算法参数，用于理解其他分布式算法。该项目将通过研究和研究生课程的编制来教育学生，并将为非专家听众提供在线材料。在分布式存储编码的标准假设下，静态消息将被写入和读取，操作瞬间完成。因此，没有考虑信息访问过程的时间方面。另一方面，异步和不可靠的消息传递网络中的共享存储器导致许多具有先验未知延迟的读取和写入操作，并且每个写入操作具有潜在不同版本的动态消息。目前缺乏对这种情况的信息理论评估。这个项目解决了在分布式网络中存储不断变化的信息的几个基本问题。首先，提出了具有变化消息的多版本编码。这是一种新的纠错码框架，它允许存储网络中存在多个版本的消息，并且在不同的存储节点上写入不同的版本子集，这样即使节点故障，也可以解码最新的可能版本。其次，研究了具有同步通信的多版本存储，其中可能无限系列的写入和读取操作在同步轮中向存储节点通信，使得每次读取都可以恢复最新的可能消息版本。 第三，研究了异步网络中的多版本存储，使得一次写或一次读可以多次访问节点，并且解码后的消息版本满足给定的一致性条件。该项目将研究这些不同的设置，构建可实现的编码和算法方案，并证明信息理论的存储和通信成本的外部边界。

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.