Computer Science
Distributed Causal Memory in the Presence of Byzantine Servers
Document Type
Conference Paper
Abstract
We study distributed causal shared memory (or distributed read/write objects) in the client-server model over asynchronous message-passing networks in which some servers may suffer Byzantine failures. Since Ahamad et al. proposed causal memory in 1994, there have been abundant research on causal storage. Lately, there is a renewed interest in enforcing causal consistency in large-scale distributed storage systems (e.g., COPS, Eiger, Bolt-on). However, to the best of our knowledge, the fault-tolerance aspect of causal memory is not well studied, especially on the tight resilience bound. In our prior work, we showed that 2 f+1 servers is the tight bound to emulate crash-tolerant causal shared memory when up to f servers may crash. In this paper, we adopt a typical model considered in many prior works on Byzantine-tolerant storage algorithms and quorum systems. In the system, up to f servers may suffer Byzantine failures and any number of clients may crash. We constructively present an emulation algorithm for Byzantine causal memory using 3 f+1 servers. We also prove that 3 f+1 is necessary for tolerating up to f Byzantine servers. In other words, we show that 3 f+1 is a tight bound. For evaluation, we implement our algorithm in Golang and compare their performance with two state-of-the-art fault-tolerant algorithms that ensure atomicity in the Google Cloud Platform.
Publication Title
2019 IEEE 18th International Symposium on Network Computing and Applications, NCA 2019
Publication Date
2019
ISBN
9781728125220
DOI
10.1109/NCA.2019.8935059
Keywords
asynchrony, Byzantine faults, causal memory, distributed storage system, evaluation, tight condition
Repository Citation
Tseng, Lewis; Wang, Zezhi; Zhao, Yajie; and Pan, Haochen, "Distributed Causal Memory in the Presence of Byzantine Servers" (2019). Computer Science. 136.
https://commons.clarku.edu/faculty_computer_sciences/136
APA Citation
Tseng, L., Wang, Z., Zhao, Y., & Pan, H. (2019, September). Distributed causal memory in the presence of byzantine servers. In 2019 IEEE 18th International Symposium on Network Computing and Applications (NCA) (pp. 1-8). IEEE.