CIF: Small: Information Recovery Under Connectivity and Communication Constraints

University Of Maryland, College Park, College Park MD

Investigators

Abstract

Modern-day large-scale distributed storage systems store data on thousands of storage nodes, and failure of individual nodes is everyday reality of the system operation. Companies maintaining storage systems make provisions for node failures, relying on erasure codes to ensure data integrity. While specialized encoding methods developed in recent years involve minimum amount of inter-nodal communication possible for such systems, most current solutions rely on the common assumption of universal connectivity between the nodes. At the same time, in many applications starting with Internet-of Things, connections between the nodes are established based on physical proximity or similar features that affect the ability of the nodes to communicate with each other or with the data collector. With this in mind, this project investigates methods of data recovery in systems with limited connectivity whereby the cost of data repair is governed by the length of the path between the nodes, and therefore depends on the topology of the network. This project intends to establish fundamental limits of communication complexity of data recovery that account for connectivity properties of the underlying network as well as to construct coding methods that ensure data integrity against node failures, incorrect information, or adversarial action that approach the bounds on the minimum possible amount of communication. As an indicator of the network properties, the research conducted in this project aims to investigate limits of data recovery in random networks and to quantify thresholds between high-probability recovery and the impossibility of recovery in random networks. This project also examines algebraic constructions of codes that correct errors under communication constraints including codes on algebraic curves, and optimal-repair codes for the cooperative repair model. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.