| NSF Org: |
CCF Division of Computing and Communication Foundations |
| Recipient: |
|
| Initial Amendment Date: | January 29, 2016 |
| Latest Amendment Date: | February 26, 2020 |
| Award Number: | 1553248 |
| Award Instrument: | Continuing Grant |
| Program Manager: |
Phillip Regalia
pregalia@nsf.gov (703)292-2981 CCF Division of Computing and Communication Foundations CSE Directorate for Computer and Information Science and Engineering |
| Start Date: | February 15, 2016 |
| End Date: | January 31, 2023 (Estimated) |
| Total Intended Award Amount: | $497,847.00 |
| Total Awarded Amount to Date: | $497,847.00 |
| Funds Obligated to Date: |
FY 2018 = $201,554.00 FY 2020 = $104,207.00 |
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
201 OLD MAIN UNIVERSITY PARK PA US 16802-1503 (814)865-1372 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
PA US 16802-7000 |
| Primary Place of
Performance Congressional District: |
|
| Unique Entity Identifier (UEI): |
|
| Parent UEI: |
|
| NSF Program(s): | Comm & Information Foundations |
| Primary Program Source: |
01001819DB NSF RESEARCH & RELATED ACTIVIT 01002021DB NSF RESEARCH & RELATED ACTIVIT |
| Program Reference Code(s): |
|
| Program Element Code(s): |
|
| Award Agency Code: | 4900 |
| Fund Agency Code: | 4900 |
| Assistance Listing Number(s): | 47.070 |
ABSTRACT
Broader Significance:
Key-value stores form an integral infrastructural component of numerous modern web-based applications including retail stores, multi-player games, reservation systems, news feeds, and social and professional networks. Cloud computing service providers commonly implement key-value stores over large scale distributed data storage systems. At the heart of key-value store implementations in distributed storage systems, there are carefully crafted algorithms that expose a consistent, current view of the stored data to a user who reads the data. The main purpose of this project is to undertake a formal study of the storage costs incurred in distributed storage systems which aspire to present a consistent, current view of the stored data. The project has the long-term potential to aid the development of new data storage techniques that can benefit key-value store implementations by reducing their storage cost and energy consumption.
Technical Description:
An important requirement of a distributed data storage system is fault tolerance, that is, the data must be accessible even if the system components fail. In applications of distributed storage to distributed computing and implementation of key-value stores, the following property known as consistency is also critical: when the data is being constantly updated, a user that reads from the system should obtain the latest version of the data. Algorithms that ensure consistency and fault tolerance in storage systems have been extensively studied in distributed systems theory and practice. The goal of this project is to obtain, for the first time, an information theoretic understanding of the storage costs incurred in consistent, fault-tolerant distributed storage systems.
Building on preliminary work by the investigator, the project will develop and study several new information theoretic formulations inspired by distributed systems theory and practice. The proposed formulations naturally expose trade-offs between the degrees of redundancy and consistency, and other physical parameters of storage systems. New coding schemes and information theoretic converses for the proposed formulations will be developed using tools from algebra, combinatorics and network information theory. The project will also pursue the development of new bounds for network coding, which naturally apply to the newly proposed formulations and to other families of codes including locally repairable codes and regenerating codes. The project will likewise develop an education plan that eyes the long term goal of developing interdisciplinary researchers and engineers who are trained in information theory, coding theory, and the theory and design of distributed systems.
PUBLICATIONS PRODUCED AS A RESULT OF THIS RESEARCH
Note:
When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external
site maintained by the publisher. Some full text articles may not yet be available without a
charge during the embargo (administrative interval).
Some links on this page may take you to non-federal websites. Their policies may differ from
this site.
PROJECT OUTCOMES REPORT
Disclaimer
This Project Outcomes Report for the General Public is displayed verbatim as submitted by the Principal Investigator (PI) for this award. Any opinions, findings, and conclusions or recommendations expressed in this Report are those of the PI and do not necessarily reflect the views of the National Science Foundation; NSF has not approved or endorsed its content.
Modern cloud data storage services are designed to ensure that the data is available to users even if some system components (such as servers) fail. This failure tolerance property is commonly ensured by replicating the data on multiple servers. Several applications such as reservation systems, financial transactions, and multiplayer gaming require storage systems to satisfy a property called consistency in addition to failure tolerance. In simple terms, consistency means that the latest update of the data must be available to users accessing the data. Consistent data storage services employ several carefully designed distributed algorithms that simultaneously ensure both failure tolerance and consistency.
Notably, data replication comes with a redundancy overhead to ensure failure tolerance. In the absence of consistency requirements, a technique called erasure coding from the area of information theory is well-known to incur significantly lower redundancy overhead as compared to data replication without lowering the degree of failure tolerance. This project studied the use of erasure coding for storage systems with consistency requirements. Specifically, the project developed information-theoretic trade-offs between failure tolerance and redundancy overhead for systems that can use erasure coding. It identified new factors that emerge in this trade-off due to the requirement of maintaining consistency. New erasure codes that are nearly optimal with respect to failure tolerance redundancy trade-offs were developed. The developed erasure coding techniques were incorporated into new distributed algorithms for consistent data storage. The cost benefits of these algorithms were analyzed and demonstrated through a prototype data storage system.
The project trained master's and Ph.D. level students in the areas of information theory, error-correcting codes, and distributed algorithms.
Last Modified: 05/01/2023
Modified by: Viveck R Cadambe
Please report errors in award information by writing to: awardsearch@nsf.gov.
