Brief Announcement: Fault-Tolerant SemiFast Implementations of Atomic Read/Write Registers

摘要

Atomic (linearizable) read/write memory is one of the fundamental abstractions in distributed computing. Atomic object services in message-passing systems allow processes to share information with precise consistency guarantees in the presence of asynchrony and failures. A seminal implementation of atomic memory of Attiya et al. [1] gives a single-writer, multiple reader (SWMR) solution where each data object is replicated at n message-passing nodes. Following this development, a folklore belief developed that in messaging-passing atomic memory implementations "atomic reads must write". However, recent work by Dutta et al. [2] established that if the number of readers is appropriately constrained with respect to the number of replicas, then single communication round implementations of reads are possible. Such an implementation given in [2] is called fast. Furthermore it was shown that any implementation with a larger set of readers cannot have only the single round-trip reads. Thus when the number of readers can be large, it is interesting to consider semifast implementations where the writes involve a single communication round and where the reads may involve one or two rounds with the goal of having as many as possible single round reads.