Christian Cachin,

IBM Research – Zurich


Fail-aware untrusted storage (FAUST)

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 suffice 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.

Joint work with Alexander Shraer and Idit Keidar.


Date: 2010-Mar-03     Time: 15:00:00     Room: 336

For more information: