Computer Science

Distributed Multi-writer Multi-reader Atomic Register with Optimistically Fast Read and Write

Document Type

Conference Paper

Abstract

A distributed multi-writer multi-reader (MWMR) atomic register is an important primitive that enables a wide range of distributed algorithms. Hence, improving its performance can have large-scale consequences. Since the seminal work of ABD emulation in the message-passing networks, many researchers study fast implementations of atomic registers under various conditions. "Fast'' means that a read or a write can be completed with 1 round-trip time (RTT), by contacting a simple majority. In this work, we explore an atomic register with optimal resilience and ''optimistically fast'' read and write operations. That is, both operations can be fast if there is no concurrent write. This paper has three contributions: (i) We present Gus, the emulation of an MWMR atomic register with optimal resilience and optimistically fast reads and writes when there are up to 5 nodes; (ii) We show that when there are > 5 nodes, it is impossible to emulate an MWMR atomic register with both properties; and (iii) We implement Gus in the framework of EPaxos and Gryff, and show that Gus provides lower tail latency than state-of-the-art systems such as EPaxos, Gryff, Giza, and Tempo under various workloads in the context of geo-replicated object storage systems.

Publication Title

Annual ACM Symposium on Parallelism in Algorithms and Architectures

Publication Date

2023

First Page

479

Last Page

488

ISBN

9781450395458

DOI

10.1145/3558481.3591086

Keywords

atomicity, evaluation, impossibility, register

APA Citation

Tseng, L., Zhou, N., Dumas, C., Bantikyan, T., & Palmieri, R. (2023). Distributed Multi-writer Multi-reader Atomic Register with Optimistically Fast Read and Write. arXiv preprint arXiv:2304.09382.

Link to Full Text

Share

COinS