Implementing three exchange read operations for distributed atomic storage

doi:10.1016/j.jpdc.2022.01.024

Implementing three exchange read operations for distributed atomic storage

2022-05-01

2

PRE

AI

C

Chryssis Georgiou

T

Theophanis Hadjistasi

N

Nicolas Nicolaou *

A

Alexander A. Schwarzmann

DOI：10.1016/j.jpdc.2022.01.024

Original

Original request for help

Save

Abstract

En 中文

Communication latency typically dominates the performance of message-passing systems, and consequently defines the efficiency of operations of algorithms implementing atomic read/write objects in asynchronous, crash-prone, message-passing systems. Here latency is measured in terms of the number of communication exchanges (or simply exchanges) involved in each operation. We present four algorithms, two for the single-writer/multiple-reader (SWMR) and two for the multi-writer/multiple-reader (MWMR) settings, that allow reads to take two or three exchanges, advancing the state-of-the-art in this area. Writes take the same number of exchanges as in prior works (i.e., two for SWMR and four for MWMR settings). In contrast with existing efficient implementations, ours come with no constraints on reader participation in both settings, and on the number of writers in the MWMR setting. Correctness of algorithms is rigorously argued. We conclude with an empirical study demonstrating the practicality of the algorithms, and identifying settings in which their read performance, is clearly superior compared to relevant algorithms. (c) 2022 Elsevier Inc. All rights reserved.

Keywords:

Atomicity

Read/write objects

Shared memory

Fault-tolerance

Implementing three exchange read operations for distributed atomic storage

Abstract

Journal

Organization