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

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

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.