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

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

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.