How to retrieve a file from a distributed storage with a single hash in spite of high churn rate

What is it about?

We proposed a data structure for retrieving distributed content that we called "entangled Merkle trees" because they merge the ideas of alpha entanglement codes and Merkle trees. Merkle trees are made of nodes that contain one (root) or more hashes, the hashes act like a pointer to retrieve other chunks. Thus, the root and all the intermediate nodes in the tree (metadata chunks) are used recursively to locate the file pieces stored in geographically distributed peers. The leaves of the tree are the file pieces (data chunks). The network does not distinguishes between data and metadata chunks. Alpha entanglement codes is an efficient technique to provide resilience in spite of high churn rate.

Featured Image

Photo by Alina Grubnyak on Unsplash

Photo by Alina Grubnyak on Unsplash

Why is it important?

Merkle trees do not have resilience to high churn rate. To cope with high churn rate or other failures that impact in the file availability, systems have used the trivial idea of replicating content which results in high storage overhead. To make things worse, because Merkle trees clearly organized content in a hierarchically way, if the root or intermediate nodes become unavailable, all the content that is usually retrievable through those nodes becomes unreachable. With entangled Merkle trees, all the chunks (content independently if are data or metadata chunk) are entangled together. In this way, it is possible to recover missing chunks through other chunks in the network, using a small amount of storage overhead and bandwidth overhead to repair missing chunks. In addition, a file is retrievable with only one hash, enabling very convenient access to small or large files distributed in the network without the need of additional metadata stored somewhere else (the user does not need to keep any additional metadata to locate chunks or any redundant chunk used in repairs).

Perspectives