| NSF Org: |
CCF Division of Computing and Communication Foundations |
| Recipient: |
|
| Initial Amendment Date: | August 21, 2015 |
| Latest Amendment Date: | June 8, 2017 |
| Award Number: | 1461559 |
| Award Instrument: | Continuing Grant |
| Program Manager: |
A. Funda Ergun
CCF Division of Computing and Communication Foundations CSE Directorate for Computer and Information Science and Engineering |
| Start Date: | September 1, 2015 |
| End Date: | August 31, 2020 (Estimated) |
| Total Intended Award Amount: | $741,436.00 |
| Total Awarded Amount to Date: | $741,436.00 |
| Funds Obligated to Date: |
FY 2017 = $250,000.00 |
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
77 MASSACHUSETTS AVE CAMBRIDGE MA US 02139-4301 (617)253-1000 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
77 Massachusetss Avenue Cambridge MA US 02139-4301 |
| Primary Place of
Performance Congressional District: |
|
| Unique Entity Identifier (UEI): |
|
| Parent UEI: |
|
| NSF Program(s): | Algorithmic Foundations |
| Primary Program Source: |
01001718DB 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
The field of Distributed Computing Theory studies algorithms for well-behaved platforms consisting of powerful agents communicating over powerful networks. These algorithms typically guarantee strong correctness and performance properties. But modern distributed platforms such as wireless networks are less well-behaved: They exhibit unpredictable behavior, including agent failures and mobility, and may have resource limitations, such as bounds on communication, memory, and precision. These complications make it hard to design algorithms that guarantee strong properties. Algorithms may also have new types of requirements: flexibility to run in different situations, robustness to failures, and adaptiveness to change.
This project will attempt to understand the fundamental capabilities of such difficult distributed platforms, and to develop algorithms, lower bounds, and general techniques for such settings. It will focus on abstract graph-based networks, wireless networks, and biological insect colonies, while seeking unifying results. The project has the potential to produce a deeper understanding of ideas that underlie important types of distributed systems, to broaden the scope of Distributed Computing Theory, and to provide unification and fundamental principles for three disparate fields. Concretely, the project may enable design of more powerful and robust wireless networks, and contribute new methods for understanding the behavior of some biological systems.
The PI has a long track record of mentoring women students and postdocs, some of whom have become leaders of the field. In recruiting new project participants, the PI will make every effort to include women, minorities, and undergraduates. The PI has taught an advanced graduate course on wireless network algorithms several times, and plans to update it based on this project.
The project consists of three closely intertwined efforts to understand the fundamental capabilities of resource-constrained, dynamic distributed systems, and to develop algorithms, lower bounds, and general techniques for such systems. Specifically, the participants will focus on graph networks, wireless networks, and insect colonies, while seeking unifying results.
Part 1 deals with distributed algorithms for abstract graph-based networks. It will begin with the traditional CONGEST model, which imposes a strict bound on the amount of information that can be sent on communication links, and will consider restrictions of this model to special classes of graphs such as planar graphs. It will also consider dynamic versions of the CONGEST model and versions with limited storage. It will emphasize problems of communication, computation, and building network structures. Part 2 deals with the more concrete setting of wireless networks, using physical platform models that incorporate communication contention. This will include Radio Network models, in which message collisions result in losses, Signal-to-Interference-and-Noise models, in which message receipt depends on signal propagation patterns, models based on rudimentary forms of communication, and models that support network coding. The project will also define network abstraction layers to help decompose the task of algorithm design. A key issue will be uncertainty in communication behavior. Part 3 deals with the concrete setting of social insect colonies (such as ants or bees); for this, the participants will collaborate with insect biologists. These platforms are extremely dynamic, and are subject to severe limitations on storage, precision, computation, and communication. Insects in colonies coordinate to solve colony problems such as obtaining food, establishing trails, feeding brood, and choosing new nests; such activities can be viewed as resource-limited and highly dynamic distributed algorithms. There are many connections among these three parts: Similar problems appear in all three settings, and similar randomized algorithmic strategies should emerge. Algorithms for graph networks may be adapted to wireless networks or may help to explain how insect colonies behave. Algorithms for wireless networks or insect colonies may be understood more abstractly, in terms of graph networks. Transformations may allow algorithms and lower bounds to be ``ported'' from one setting to another. Algorithmic ideas arising for insect colonies may inspire entirely new styles of algorithms for wireless networks or graph networks, satisfying new flexibility, robustness, and adaptiveness properties. New metrics will be needed to capture these properties. Throughout, the project participants will seek common definitions, results, and general principles that span these different kinds of platforms, thus explaining in a deep and general way the impact of resource constraints and dynamicity on the possibility and costs of solving distributed problems.
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 field of distributed computing theory generally studies algorithms
for well-behaved computing platforms consisting of powerful agents
communicating over reliable networks. However, modern distributed
platforms such as wireless networks or robot swarms are less
well-behaved: they exhibit unpredictable behavior, including agent
failures and mobility, and may have stringent limitations on
communication, memory, and precision. These complications make it
hard to design algorithms with strong guarantees. Algorithms also
have new requirements: flexibility to run in different situations,
robustness to failures, and adaptiveness to change.
This project focused on understanding, in mathematical terms, the
fundamental capabilities of such difficult distributed computing
platforms, and on developing new algorithms and general algorithm
design and analysis techniques for such settings. The project
consisted of three closely intertwined efforts, involving graph-based
networks, wireless networks, and colonies of social insects. There
are many connections among these topics: similar problems appear in
all three settings, and similar algorithmic strategies and modeling
and analysis methods have emerged.
Results for graph-based networks include algorithms for many
fundamental graph problems, including constructing Maximal
Independent Sets (MISs) of nodes in network graphs, computing graph
distances, graph coloring, computing minimum spanning trees, and
constructing fault-tolerant overlay networks. For example, the new MIS
algorithm represents a great improvement over previous algorithms and
won a Best Paper award at a key algorithms conference. Another interesting
contribution was a new technique for running several distributed
algorithms concurrently, in the same network.
Results for wireless networks include algorithms for fundamental
problems of communication and leader election. The project produced a
new, efficient algorithm for leader election in the ``Signal to
Interference and Noise Ratio'' model of wireless communication,
in a setting where the nodes control the power of their transmitted
signals. The project also demonstrated how simple algorithms that were
originally designed for reliable radio networks can be adapted to work
well for solving communication problems in noise-prone networks; here
the key was to rely on a stochastic noise model. These results greatly
improve on previous results for worst-case noise models. Both of these
efforts won Best Paper awards at computer science theory
conferences. The project also considered novel wireless network
models, such as networks in which nodes communicate via ``beeps'',
rather than elaborate messages; such models are inspired by
communication in biological systems.
Results for insect colonies include algorithms and lower bounds for
problems of searching, colony density estimation, task allocation, and
reaching consensus. The project produced a density estimation
algorithm in which ants wander randomly and count the frequency of
encounters with other ants---a strategy used in real ant
colonies. Results include a precise analysis of the accuracy of the
estimates, as well as extensions of the algorithm by which ``bots''
could estimate the size of a social network. The project also
studied the problem of finding and agreeing upon a new nest; the
algorithms used by ants are similar to quorum-based algorithms used
for decision-making in computer systems. Again, a key here was to
model noise stochastically.
The project also began an exploration of algorithms that might be used
in brains to solve problems of focus and attention, decision-making,
neural representation of real-world concepts, learning, and
recognition. Brain algorithms are modeled by stochastic Spiking Neural
Networks (SNNs)---a type of directed graph network model that includes
high levels of stochastic uncertainty. The project developed
mathematical foundations for SNNs, including support for composing
networks. Problems studied include ``Winner-Take-All'', a problem of
choosing among many alternatives; here, the project produced
interesting tradeoffs between network size and time to converge on a
decisision. Also, the project has produced new models and algorithms
for robust learning of hierarchically structured data and of abstract
representations for unstructured data.
Intellectual Merit:
The project has produced many algorithms and lower bounds for
resource-constrained and dynamic distributed systems. It has focused
on wireless networks, graph-based networks, and biological systems,
while seeking unifying results. Similar kinds of mathematical modeling
frameworks and analysis methods apply throughout. Many of the
same problems arise in the different settings, such as problems of
consensus and leader election, with similar algorithmic solutions.
Some ideas, like stochastic noise models, recur throughout.
The project has produced new understanding of ideas that underlie
important types of distributed systems, has broadened the scope of
distributed computing theory to include new types of algorithms and
problems and new techniques, and has provided unification and
fundamental principles for three apparently-disparate fields.
It has shown how distributed algorithms techniques can help
biologists to understand the behavior of their systems, as well as
contributing new bio-inspired ideas to distributed computing theory.
Broader Impacts:
This work may contribute to the design of more powerful and robust
wireless networks.
For biology, it has introduced algorithms that are meaningful in
biological settings, as well as new computational methods for
understanding the behavior of biological systems. The work has
contributed to experimental study of insect colonies, by providing
models that explain colony decision-making, suggesting new
experiments, and providing new modeling and analysis techniques. It
has contributed to experimental neuroscience research on neural
mechanisms used in learning, by supplying an SNN-based modeling
methology that enables simple abstract description and simulation of
the mechanisms.
The work has also contributed to research on new kinds of computers
based on Spiking Neural Networks, by providing example networks to
test the designs.
The PI of this project is female, as are many of the students,
postdocs, and collaborators.
Last Modified: 11/07/2020
Modified by: Nancy A Lynch
Please report errors in award information by writing to: awardsearch@nsf.gov.
