Restart-Rollback: A Fault model for distributed systems with persistent state

Baltasar Azevedo e Silva Dinis

Key information

Authors:

Baltasar Azevedo e Silva Dinis (Baltasar Azevedo e Silva Dinis)

Supervisors:

Rodrigo Seromenho Miragaia Rodrigues (Rodrigo Seromenho Miragaia Rodrigues); Peter Druschel

Published in

November 25, 2022

Abstract

TEEs ensure the confidentiality and integrity of computations in hardware. Subject to the TEE’s threat model, the hardware shields computation from most externally induced faults except crashes. As a result, CFT replication protocols should be sufficient when replicating TEEs. However, TEEs do not offer efficient means of ensuring the freshness of persistent state, which can be rolled back to an earlier version. In this dissertation, we propose the Restart-Rollback (RR) fault model for replicating TEEs, which precisely captures the possible fault behaviors of TEEs with external state, making it possible to avoid using expensive BFT protocols. Then, we show that existing CFT replication protocols can be easily adapted to this fault model with few changes, while retaining their original performance. To illustrate the usefulness of TEE replication under RR, we built a replicated metadata service called TEEMS, which can be used to add TEE-grade confidentiality, integrity, and freshness to untrusted cloud storage. Then, we showcase the generality of the RR model, by applying it to the context of replicated KVSs. Current replicated KVSs make a tradeoff between latency, throughput and durability, depending on whether they flush writes before replying (which offers poor performance) or batch writes in memory (possibly losing data if nodes crash before flushing). We observe that the latter case effectively constitutes a rollback, which is captured by RR. We implemented the various protocols and systems, and our evaluation shows performance that is comparable to CFT systems but with stronger guarantees, and significantly better than BFT systems.