AiTF: Collaborative Research: Algorithms for Smartphone Peer-to-Peer Networks

AiTF：协作研究：智能手机点对点网络算法

• 批准号: 1733872
• 负责人: Klara Nahrstedt
• 金额: $ 31.87万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-09-01 至 2021-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1733872&HistoricalAwards=false
• 关键词: AiTF; Collaborative; Research; Algorithms; Smartphone

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.

智能手机的日益普及，再加上对附近设备之间直接无线通信的操作系统支持的快速改进，为出现易于部署和广泛使用的智能手机对等应用创造了一个引人注目的机会。这类应用程序有几个用例。例如，在许多用户环境中，蜂窝数据分钟是以小块形式购买的，并由用户仔细保存，从而产生了对可以避免基础设施的网络运营的兴趣。此外，智能手机点对点网络可以为灾区、节日或荒野等环境带来连接，在这些环境中，传统的蜂窝和WiFi覆盖范围受到影响、不堪重负或根本不存在。该项目旨在开发网络算法和工具，以简化基于本地点对点连接的有用分布式系统的设计。该项目通过为智能手机对等网络启用引人注目的新应用程序，有可能产生重大的社会影响。预计该项目还将产生重大的教育影响。该项目专注于设计和分析可证明正确和高效的网络计算算法，这些算法可以在现有的智能手机对等服务上运行，并简化可以部署在现有智能手机硬件上的对等系统的设计。该项目由两个主要研究方向组成。第一个研究方向是实验性的。它将研究和评估商用智能手机操作系统中提供的对等服务，并定义少量经过验证的抽象，以捕获它们的功能和行为。第二个研究方向是理论性的。它将使用这些抽象来描述和分析动机良好的网络计算基元的解决方案。研究的问题将包括共识、领导人选举、谣言传播、八卦和函数计算。该项目将寻求可证明正确和有效的算法，以及为这种情况下的有用计算建立基本限制的下限。

项目成果

Exact Byzantine Consensus on Undirected Graphs under Local Broadcast Model

本地广播模型下无向图的精确拜占庭共识

• DOI: 10.1145/3293611.3331619
• 发表时间: 2019
• 期刊: ACM Symposium on Principles in Distributed Computing
• 作者: Khan, Muhammad Samir;Naqvi, Syed Shalan;Vaidya, Nitin H.
• 通讯作者: Vaidya, Nitin H.

Exact Byzantine Consensus on Arbitrary Directed Graphs Under Local Broadcast Model

本地广播模型下任意有向图的精确拜占庭共识

• DOI: 10.4230/lipics.opodis.2019.30
• 发表时间: 2019
• 期刊: International Conference on Principles of Distributed Systems
• 作者: Khan, Muhammad Samir;Tseng, Lewis;Vaidya, Nitin
• 通讯作者: Vaidya, Nitin

Byzantine Consensus with Local Multicast Channels

与本地多播通道的拜占庭共识

• DOI: 10.4230/lipics.disc.2021.26
• 发表时间: 2021
• 期刊: Leibniz international proceedings in informatics
• 作者: Khan, Muhammad Samir

Testing Equality Under the Local Broadcast Model

检验本地广播模式下的平等性

• DOI: 10.1007/978-3-030-79527-6_15
• 发表时间: 2021
• 期刊: 28th International Colloquium on Structural Information and Communication Complexity
• 作者: Khan M.S., Vaidya N.H.