  In this paper, we study the problem of storing an archive of versioned data
in a reliable and efficient manner in distributed storage systems. We propose a
new storage technique called differential erasure coding (DEC) where the
differences (deltas) between subsequent versions are stored rather than the
whole objects, akin to a typical delta encoding technique. However, unlike
delta encoding techniques, DEC opportunistically exploits the sparsity (i.e.,
when the differences between two successive versions have few non-zero entries)
in the updates to store the deltas using compressed sensing techniques applied
with erasure coding. We first show that DEC provides significant savings in the
storage size for versioned data whenever the update patterns are characterized
by in-place alterations. Subsequently, we propose a practical DEC framework so
as to reap storage size benefits against not just in-place alterations but also
real-world update patterns such as insertions and deletions that alter the
overall data sizes. We conduct experiments with several synthetic workloads to
demonstrate that the practical variant of DEC provides significant reductions
in storage overhead (up to 60\% depending on the workload) compared to baseline
storage system which incorporates concepts from Rsync, a delta encoding
technique to store and synchronize data across a network.
