The Effects of Locality on Efficient Distributed Computation

局部性对高效分布式计算的影响

• 批准号: RGPIN-2017-05936
• 负责人: Miller, Avery
• 金额: $ 1.46万
• 依托单位: University of Manitoba
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=677320
• 关键词: Effects; Locality; Efficient; Distributed; Computation

We live in an era of increasing connectivity. The days where computation happens at a single machine are coming to an end, and now our systems often comprise of a set of independent devices that have to interact to accomplish a goal without a central coordinator. This shift has introduced many new challenges and has forced us to think about algorithms and computation in a different way. One central issue that is unique to distributed algorithm design is that of "locality", a term that means that each device might have very limited information about the entire system, or can only view and communicate with other nearby devices. ******Our goal in this research is to better understand how different degrees of locality affect how efficient distributed algorithms can be. We consider the notion of efficiency in a broad sense, since different applications have different priorities with respect to resource consumption. Three important measures of efficiency are: time (how fast is the algorithm), cost (how much money or fuel does it take to run the algorithm), and communication (what are the network bandwidth requirements). Our main contributions will be to formally and precisely analyze the tradeoff between the efficiency of algorithms (with respect to the three measures listed above) and locality constraints. More specifically, this involves producing two kinds of results: ***(1) describing efficient algorithms when information and/or device capabilities are restricted, and, ***(2) proving impossibility results that give the best efficiency bounds that we can hope for under such restrictions. ******We have identified four application areas where we will focus our efforts in producing these kinds of results: ***(Area 1) Static Networks with Synchronous Communication***(Area 2) Networks of Mobile Nodes with Wireless Radio Communication***(Area 3) Autonomous Robots in Unknown Environments***(Area 4) Routing Packets in Networks with Bounded Buffers******In the next 5 years, I plan to complete the following projects within each of the above application areas:***(Area 1) Determining the optimal leader election algorithms under all possible ranges of information locality.***(Area 2) Determining the optimal neighbour discovery algorithms for vehicles traveling on simple road networks, both under information restrictions and communication/sensing restrictions.***(Area 3) Determining the optimal rendezvous algorithms for autonomous robots in an unknown environment with limited communication and vision.***(Area 4) Determining the best strategy for forwarding packets in a network where each router has a small memory buffer and limited information about the rest of the network.******I plan to directly train 8-10 HQP in the next 5 years, and I will be indirectly involved in the training of other HQP in our newly-formed collaborative research lab.**

我们生活在一个互联互通日益增强的时代。在一台机器上进行计算的日子即将结束，现在我们的系统通常由一组独立的设备组成，这些设备必须在没有中央协调器的情况下进行交互才能实现目标。这种转变带来了许多新的挑战，迫使我们以不同的方式思考算法和计算。分布式算法设计独特的一个核心问题是“局部性”，这是一个术语，意味着每个设备关于整个系统的信息可能非常有限，或者只能查看附近的其他设备并与其通信。*我们在这项研究中的目标是更好地了解不同程度的局部性如何影响分布式算法的效率。我们在广义上考虑效率的概念，因为不同的应用程序在资源消耗方面具有不同的优先级。衡量效率的三个重要指标是：时间(算法的速度有多快)、成本(运行算法需要多少金钱或燃料)和通信(网络带宽要求是什么)。我们的主要贡献将是正式和准确地分析算法效率(关于上面列出的三个衡量标准)和位置限制之间的权衡。更具体地说，这涉及产生两种结果：*(1)描述当信息和/或设备能力受到限制时的有效算法，以及*(2)证明不可能的结果，这些结果给出了我们在这样的限制下所能期望的最佳效率界限。*我们已经确定了四个应用领域，将重点放在以下四个应用领域：*(区域1)同步通信静态网络*(区域2)无线通信移动节点网络*(区域3)未知环境中的自主机器人*(区域4)未来5年内在有界缓冲区的网络中路由包*我计划在上述每个应用领域内完成以下项目：*(区域1)确定所有可能的信息局部性范围下的最优领导人选举算法。*(区域2)确定在简单道路网络上行驶的车辆的最优邻居发现算法，在信息限制和通信/感知限制下。*(区域3)在通信和视觉受限的未知环境中确定自主机器人的最佳交会算法。*(区域4)在每个路由器的内存缓冲区较小且网络其余部分信息有限的网络中确定转发数据包的最佳策略。*我计划在未来5年直接培训8-10个HQP，并将在我们新成立的协作研究实验室间接参与其他HQP的培训。**