CIF: Small: Collaborative Research:Synchronization and Deduplication of Distributed Coded Data: Fundamental Limits and Algorithms

CIF：小型：协作研究：分布式编码数据的同步和重复数据删除：基本限制和算法

• 批准号: 1527130
• 负责人: Lara Dolecek
• 金额: $ 15万
• 依托单位: University of California-Los Angeles
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-07-01 至 2019-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1527130&HistoricalAwards=false
• 关键词: CIF; Small; Collaborative; Research; Synchronization

Part 1: Coding for distributed storage systems has garnered significant attention in the past few years due to the rapid development of information technologies and the emergence of Big Data formats that need to be stored and disseminated across large-scale networks. As typical distributed systems need to ensure low-latency data access and store a large number of files over a set of nodes connected through a communication network, it is imperative to develop new distributed coding schemes that protect the systems from undesired component failures. The two key functionalities of codes used in distributed systems, namely the reconstruction of files via access to a subset of the nodes and repair of failed nodes, need to be retained when the files are accessed and processed by the users via symbol/block insertion, deletion, or substitution edits. Deletions frequently arise due to system-level data deduplication: when parts of files are deduplicated or edited, the changes in the information content need to be communicated to the redundant storage nodes with minimum communication cost. Current solutions for synchronizing data that underwent edits assume that data is uncoded and they do not fully exploit the distributed nature of information. Furthermore, they mostly ignore the presence of deduplication protocols. This makes distributed storage architectures inefficient in terms of storage, user access times, and error protection. Hence, the goals of the proposed research program are to develop a new set of protocols and coding schemes that will support a new generation of versatile and updatable coded distributed storage systems. Part 2: Building on the preliminary work of the investigators, this proposal aims to set the foundations of the new field of coded synchronization and deduplication, with the goal of deriving fundamental performance limits, developing efficient algorithmic solutions for the two families of problems, and constructing new distributed storage codes that enable synchronization of coded data and coded deduplication. In particular, the proposal addresses the following comprehensive issues: 1) Characterizing the communication rate limits of known and new (un)coded synchronization schemes, trade-offs between deduplication and data repair performance for different structured or encoded data formats and different types of communication channels.2) Introducing and analyzing the communication rate-distortion (CRD) function for approximate synchronization and deduplication of structured/encoded data, with a special focus on delay-sensitive applications.3) Developing dynamically updatable synchronization and deduplication algorithms cognizant of the network topology and of different prioritization needs of the users, as encountered in image and video data coding.

第 1 部分：由于信息技术的快速发展以及需要在大规模网络上存储和传播的大数据格式的出现，分布式存储系统的编码在过去几年中引起了极大的关注。由于典型的分布式系统需要确保低延迟数据访问并通过通信网络连接的一组节点存储大量文件，因此必须开发新的分布式编码方案来保护系统免受意外组件故障的影响。当用户通过符号/块插入访问和处理文件时，需要保留分布式系统中使用的代码的两个关键功能，即通过访问节点子集来重建文件和修复故障节点，删除或替换编辑。由于系统级重复数据删除而频繁出现删除：当部分文件被重复删除或编辑时，信息内容的变化需要以最小的通信成本传达到冗余存储节点。当前用于同步经过编辑的数据的解决方案假设数据是未编码的，并且它们没有充分利用信息的分布式性质。此外，他们大多忽略重复数据删除协议的存在。这使得分布式存储架构在存储、用户访问时间和错误保护方面效率低下。因此，拟议研究计划的目标是开发一套新的协议和编码方案，以支持新一代通用且可更新的编码分布式存储系统。第 2 部分：在研究人员的前期工作的基础上，该提案旨在为编码同步和重复数据删除这一新领域奠定基础，其目标是导出基本性能限制，为这两类问题开发有效的算法解决方案，以及构建新的分布式存储代码，实现编码数据同步和编码重复数据删除。特别是，该提案解决了以下综合问题：1）表征已知和新的（未）编码同步方案的通信速率限制，不同结构化或编码数据格式和不同类型通信的重复数据删除和数据修复性能之间的权衡2) 介绍和分析用于结构化/编码数据的近似同步和重复数据删除的通信速率失真（CRD）函数，特别关注延迟敏感的应用。3) 开发动态可更新的同步和重复数据删除算法认识到图像和视频数据编码中遇到的网络拓扑和用户的不同优先级需求。

项目成果

Data deduplication with edit errors

具有编辑错误的重复数据删除

• 发表时间: 2018-12
• 期刊: IEEE Global Communications Conference
• 作者: Conde;Condie, Tyson;Dolecek, Lara
• 通讯作者: Dolecek, Lara

An Interactive Algorithm for Synchronizing from Burst Deletions

一种用于突发删除同步的交互式算法

• 发表时间: 2018-12
• 期刊: IEEE International Symposium on Turbo Coding and Iterative Information Processing
• 作者: Jiang, Shuyang;Schoeny, Clayton;Dolecek, Lara
• 通讯作者: Dolecek, Lara

Theoretical Bounds and Constructions of Codes in the Generalized Cayley Metric

广义凯莱度量中的理论界限和代码构造

• DOI: 10.1109/tit.2019.2899868
• 发表时间: 2018-03-12
• 期刊: IEEE Transactions on Information Theory
• 影响因子: 2.5
• 作者: Siyi Yang;Clayton Schoeny;L. Dolecek
• 通讯作者: L. Dolecek