Asynchronous Resilient Linearizability - Chordia, Sagar; Rajamani, Sriram; Rajan, Kaushik; Ramalingam, G.; Vaswani, Kapil (Microsoft Technical Report, 2013)
In this paper we address the problem of implementing a distributed data-structure that can tolerate (non-byzantine) process failures in an asynchronous message passing system, while guaranteeing correctness (linearizability with respect to a given sequential speciﬁcation) and resiliency (the operations are guaranteed to terminate, as long as a majority of the processes do not fail). We consider a class of data-structures whose operations can be classiﬁed into two kinds: update operations that can modify the data-structure but do not return a value and read operations that return a value, but do not modify the data-structure. We show that if every pair of update operations commute or nullify each other, then resilient linearizable replication is possible for the data-structure. We propose an algorithm for this class of data-structures with a message complexity of two message round trips for all read operations and O(n) round trips for all update operations. We also show that if there exists some reachable state where a pair of idempotent update operations neither commute nor nullify each other, resilient linearizable replication is not possible.
International Symposium on Distributed Computing (DISC)