Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Asynchronous Resilient Linearizability

Sagar Chordia, Sriram Rajamani, Kaushik Rajan, G. Ramalingam, and Kapil Vaswani

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.

Details

Publication typeInproceedings
Published inInternational Symposium on Distributed Computing (DISC)
> Publications > Asynchronous Resilient Linearizability