Verifying the Consistency of Remote Untrusted Services with Commutative Operations

摘要: A group of mutually trusting clients outsources a computation service to remote server, which they do not fully trust and that may be subject attacks. The communicate with each other would like verify the correctness consistency server’s responses. This paper first presents Commutative-Operation verification Protocol (COP) ensures linearizability when server is correct preserves fork-linearizability in any case. All observe other’s operations are consistent, sense their own those see linearizable. Second, this work extends COP through authenticated data structures Authenticated , allows outsourced services whose state kept only remotely, by server. yields fork-linearizable protocol for generic (1) relieves from storing state, (2) supports wait-free client operations, (3) handles sequences arbitrary commutative operations.