| NSF Org: |
CCF Division of Computing and Communication Foundations |
| Recipient: |
|
| Initial Amendment Date: | August 10, 2017 |
| Latest Amendment Date: | September 15, 2018 |
| Award Number: | 1733872 |
| Award Instrument: | Standard 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, 2017 |
| End Date: | August 31, 2021 (Estimated) |
| Total Intended Award Amount: | $318,735.00 |
| Total Awarded Amount to Date: | $318,735.00 |
| Funds Obligated to Date: |
|
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
506 S WRIGHT ST URBANA IL US 61801-3620 (217)333-2187 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
IL US 61820-7473 |
| Primary Place of
Performance Congressional District: |
|
| Unique Entity Identifier (UEI): |
|
| Parent UEI: |
|
| NSF Program(s): | Algorithms in the Field |
| 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 growing ubiquity of smartphones, combined with the rapid improvement of operating system support for direct wireless communication between nearby devices, creates a compelling opportunity for the emergence of easy to deploy and widely used smartphone peer-to-peer applications. There are several use cases for such applications. For example, in many user environments, cellular data minutes are bought in small blocks and carefully conserved by users, generating an interest in networking operations that can avoid infrastructure. In addition, smartphone peer-to-peer networks can bring connectivity to settings such as disaster zones, festivals, or wilderness where traditional cellular and WiFi coverage is compromised, overwhelmed, or non-existent. This project aims to develop network algorithms and tools that simplify the design of useful distributed systems on top of local peer-to-peer connections. The project has the potential for significant societal impact by enabling compelling new applications for smartphone peer-to-peer networks. The project is also expected to have significant educational impact.
The project focuses on designing and analyzing provably correct and efficient network computation algorithms that can run on top of existing smartphone peer-to-peer services, and simplify the design of peer-to-peer systems that can be deployed on existing smartphone hardware. The project consists of two major research directions. The first research direction is experimental in nature. It will study and evaluate peer-to-peer services available in commodity smartphone operating systems and define a small number of validated abstractions that capture their capabilities and behavior. The second research direction is theoretical in nature. It will describe and analyze solutions to well-motivated network computation primitives using these abstractions. The problems studied will include consensus, leader election, rumor spreading, gossip and function computation. The project will seek both provably correct and efficient algorithms as well as lower bounds that establish fundamental limits for useful computation in this setting.
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.
Smartphones have become ubiquitous in recent years, and their usage continues to grow. The smartphones, and other similar devices, are increasingly supporting direct wireless communication with nearby devices. Often, the devices may be able to communicate with each other using multiple different wireless technologies, such as Wi-Fi and Bluetooth. Such technologies make it possible to deploy peer-to-peer applications on these devices. This project addressed design and analysis of distributed computation algorithms that can be implemented on top of such networks.
We made significant progress on the problem of distributed consensus in the presence of Byzantine faulty agents. In this problem, the specific objective for a set of agents is to agree on a valid decision as a function of the inputs of the agents. Due to the local broadcast property of the wireless medium, there is an opportunity to improve performance by exploiting the wireless medium. Importantly, the broadcast medium also limits the ability of Byzantine faulty agents to equivocate, or to send inconsistent information to their neighbors. In some instances, the wireless links may not be bidirectional. Such properties of the wireless medium can affect algorithm design. We have investigated the Byzantine consensus problem when local broadcast capability is available, and also addressed the challenge posed by directed links in the network.
We have also explored other distributed algorithms. In one research direction, we considered the problem of designing efficient algorithms for fault-tolerance in graph computations. In particular, we begin with a solution to a graph problem of interest, e.g., a maximal independent set (MIS), in a given graph. We then consider the possibility that, at some point in the future, some nodes may crash, invalidating the initially chosen solution. The goal of our work is to design efficient algorithms to recompute the solution (e.g., MIS), given the faults that have occurred. In our approach, the network may perform some pre-computation preparing for potential failures before they actually occur, and then may perform additional computation repairing the initial solution once failures do occur. The pre-computation is necessarily independent of the exact failures that will occur later in time, but the repair time would generally depend on the failures that actually occur. We have obtained interesting results in the context of MIS and maximal matching problems. In another research direction, we explored the contention resolution problem under the assumption that nodes are provided with imperfect prior knowledge, particularly, in the form of a probability distribution over the possible network sizes. We characterized the performance of a contention resolution algorithm as a function of this distribution. Through our work on these and related problems, we have improved the understanding of distributed computations over peer-to-peer networks.
Selected results from the project have been published in peer-reviewed venues. Due to the increasing deployment of devices that can support peer-to-peer connectivity, the results from this project have a significant potential for impact. Also, some of our fundamental results are expected to have an impact on future research in the area.
Last Modified: 12/14/2021
Modified by: Klara Nahrstedt
Please report errors in award information by writing to: awardsearch@nsf.gov.
