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

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.

Byzantine Consensus with Local Multicast Channels

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

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