EAGER: Noisy Computation of Distributed State Machines

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

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.