Building a Verifiable Logical Clock for P2P Networks
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917747351355392 |
|---|---|
| author | Sun, Guangda Tao, Tianyang Guo, Yanpei Hu, Michael Yiqing Li, Jialin |
| author_facet | Sun, Guangda Tao, Tianyang Guo, Yanpei Hu, Michael Yiqing Li, Jialin |
| contents | Logical clocks are a fundamental tool to establish causal ordering of events in a distributed system. They have been applied in weakly consistent storage systems, causally ordered broadcast, distributed snapshots, deadlock detection, and distributed system debugging. However, prior logical clock constructs fail to work in an open network with Byzantine participants. In this work, we present Chrono, a novel logical clock system that targets such challenging environment. We first redefine causality properties among distributed processes under the Byzantine failure model. To enforce these properties, Chrono defines a new validator abstraction for building fault-tolerant logical clocks. Furthermore, our validator abstraction is customizable: Chrono includes multiple backend implementations for the abstraction, each with different security-performance trade-offs. We have applied Chrono to build two decentralized applications, a mutual exclusive service and a weakly consistent key-value store. Chrono adds only marginal overhead compared to systems that tolerate no Byzantine faults. It also out-performs state-of-the-art BFT total order protocols by significant margins. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_13349 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Building a Verifiable Logical Clock for P2P Networks Sun, Guangda Tao, Tianyang Guo, Yanpei Hu, Michael Yiqing Li, Jialin Distributed, Parallel, and Cluster Computing Logical clocks are a fundamental tool to establish causal ordering of events in a distributed system. They have been applied in weakly consistent storage systems, causally ordered broadcast, distributed snapshots, deadlock detection, and distributed system debugging. However, prior logical clock constructs fail to work in an open network with Byzantine participants. In this work, we present Chrono, a novel logical clock system that targets such challenging environment. We first redefine causality properties among distributed processes under the Byzantine failure model. To enforce these properties, Chrono defines a new validator abstraction for building fault-tolerant logical clocks. Furthermore, our validator abstraction is customizable: Chrono includes multiple backend implementations for the abstraction, each with different security-performance trade-offs. We have applied Chrono to build two decentralized applications, a mutual exclusive service and a weakly consistent key-value store. Chrono adds only marginal overhead compared to systems that tolerate no Byzantine faults. It also out-performs state-of-the-art BFT total order protocols by significant margins. |
| title | Building a Verifiable Logical Clock for P2P Networks |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2405.13349 |