Fail-Aware Untrusted Storage
Authors:
- Christian CachinCCChristian Cachin
- Idit KeidarIKIdit Keidar
- Alexander ShraerASAlexander Shraer
- 1 January 2011
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 40 (2) , 493-533
Abstract
We consider a set of clients collaborating through an online service provider that is subject to attacks and hence not fully trusted by the clients. We introduce the abstraction of a fail-aware untrusted service, with meaningful semantics even when the provider is faulty. In the common case, when the provider is correct, such a service guarantees consistency (linearizability) and liveness (wait-freedom) of all operations. In addition, the service always provides accurate and complete consistency and failure detection. We illustrate our new abstraction by presenting a Fail-Aware Untrusted STorage service (FAUST). Existing storage protocols in this model guarantee so-called forking semantics. We observe, however, that none of the previously suggested protocols suffices for implementing fail-aware untrusted storage with the desired liveness and consistency properties (at least wait-freedom and linearizability when the server is correct). We present a new storage protocol, which does not suffer from this limitation, and implements a new consistency notion, called weak fork-linearizability. We show how to extend this protocol to provide eventual consistency and failure awareness in FAUST.Keywords
This publication has 23 references indexed in Scilit:
- Fork sequential consistency is blockingInformation Processing Letters, 2009
- Optimal propagation-based protocols implementing causal memoriesDistributed Computing, 2006
- Optimistic replicationACM Computing Surveys, 2005
- Group communication specificationsACM Computing Surveys, 2001
- The timed asynchronous distributed system modelIEEE Transactions on Parallel and Distributed Systems, 1999
- Disconnected operation in the Coda File SystemACM Transactions on Computer Systems, 1992
- Wait-free synchronizationACM Transactions on Programming Languages and Systems, 1991
- Linearizability: a correctness condition for concurrent objectsACM Transactions on Programming Languages and Systems, 1990
- Reliable communication in the presence of failuresACM Transactions on Computer Systems, 1987
- Time, clocks, and the ordering of events in a distributed systemCommunications of the ACM, 1978