CSR --- PDOS: Combining Replication with Erasure Coding for Efficient Fault-Tolerance

CSR --- PDOS：将复制与纠删码相结合以实现高效容错

• 批准号: 0718990
• 负责人: Vijay Garg
• 金额: $ 24.23万
• 依托单位: University of Texas at Austin
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-09-01 至 2011-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0718990&HistoricalAwards=false
• 关键词: CSR; PDOS; Combining; Replication; Erasure

In this project, we are investigating the theory, algorithms and applications of fusible data structures for fault-tolerance in parallel or distributed programs with low overhead. Fusible data structures are based on combining partial replication with erasure coding to satisfy three main properties: recovery, space constraint and efficient maintenance. The recovery property ensures that in case of a failure, the fused structure, along with the remaining original data structures, can be used to reconstruct the failed structure. The space constraint ensures that the number of nodes in the fused structures is strictly smaller than the number of nodes in the original structures. Finally, the efficient maintenance property ensures that when any of the original data structures is updated, the fused structure can be updated incrementally using local information about the update and does not need to be entirely recomputed.The project is carrying out the following three tasks: (i) develop algorithms for fusible data structures for other commonly used structures such as trees and graphs, (ii) develop theory and associated algorithms for multiple faults (iii) apply fusible data structures for recovery of parallel and distributed applications and evaluate the performance benefits of our approach in real applications.

在这个项目中，我们正在研究可熔数据结构的理论，算法和应用程序的容错并行或分布式程序的低开销。 融合数据结构是基于部分复制和纠删编码相结合，以满足三个主要属性：恢复，空间约束和有效的维护。恢复属性确保在故障的情况下，融合结构连同剩余的原始数据结构沿着可以用于重构故障结构。 空间约束确保融合结构中的节点数量严格小于原始结构中的节点数量。 最后，高效的维护属性确保了当任何原始数据结构被更新时，融合结构可以使用关于更新的本地信息进行增量更新，而不需要完全重新计算。该项目正在执行以下三项任务：（i）为其他常用结构（例如树和图）开发可融合数据结构的算法，（ii）开发多故障的理论和相关算法（iii）应用可熔数据结构恢复并行和分布式应用程序，并评估我们的方法在真实的应用中的性能优势。