Data replication is a widely used technique for achieving fault
tolerance and improved performance. With the advent of content
delivery networks, it is becoming more and more frequent that
data content is placed on hosts that are not directly controlled
by the content owner, and because of this, security mechanisms to
protect data integrity are necessary. In this paper we present a
system architecture that allows arbitrary queries to be supported
on data content replicated on untrusted servers. To prevent these
servers from returning erroneous answers to client queries, we
make use of a small number of trusted hosts that randomly check
these answers and take corrective action whenever
necessary. Additionally, our system employs an audit mechanism
that guarantees that any untrusted server acting maliciously will
eventually be detected and excluded from the system.
