Fail-Aware Untrusted Storage

This paper considers a set of clients collaborating through an online service provider that is subject to attacks, and hence not fully trusted by the clients. The paper introduces 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. The illustrates the new abstraction by presenting a Fail-Aware Untrusted STorage service (FAUST). Existing storage protocols in this model guarantee so-called forking semantics.