| NSF Org: |
CCF Division of Computing and Communication Foundations |
| Recipient: |
|
| Initial Amendment Date: | July 28, 2014 |
| Latest Amendment Date: | July 28, 2014 |
| Award Number: | 1422715 |
| Award Instrument: | Standard Grant |
| Program Manager: |
Rahul Shah
CCF Division of Computing and Communication Foundations CSE Directorate for Computer and Information Science and Engineering |
| Start Date: | September 1, 2014 |
| End Date: | August 31, 2017 (Estimated) |
| Total Intended Award Amount: | $382,000.00 |
| Total Awarded Amount to Date: | $382,000.00 |
| Funds Obligated to Date: |
|
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
360 HUNTINGTON AVE BOSTON MA US 02115-5005 (617)373-5600 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
360 Huntington Ave Boston MA US 02115-5005 |
| Primary Place of
Performance Congressional District: |
|
| Unique Entity Identifier (UEI): |
|
| Parent UEI: |
|
| NSF Program(s): | Algorithmic Foundations |
| Primary Program Source: |
|
| Program Reference Code(s): |
|
| Program Element Code(s): |
|
| Award Agency Code: | 4900 |
| Fund Agency Code: | 4900 |
| Assistance Listing Number(s): | 47.070 |
ABSTRACT
Modern information networks are composed of heterogeneous nodes and links, whose capacities and capabilities change unexpectedly due to mobility, failures, maintenance, and adversarial attacks. User demands and critical infrastructure needs, however, require that basic primitives including access to information and services be always efficient and reliable. This project studies the design of highly robust networked systems that are resilient to extreme failures and rapid dynamics, and provide optimal performance under a wide spectrum of scenarios with varying levels of predictability.
The focus of this project will be on two problem domains, which together address adversarial network dynamics and stochastic network failures. The first component is a comprehensive theory of information spreading in dynamic networks. The PI will develop an algorithmic toolkit for dynamic networks, including local gossip-style protocols, network coding, random walks, and other diffusion processes. The second component of the project concerns failure-aware network algorithms that provide high availability in the presence of unexpected and correlated failures. The PI will study failure-aware placement of critical resources, and develop flow and cut algorithms under stochastic failures using techniques from chance-constrained optimization. Algorithms tolerant to adversarial and stochastic uncertainty will play a critical role in large-scale heterogeneous information networks of the future. Broader impacts include student training and curriculum development.
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.
The goal of this project was to develop solutions for computer
networks in scenarios where there is significant uncertainty in the
operating environment. This uncertainty may manifest as lack of
information about the inputs (e.g., network traffic, computational
tasks), adversarial threats (e.g., denial-of-service attacks), or
accidental failures (e.g., dynamic changes in networks, communication
errors). Developing algorithms that work in such uncertain scenarios
is challenging. In this project, we have addressed these challenges
in three different ways.
First, we have developed new algorithms for allocating resources in
datacenter networks which ensure that critical data processing tasks
get completed even under threats to the underlying infrastructure.
These results offer new techniques for allocating datacenter resources
in the presence of complex failure patterns. Second, we have shown
that if the communication links within a distributed system are
controlled by an adversary even partially, it is necessary to develop
randomized, as opposed to deterministic, methods for exchanging
information to ensure timely sharing of data. These results also
highlight the power of simple local gossip-style protocols that enable
fast sharing of information. Finally, we have studied various
communication paradigms (e.g., streaming from a single location to
multiple network locations) and have shown how to build network
structures that support these paradigms on a given communication
infrastructure in a cost-effective manner. The mathematical problems
underlying the design of such network structures are known to be
computationally intractable, and we have shown how to overcome such
challenges using new techniques.
The results from our project will have the following broader impacts:
improved allocation of resources in datacenters that handle virtually
all of our Internet needs (e.g., email, web services, e-commerce,
computing needs of small businesses); new techniques for sharing
information in networks under adversarial or natural threats (e.g., ad
hoc networks in disaster recovery, military communications);
cost-effective methods for realizing important communication paradigms
in communication networks.
Last Modified: 12/27/2017
Modified by: Rajmohan Rajaraman
Please report errors in award information by writing to: awardsearch@nsf.gov.
