CAREER: An Information Theoretic Perspective of Consistent Distributed Storage Systems

职业：一致分布式存储系统的信息论视角

• 批准号: 1553248
• 负责人: Viveck Cadambe
• 金额: $ 49.78万
• 依托单位: Pennsylvania State Univ University Park
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-02-15 至 2023-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1553248&HistoricalAwards=false
• 关键词: CAREER; Information; Theoretic; Perspective; Consistent

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.

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

项目成果

Brief Announcement: CausalEC: A Causally Consistent Data Storage Algorithm based on Cross-Object Erasure Coding

简短公告：CausalEC：基于跨对象纠删码的因果一致数据存储算法

• DOI: 10.1145/3583668.3594603
• 发表时间: 2023
• 期刊: PODC '23: Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing
• 作者: Cadambe, Viveck R.;Lyu, Shihang
• 通讯作者: Lyu, Shihang