EAGER: Noisy Computation of Distributed State Machines

EAGER：分布式状态机的噪声计算

• 批准号: 1649484
• 负责人: Calvin Newport
• 金额: $ 7.23万
• 依托单位: Georgetown University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-09-01 至 2018-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1649484&HistoricalAwards=false
• 关键词: EAGER; Noisy; Computation; Distributed; State

Distributed systems are collections of computational devices that work together to solve problems. These systems play an increasingly important role in modern society - from data centers serving popular websites to GPU clusters tackling deep scientific problems. A key obstacle in designing these systems is that due to many different unpredictable factors individual devices might behave in a faulty manner. Standard strategies to cope with this possibility assume that only a bounded fraction of the devices might suffer from faults (which can be catastrophic), while the rest execute perfectly. This project, by contrast, explores novel modeling and analysis techniques for studying systems in which every device might be faulty to some degree, but the faults are assumed less severe than the typical definitions. By doing so, it tackles the following fundamental question: when and how is it possible for a collection of locally unreliable devices to work together to reliably solve a global problem? Answers to this question can support the development of more cost effective and robust distributed systems. They will also provide potential insight into coordination problems in nature where the underlying computational "devices" (be they cells, ants, or bees) execute much less precisely than digital processors. In addition to these large scale impacts, this project will also have a local impact in the classroom. The PI will include insights from this work into a course that includes a module on novel ideas in the theory of distributed systems, and the project will help fund a graduate student to work on the topic.In more detail, the canonical approach to formally modeling a distributed system is to represent the distributed processes as state machines that interact through shared objects or network channels. This project describes local faults (called "computational noise" in the following) as state machine transition functions that might probabilistically deviate from their specification. There are many different ways to instantiate this general idea. This project will investigate two main approaches: one which describes noise by allowing bounded adversarial modifications to the system's state machines, and another which describes noise as injections of random offsets to the underlying multi-dimensional vector of property values describing each device's current configuration. The project will apply these two approaches to two representative and well-studied problems: symmetry breaking on a shared channel and threshold detection with population protocols. The goal is to produce new results of immediate application to existing areas of computer science research, as well as to develop a foundation of models and tools on which a long-term investigation of this topic can be built.

分布式系统是一起工作以解决问题的计算设备的集合。这些系统在现代社会中发挥着越来越重要的作用-从服务于热门网站的数据中心到解决深层科学问题的GPU集群。设计这些系统的一个关键障碍是，由于许多不同的不可预测因素，单个设备可能会以错误的方式运行。科普这种可能性的标准策略假设只有有限的一部分设备可能会出现故障（这可能是灾难性的），而其余的设备可以完美地执行。相比之下，这个项目探索了新的建模和分析技术，用于研究系统，其中每个设备都可能在某种程度上出现故障，但故障被认为没有典型定义那么严重。通过这样做，它解决了以下基本问题：何时以及如何使一组本地不可靠的设备协同工作，以可靠地解决全球问题？ 这个问题的答案可以支持更经济有效和强大的分布式系统的开发。它们还将为自然界中的协调问题提供潜在的洞察力，在这些问题中，底层的计算“设备”（无论是细胞、蚂蚁还是蜜蜂）的执行精度远低于数字处理器。除了这些大规模的影响，这个项目也将在课堂上产生当地的影响。PI将把这项工作的见解纳入到一门课程中，该课程包括一个关于分布式系统理论中新思想的模块，该项目将资助一名研究生从事该主题的工作。更详细地说，正式建模分布式系统的规范方法是将分布式进程表示为通过共享对象或网络通道进行交互的状态机。这个项目将局部故障（以下称为“计算噪声”）描述为状态机转换函数，这些函数可能概率性地偏离其规范。有许多不同的方法来实例化这个一般的想法。该项目将研究两种主要方法：一种通过允许对系统状态机进行有界对抗性修改来描述噪声，另一种将噪声描述为将随机偏移注入到描述每个设备当前配置的属性值的基础多维向量。该项目将这两种方法应用于两个具有代表性的和充分研究的问题：对称性破缺共享信道和人口协议的阈值检测。其目标是产生新的成果，立即应用到现有的计算机科学研究领域，以及开发模型和工具的基础上，可以建立一个长期的调查这一主题。

项目成果

Symmetry Breaking with Noisy Processes

噪声过程导致对称性破缺

• DOI: 10.1145/3087801.3087814
• 发表时间: 2017
• 期刊: Proceedings of the ACM Conference on the Principles of Distributed Computing
• 作者: Gilbert, Seth;Newport, Calvin
• 通讯作者: Newport, Calvin