The graph constructed by using bloom filter-style hash functions supports a decoding process called "peeling" where you:
1. Find a batch with 1 missing element
2. Delete that element from its other assigned partitions
3. Repeat, as the modified batches may now be recoverable
This iterative process (surprisingly!) succeeds with very high probability as long as the number of partitions is 1.22x larger than the number of missing elements with k=3 hash functions.
Comments
The graph constructed by using bloom filter-style hash functions supports a decoding process called "peeling" where you:
1. Find a batch with 1 missing element 2. Delete that element from its other assigned partitions 3. Repeat, as the modified batches may now be recoverable
This iterative process (surprisingly!) succeeds with very high probability as long as the number of partitions is 1.22x larger than the number of missing elements with k=3 hash functions.