@techreport{chordia2013asynchronous,
author = {Chordia, Sagar and Rajamani, Sriram and Rajan, Kaushik and Ramalingam, G. and Vaswani, Kapil},
title = {Asynchronous Resilient Linearizability},
year = {2013},
month = {July},
abstract = {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 specification) 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 classified 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.},
publisher = {Microsoft Technical Report},
url = {http://approjects.co.za/?big=en-us/research/publication/asynchronous-resilient-linearizability-2/},
edition = {International Symposium on Distributed Computing (DISC)},
number = {MSR-TR-2013-71},
note = {International Symposium on Distributed Computing (DISC)},
}