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

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

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.