Analyzing the number of slow reads for semifast atomic read/write register implementations

Abstract

Developing fast implementations of atomic read/write registers in the message passing model is among the fundamental problems in distributed computing. Typical implementations require two communication round trips for read and write operations. Dutta et al. [4] developed the first fast single writer, multiple reader (SWMR) atomic memory implementation, where all read and write operations complete in a single communication round trip. It was shown that fast implementations are possible only if the number of readers is constrained with respect to the number of register replicas and the number of replica failures. Addressing this constraint, Georgiou et al. [5] developed a solution for an arbitrary number of readers at the cost of allowing some reads to be slow, i.e., taking two round trips. They termed such implementations semifast. Once some reads are allowed to be slow, it is interesting to quantify the number of occurrences of slow reads in executions of semifast implementations. This paper analyzes the implementation [5] , yielding high probability bounds on the number of slow read operations per write operation. The analysis is performed for the settings with low and high contention of read and write operations. For scenarios with low contention it is shown that O(logR) slow read operations may suffice per write operation. For scenarios with high contention it is shown that if ω(logR) reads occur then the system may reach, with high probability, a state from which up to R slow reads may be performed. These probabilistic results are further supported by algorithm simulations.