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.