Self-healing of Byzantine faults

Abstract. 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. How-ever, 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 − )n nodes, for any non-negative . First, the network provides a point-to-point com-munication with bandwidth and latency costs that are asymptotically optimal. Second, the expected total number of message corruptions is O(t(log ∗ n)2) be-fore the adversarially controlled nodes are effectively quarantined so that they cause no more corruptions. Empirical results show that our algorithm can reduce bandwidth cost by up to a factor of 70