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.

更广泛的意义：钥匙值商店构成了许多基于Web的应用程序的组成基础设施组成部分，包括零售商店，多玩家游戏，预订系统，新闻提要以及社交和专业网络。云计算服务提供商通常在大规模分布数据存储系统上实现密钥值存储。在分布式存储系统中钥匙值商店实现的核心，有一些精心设计的算法，这些算法将存储数据的一致，当前视图展示给读取数据的用户。 该项目的主要目的是对分布式存储系统产生的存储成本进行正式研究，该研究渴望呈现存储数据的一致，当前的观点。该项目具有长期的潜力，可以帮助开发新的数据存储技术，可以通过降低其存储成本和能源消耗来使密钥值商店实施受益。技术描述：分布式数据存储系统的重要要求是容忍度，即即使系统组件失败，数据也必须访问。在分布式存储在分布式计算和键值商店的实现中的应用程序中，以下称为一致性的属性也至关重要：当数据不断更新时，从系统中读取的用户应获得最新版本的数据。在分布式系统理论和实践中广泛研究了确保存储系统中一致性和容错性的算法。该项目的目的是首次获得对存储成本的信息理论理解，该存储成本是在研究人员的初步工作中建立的，该项目将开发和研究以分布式系统理论和实践为灵感的一些新信息理论公式。拟议的配方自然会在冗余程度和一致性程度以及存储系统的其他物理参数之间揭示权衡取舍。将使用代数，组合学和网络信息理论的工具开发针对拟议公式的新编码方案和信息理论对话。该项目还将追求用于网络编码的新界限，该项目自然适用于新提出的配方以及其他代码家族，包括本地维修的代码和再生代码。该项目同样将制定一项教育计划，该计划的长期目标是开发接受信息理论，编码理论以及分布式系统的理论和设计的跨学科研究人员和工程师。

项目成果

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