| NSF Org: |
CCF Division of Computing and Communication Foundations |
| Recipient: |
|
| Initial Amendment Date: | July 20, 2015 |
| Latest Amendment Date: | July 20, 2015 |
| Award Number: | 1527867 |
| Award Instrument: | Standard Grant |
| Program Manager: |
Tracy Kimbrel
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, 2019 (Estimated) |
| Total Intended Award Amount: | $400,000.00 |
| Total Awarded Amount to Date: | $400,000.00 |
| Funds Obligated to Date: |
|
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
4300 MARTIN LUTHER KING BLVD HOUSTON TX US 77204-3067 (713)743-5773 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
Houston TX US 77204-2015 |
| 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
The overarching goal of this project is to significantly advance the state of the art in the algorithmic foundations of distributed computing for dynamic networks. In a dynamic network, the topology of the network---both nodes (representing processors/endhosts) and communication links---changes continuously over time. Modern networking technologies such as peer-to-peer networks, overlay networks, and ad hoc wireless and mobile networks, are inherently very dynamic; furthermore, they are resource-constrained, unreliable, and vulnerable to attacks. Distributed/decentralized algorithms are critical to the efficient operation of large-scale communication networks, e.g., distributed shortest paths algorithms are used for routing in the Internet. Till recently, much of the distributed algorithmic theory developed over the last three decades has focused mainly on static networks; as such its results do not apply to dynamic networks. This necessitates the development of a solid theoretical foundation for robust, secure, and scalable distributed computing for dynamic networks. Such a foundation is critical to realize the full potential of these large-scale networks that have a wide variety of applications including communication, data storage and retrieval, environment monitoring, electronic commerce, resource distribution and sharing, and search.
The project will develop a rigorous theoretical foundation for distributed computing in highly dynamic networks. In particular, it will develop and analyze distributed algorithms that scale well to very large-sized networks, are highly robust to dynamic changes and large-scale failures, and are secure against malicious participants in the network. The project will result in an algorithmic toolkit which will provide the building blocks for performing distributed computation in dynamic networks, besides providing algorithms with performance guarantees and theoretical benchmarks for practitioners. The project has the potential to impact the design and engineering of topologically-aware and self-regulating networks, i.e., networks that can measure, monitor, and regulate themselves in a decentralized fashion. The PI plans to develop a new course and a textbook on distributed network algorithms that is closely related to the research undertaken. This research will actively involve postdoctoral researchers, graduate students, and undergraduate students.
The project has two key research goals. First, it will design and analyze scalable and robust distributed algorithms for fundamental distributed computing problems including agreement, leader election, storage and search, and routing. These problems are basic building blocks in distributed computing and are widely used. Motivated by fault-tolerance and security considerations, the project will study the above problems in an adversarial dynamic setting, that can also include the presence of Byzantine (malicious) nodes which may try to foil the distributed algorithm. The project will also study lower bounds on the performance of distributed algorithms including the amount of dynamism that can be tolerated. Second, it will develop fully-distributed algorithms for computing key global metrics of a network and to maintain dynamic networks with desirable properties. This addresses an important issue that is complementary and also critical to the first goal, i.e., how to measure basic parameters of a dynamic network such as its size, connectivity properties, conductance, average degree and other node-related statistics. A related goal is to construct and maintain dynamic networks with good topological properties such as low diameter, high connectivity, and high conductance. In both the above research goals, the key challenge is to design scalable distributed algorithms that are robust and fault-tolerant even under a high amount of dynamism and the presence of a large amount of Byzantine nodes. The project will build on and significantly extend the distributed algorithmic framework for dynamic networks that was recently developed by the PI and his collaborators.
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 results of this project has significantly advanced our ability to design provably good distributed algorithms for dynamic networks, in particular, Peer-to-Peer (P2P) Networks. P2P networks are highly dynamic networks (experiencing a high amount of churn, i.e., nodes joining and leaving the network over time) which pervade the modern networking technology with applications ranging from search and storage to electronic commerce and blockchain systems.
Intellectual Merit: The project has resulted in the design and analysis of new distributed algorithms for dynamic networks that are highly robust, scalable, and secure. In particular, for P2P networks efficient, secure, and robust distributed algorithms have been developed that can tolerate a large amount of churn and malicious behavior of nodes.
The project has also resulted in developing efficient algorithms for the fundamental information spreading in dynamic networks. Information spreading is a useful primitive in disseminating information through a network and serves as a building block for other distributed computing tasks.
It has also resulted in developing fully distributed algorithms for computing key global metrics of a network such as network size, and mixing time and to maintain dynamic networks with desirable properties such as low diameter, high connectivity, and high conductance.
Broader Impacts:
The results published in this project have the potential to impact the design of highly dynamic networks such as peer-to-peer networks. The result published in the 2015 IEEE Symposium on the Foundations of Computer Science (FOCS) showed, for the first time, how one can design a dynamic network that can tolerate a large amount of churn, i.e., can maintain desirable properties such as connectivity, low-diameter, and high expansion. The protocol given in the FOCS 2015 paper can serve as a building block to design dynamic peer-to-peer networks that can tolerate a large amount of adversarial churn.
The above result has been significantly extended in a subsequent work (under submission) in a way that will also tolerate Byzantine nodes, which is important in theory as well as in practice. In the real-world, especially in P2P networks which have a open admission policy, it is easy for Byzantine nodes to enter the network and cause network disruption. Our result has the potential to serve as building blocks to build peer-to-peer networks that can work well under large amount of bad participants as well as tolerate dynamic behavior. This can have direct applications in designing emerging applications in blockchain systems.
The results of this project have been published in top peer-reviewed conferences in computer science.
The project has resulted in disseminating the work on dynamic networks to a more broader audience. This has been done by numerous talks given by the PI and his collaborators on dynamic networks in various institutions and workshops. The PI also has publihsed an expository article on dynamic networks (including the results of this project) in the Association of Computing Machinery's (ACM) SIGACT News, a magazine for the Computer Science theory community. The PI has also incorporated the results of this research in his Distributed Algorithms course taught at University of Houston and Indian Institute of Technoogy (IIT) at Madras.
The project has contributed to opportunities for research and mentoring of three Ph.D. students --- Soumyottam Chatterjee, Reza Fathi and Nguyen Dinh Pham (all at University of Houston, a minority serving Tier 1 public research institution) and two postdoctoral scholars --- Michele Scquizzato and Robert Gmyr (both at University of Houston). The project has also contributed to opportunities for research and mentoring of two other Ph.D. students --- Scott Roche and Mehraneh Liaee (both Northeastern University). Mehraneh Liaee is a female Ph.D. student.
The project has also contributed to collaborations with Prof. John Augutine (IIT Madras) and Prof. Anisur Molla (Indian Statistical Institute, Kolkatta), and Peter Robinson (City University of Hong Kong). These collaborations have resulted in more broadly disseminating the research topics among the researchers in the respective universities.
Last Modified: 11/08/2019
Modified by: Gopal Pandurangan
Please report errors in award information by writing to: awardsearch@nsf.gov.
