Computer Science

Resilient distributed causal memory in client-server model

Document Type

Conference Paper

Abstract

We study distributed causal shared memory (or key-value pairs) in an asynchronous network under crash failures. Causal memory, introduced by Ahamad et al. in the context of multi-processor environment in 1994, is an abstraction which ensures that nodes agree on the relative ordering of read and write operations that are causally related on key-value pairs. Inspired by the recent interests in geo-replicated causal storage systems (e.g., COPS, Eiger, Bolt-on), we systematically study the fault-tolerance property of the causal shared memory in the client-server model in this work. We identify that 2f + 1 servers is both necessary and sufficient to build a resilient causal memory in the presence of up to f crashed servers. We provide both the necessity proof and a new optimal algorithm that matches the bound. For evaluation, we implement our algorithm in Golang and compare the performance with state-of-the-art fault-tolerant algorithms that ensure strong consistency in the Google Cloud Platform.

Publication Title

Proceedings of IEEE Pacific Rim International Symposium on Dependable Computing, PRDC

Publication Date

2019

Volume

2019-December

First Page

95

Last Page

104

ISSN

1541-0110

ISBN

9781728149615

DOI

10.1109/PRDC47002.2019.00035

Keywords

asynchrony, causal memory, Crash faults, Distributed storage system, Evaluation

APA Citation

Tseng, L., Wang, Z., & Zhao, Y. (2019, December). Resilient Distributed Causal Memory in Client-Server Model. In 2019 IEEE 24th Pacific Rim International Symposium on Dependable Computing (PRDC) (pp. 95-9509). IEEE.

Link to Full Text

Share

COinS