Accelerating distributed protocols with clock synchronization
Abstract/Contents
- Abstract
- Distributed systems are at the heart of computing today and the distributed protocols stand at the core of these systems. Distributed protocols help to coordinate the state and actions at the different servers constituting the distributed system. These protocols are required to possess two main properties: (i) Correctness—the protocol should correctly execute the action required of it, even in the face of the failure of one or more servers in the distributed system; and (ii) Efficiency—the execution of the protocol should take the least amount of resources in the distributed system as well as the least amount of time. However, despite the past decades of effort that has been spent in designing distributed protocols, achieving both goals (correctness and efficiency) is non-trivial and such protocols are often bottlenecks to many industrial systems (e.g., Kafka, Pulsar, TiDB) in practical use. In trying to understand the reason for these bottlenecks, we realize that, although these protocols aim to satisfy different correctness properties (e.g., linearizability, strict serializability, etc.), these correctness properties all require the protocols to establish certain kind of global ordering agreement across multiple servers, i.e., the multiple servers should take actions according to the same order. The establishment of such a global ordering agreement is not easy for prior protocols, because they have all assumed that the servers of the distributed system do not have a "global view": Each node is only aware of its own state and not the state of other nodes. As a result, prior works usually use one server to play the "leader" role to decide an ordering of the actions; the other ("follower") servers follow the leader's decision and take actions according to the decided order. Such designs can easily cause the throughput bottleneck at the leader, and also cost more latency overheads due to the multiple rounds of communication between the leader and the followers. We aim to avoid such performance bottlenecks caused by the lack of global view. Clock synchronization provides an elegant workaround to do so: By synchronizing the clocks among the servers, these servers are equipped with a global view, or more precisely, a "common clock". After the equipment of the common clock, the servers can refer to their local clock time and take actions simultaneously at a specified time, without relying on a centralized leader to coordinate them. Such a design has not been practical in the past, because tightly synchronizing the clocks at the different servers itself requires a highly performant distributed protocol! Until recently, such a protocol just wasn't available. But, the seminal work of Geng et. al. has developed just such a clock synchronization protocol, making the idea of "common clock" become realistic. Driven by the "common clock" idea, we first develop a general primitive in the thesis, namely deadline-ordered multicast (DOM), which serves as the basic building block for developing high- performance protocols. Simply speaking, DOM works in a "multi-sender-and-multi-receiver" scenario and it equips all the senders and receivers with the common clock. As a result, the sender can specify a future time, called deadline, when it is about to multicast the message to receivers. Receivers, on the other hand, can process the message simultaneously at the specified deadline because they share the same timeline as the sender. Since DOM facilitates the establishment of ordering agreement (on processing messages) among receivers, it helps the distribute protocol to fulfill the correctness requirements more efficiently. Therefore, we are able to develop new distributed protocols which are more performant. Meanwhile, DOM also opens up the possibility of designing new "time-sensitive" systems which were hitherto not possible. In this thesis, we will see some examples of both types. Specifically, Common Clock-based protocols. We will present three distributed protocols, and all of them use DOM to achieve high performance. The three protocols are (1) Nezha (DOM for consensus), (2) Deacon (DOM for concurrency control), and (3) Tiga (DOM for both consensus and concurrency control). New time-sensitive system. We will also present a new financial exchange system called CloudEx. Different from the conventional exchange systems, CloudEx uses "DOM for fairness": By incorporating DOM, CloudEx can create more fair trading environment for the market participants to compete with each other.
Description
| Type of resource | text |
|---|---|
| Form | electronic resource; remote; computer; online resource |
| Extent | 1 online resource. |
| Place | California |
| Place | [Stanford, California] |
| Publisher | [Stanford University] |
| Copyright date | 2023; ©2023 |
| Publication date | 2023; 2023 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Author | Geng, Jinkun |
|---|---|
| Degree supervisor | Prabhakar, Balaji, 1967- |
| Degree supervisor | Rosenblum, Mendel |
| Thesis advisor | Prabhakar, Balaji, 1967- |
| Thesis advisor | Rosenblum, Mendel |
| Thesis advisor | Sivaraman Kaushalram, Anirudh |
| Degree committee member | Sivaraman Kaushalram, Anirudh |
| Associated with | Stanford University, School of Engineering |
| Associated with | Stanford University, Computer Science Department |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | Jinkun Geng. |
|---|---|
| Note | Submitted to the Computer Science Department. |
| Thesis | Thesis Ph.D. Stanford University 2023. |
| Location | https://purl.stanford.edu/jp960br9938 |
Access conditions
- Copyright
- © 2023 by Jinkun Geng
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...