EAGER: Noisy Computation of Distributed State Machines

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

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.