Analyzing the number of slow reads for semifast atomic read/write register implementations
Chryssis Georgiou, Sotirios Kentros, Nicolas Nicolaou, Alexander A. Shvartsman · 2009
Developing fast implementations of atomic read/write reg-isters in the message passing model is among the funda-mental problems in distributed computing. Typical imple-mentations 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 com-plete 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 regis-ter 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 inter-esting to quantify the number of occurrences of slow reads in executions of semifast implementations. This paper an-alyzes 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 proba-bility, a state from which up to R slow reads may be per-formed. These probabilistic results are further supported by algorithm simulations. KEY WORD: atomic memory, message-passing, fault-tolerance, probabilistic analysis