  A group of mutually trusting clients outsources a computation service to a
remote server, which they do not fully trust and that may be subject to
attacks. The clients do not communicate with each other and would like to
verify the correctness of the remote computation and the consistency of the
server's responses. This paper presents the Conflict-free Operation
verification Protocol (COP) that ensures linearizability when the server is
correct and preserves fork-linearizability in any other case. All clients that
observe each other's operations are consistent, in the sense that their own
operations and those operations of other clients that they see are
linearizable. If the server forks two clients by hiding an operation, these
clients never again see operations of each other. COP supports wait-free client
operations in the sense that when executed with a correct server,
non-conflicting operations can run without waiting for other clients, allowing
more parallelism than earlier protocols. A conflict arises when an operation
causes a subsequent operation to produce a different output value for the
client who runs it. The paper gives a precise model for the guarantees of COP
and includes a formal analysis that these are achieved.
