  Recent years have seen significant interest in designing networks that are
self-healing in the sense that they can automatically recover from adversarial
attacks. Previous work shows that it is possible for a network to automatically
recover, even when an adversary repeatedly deletes nodes in the network.
However, there have not yet been any algorithms that self-heal in the case
where an adversary takes over nodes in the network. In this paper, we address
this gap. In particular, we describe a communication network over n nodes that
ensures the following properties, even when an adversary controls up to t <=
(1/8 - \epsilon)n nodes, for any non-negative \epsilon. First, the network
provides a point-to-point communication with bandwidth and latency costs that
are asymptotically optimal. Second, the expected total number of message
corruptions is O(t(log* n)^2) before the adversarially controlled nodes are
effectively quarantined so that they cause no more corruptions. Empirical
results show that our algorithm can reduce the bandwidth cost by up to a factor
of 70.
