  We study how to efficiently diffuse updates to a large distributed system of
data replicas, some of which may exhibit arbitrary (Byzantine) failures. We
assume that strictly fewer than $t$ replicas fail, and that each update is
initially received by at least $t$ correct replicas. The goal is to diffuse
each update to all correct replicas while ensuring that correct replicas accept
no updates generated spuriously by faulty replicas. To achieve reliable
diffusion, each correct replica accepts an update only after receiving it from
at least $t$ others. We provide the first analysis of epidemic-style protocols
for such environments. This analysis is fundamentally different from known
analyses for the benign case due to our treatment of fully Byzantine
failures---which, among other things, precludes the use of digital signatures
for authenticating forwarded updates. We propose two epidemic-style diffusion
algorithms and two measures that characterize the efficiency of diffusion
algorithms in general. We characterize both of our algorithms according to
these measures, and also prove lower bounds with regards to these measures that
show that our algorithms are close to optimal.
