CAREER: An Information Theoretic Perspective of Consistent Distributed Storage Systems

更广泛的意义：键值存储构成了许多现代基于Web的应用程序的不可或缺的基础设施组件，包括零售商店、多人游戏、预订系统、新闻源以及社交和专业网络。云计算服务提供商通常在大规模分布式数据存储系统上实现键值存储。在分布式存储系统中的键值存储实现的核心，有精心设计的算法，这些算法向读取数据的用户公开存储数据的一致的当前视图。 这个项目的主要目的是进行正式的研究，在分布式存储系统中产生的存储成本，渴望提出一个一致的，当前的存储数据的视图。该项目具有帮助开发新的数据存储技术的长期潜力，这些技术可以通过降低存储成本和能耗来使键值存储实现受益。技术描述：分布式数据存储系统的一个重要要求是容错，即即使系统组件发生故障，数据也必须是可访问的。在分布式存储到分布式计算的应用和键值存储的实现中，以下被称为一致性的属性也是至关重要的：当数据不断更新时，从系统读取的用户应该获得数据的最新版本。在分布式系统的理论和实践中，存储系统中保证一致性和容错性的算法得到了广泛的研究。该项目的目标是首次从信息论的角度理解一致的、容错的分布式存储系统的存储成本。在研究者前期工作的基础上，该项目将开发和研究受分布式系统理论和实践启发的几种新的信息论公式。所提出的配方自然暴露的冗余度和一致性，以及存储系统的其他物理参数之间的权衡。新的编码方案和信息理论转换的建议配方将开发使用的工具，代数，组合学和网络信息理论。该项目还将寻求开发网络编码的新界限，这自然适用于新提出的公式和其他代码族，包括本地可修复代码和再生代码。该项目还将制定一项教育计划，着眼于培养跨学科研究人员和工程师的长期目标，这些研究人员和工程师在信息理论，编码理论以及分布式系统的理论和设计方面受到培训。

Broader Significance:Key-value stores form an integral infrastructural component of numerous modern web-based applications including retail stores, multi-player games, reservation systems, news feeds, and social and professional networks. Cloud computing service providers commonly implement key-value stores over large scale distributed data storage systems. At the heart of key-value store implementations in distributed storage systems, there are carefully crafted algorithms that expose a consistent, current view of the stored data to a user who reads the data. The main purpose of this project is to undertake a formal study of the storage costs incurred in distributed storage systems which aspire to present a consistent, current view of the stored data. The project has the long-term potential to aid the development of new data storage techniques that can benefit key-value store implementations by reducing their storage cost and energy consumption.Technical Description:An important requirement of a distributed data storage system is fault tolerance, that is, the data must be accessible even if the system components fail. In applications of distributed storage to distributed computing and implementation of key-value stores, the following property known as consistency is also critical: when the data is being constantly updated, a user that reads from the system should obtain the latest version of the data. Algorithms that ensure consistency and fault tolerance in storage systems have been extensively studied in distributed systems theory and practice. The goal of this project is to obtain, for the first time, an information theoretic understanding of the storage costs incurred in consistent, fault-tolerant distributed storage systems.Building on preliminary work by the investigator, the project will develop and study several new information theoretic formulations inspired by distributed systems theory and practice. The proposed formulations naturally expose trade-offs between the degrees of redundancy and consistency, and other physical parameters of storage systems. New coding schemes and information theoretic converses for the proposed formulations will be developed using tools from algebra, combinatorics and network information theory. The project will also pursue the development of new bounds for network coding, which naturally apply to the newly proposed formulations and to other families of codes including locally repairable codes and regenerating codes. The project will likewise develop an education plan that eyes the long term goal of developing interdisciplinary researchers and engineers who are trained in information theory, coding theory, and the theory and design of distributed systems.