This paper presents a new erasure code called Treeplication designed for distributed recovery of the full information word, while most prior work in coding for distributed storage only supports distributed repair of individual symbols. A Treeplication code for k information symbols is defined on a binary tree with 2k-1 vertices, along with a distribution for selecting code symbols from the tree layers. We analyze and optimize the code under a random-multiset model, which captures the system property that the nodes available for recovery are drawn randomly from the nodes storing the code symbols. Treeplication codes are shown to have full-recovery communication-cost comparable to replication, while offering much better recoverability.

This paper presents a new erasure code called Treeplication which features the benefits of both coding and replication. 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. The significant performance advantages over both replication and existing erasure codes motivate the use of Treeplication in decentralized distributed storage systems.