Lecturer:

Michael Gandelman

Affiliation:

Viterbi Faculty of Electrical Engineering, Technion

Treeplication: An Erasure Code for Decentralized Storage Systems

In this talk we present a new (rateless) erasure code called Treeplication, which features the benefits of both coding and replication. From the system's perspective, Treeplication allows recovering large distributed data items with better probability than replication, and with lower complexity than known erasure codes. From the coding perspective, a Treeplication code for k data fragments is defined on a binary tree with 2k-1 vertices, along with a distribution for selecting code fragments from the tree layers. The tree structure allows to optimize the recoverability of random subsets of code fragments, while at the same time behaving similarly to replication in recovering individual data fragments (in particular, most code symbols in the optimal distributions turn out to be systematic information symbols). In addition to optimizing Treeplication for recoverability, our results include analysis of their recovery communication cost, dynamic optimization of their redundancy, and an algorithm for decentralized maintenance of a Treeplication-coded system.

 

*M.Sc student advised by Prof. Yuval Cassuto.

Date: Wed 13 Nov 2019

Start Time: 11:30

End Time: 12:30

861 | Electrical Eng. Building