Update efficient codes for distributed storage

This paper determines mechanisms for distributed storage that are simultaneously repair and update efficient. Repair efficiency demands that minimum information be downloaded from surviving nodes to reconstruct failed storage nodes. Update efficiency desires that changes in the original data require minimal updates at the storage nodes. These two requirements can be seen as counteracting one another, as the latter imposes a sparsity constraint on the encoding process that is not desirable for the former. In this paper we establish the existence of the codes that meet both requirements: require only logarithmic updates when data changes, while simultaneously minimizing repair bandwidth for exact reconstruction. To show this, we use a combination of KG codes for update efficiency with interference-alignment strategies for distributed storage.