Treeplication: An Erasure Code for Distributed Full Recovery in Storage Systems


Event details

Date and time 28.02.2020 14:1515:15  
Place and room
Speaker Prof. Yuval Cassuto, Technion
Category Conferences - Seminars
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 communication cost 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.

Practical information

  • Informed public
  • Free


  • IPG Seminar (O. Lévêque)


  • Muriel Bardet