CAREER: Deadline-Ordered Multicast: A Network Primitive for Cloud-Native Distributed Systems

分布在多台机器上的计算机系统-也称为分布式系统-为当今大多数数字世界和绝大多数网络应用程序提供动力。这种数字系统包括存储系统和搜索引擎以及网络服务。将数字系统分布在多台机器上有多个好处，包括(1)通过将计算转移到不同的机器来在机器故障中幸存下来的能力，以及(2)利用多台机器的能力更快完成计算的能力。为了实现这些好处，分布式系统中的机器必须相互协调，以确保结果与在单一机器上执行计算的理想化错觉相同。这个项目将通过开发一种新的抽象--截止日期有序多播(DOM)来显著加快协调速度，它结合了：(1)多播：能够同时从发送方向多个接收方发送消息的能力；(2)同步时钟：确保在任何时刻，不同机器上的时钟显示相同的时间值，并且这些时钟彼此同步前进的技术。该项目将演示如何使用DOM来加速广泛使用的计算机系统，如分布式数据库、协调服务和区块链。该项目还将培训本科生和研究生，使用各种方法来理解在考虑分布式系统时同步时钟的好处。分布式系统是当今计算的核心，包括广泛使用的系统，如分布式数据库、容错键值存储和分布式分类账。这些系统的核心是分布式协议，如故障容错一致性、并发控制和拜占庭容错一致性。多年来，在改进分布式协议的性能方面花费了大量的努力，包括最近利用更丰富的网络服务来改进分布式协议的努力。此类服务包括交换机组播、可编程交换机、可编程网络接口卡、网内优先级队列以及对路由的控制。然而，目前许多分布式系统都是由云租户部署的，这些租户无法访问丰富的网络服务，因此无法从丰富的网络服务带来的协议性能提升中受益。该项目将开发一种新的网络原语，称为截止日期有序多播(DOM)，它将使在公有云上构建高性能的分布式协议变得更加容易。DOM利用了两项关键技术：(1)最近提供的同步时钟作为一种服务，现在允许在公共云中紧密同步时钟；(2)多播，它很难在互联网上找到牵引力，但对于分布式系统核心的单发送器-多接收器通信来说是理想的。DOM在消息的截止日期或之后将来自发送者的多播消息传递给多个接收者，并按截止日期顺序传递多个消息。DOM提供了一个一致的顺序(截止日期的顺序)，不同的接收者可以按照该顺序处理一组消息，从而加速了过程中的几个分布式协议。这项提议将开发DOM抽象，设计优化的DOM服务，并制作几个展示DOM价值的应用程序的原型。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Computer systems spread out over multiple machines---also known as distributed systems---power most of today's digital world and the vast majority of web applications. Such digital systems include storage systems and search engine as well as web services. Spreading out digital systems across machines has multiple benefits including (1) the ability to survive machine failures by moving computation to a different machine and (2) the ability to leverage the capabilities of multiple machines to finish computations faster. To realize these benefits, the machines within a distributed system must coordinate amongst themselves to ensure the result is identical to an idealised illusion of executing the computation on a single machine. This project will make coordination significantly faster by developing a new abstraction, deadline-ordered multicast (DOM), which combines: (1) Multicast: The ability to simultaneously transmit a message from a sender to multiple receivers and (2) Synchronized clocks: Technology to ensure that, at any instant, clocks on various machines display the same value of time and that these clocks progress in lock step with each other. The project will demonstrate how DOM can be used to accelerate widely used computer systems, such as distributed databases, coordination services, and blockchains. The project will also train both undergraduate and graduate students using a variety of approaches to understand the benefits of synchronized clocks when thinking about distributed systems. Distributed systems are at the heart of computing today and include widely used systems such as distributed databases, fault-tolerant key-value stores, and distributed ledgers. At the core of these systems are distributed protocols such as crash-fault-tolerant consensus, concurrency control, and Byzantine-fault-tolerant consensus. Much effort has been expended on improving the performance of distributed protocols over the years including recent efforts that leverage richer network services to improve distributed protocols. Such services include switch multicast, programmable switches, programmable network-interface cards, in-network priority queues, and control over routing. However, many distributed systems today are deployed by cloud tenants, who have no access to such rich network services, making it impossible for them to benefit from the improved protocol performance enabled by such rich network services.This project will develop a new network primitive called deadline-ordered multicast (DOM) that will make it easier to construct high-performance distributed protocols on the public cloud. DOM leverages 2 key techniques: (1) the recent availability of synchronized clocks as a service, which now permit tightly synchronized clocks in the public cloud and (2) multicast, which struggled to find traction in the Internet, but is ideal for the one-sender-multi-receiver communication at the heart of distributed systems. DOM delivers a multicast message from a sender to multiple receivers at or after a message's deadline and delivers multiple messages in deadline order. DOM provides a consistent order (the order of deadlines) in which different receivers process a set of messages, accelerating several distributed protocols in the process. This proposal will develop the DOM abstraction, design an optimized DOM service, and prototype several applications demonstrating DOM's value.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.