# Machinations

Self-healing of Byzantine Faults
May 21, 2012, 7:41 pm
Filed under: Uncategorized | Tags: , ,

“You have to have good researchers. Good researchers, all of them.” – Paraphrase of quote from Das Boot.

Sometimes writing a paper can be a challenging slog: goals move as conjectures prove wrong; facts that seem simple turn out to be slippery to prove; experiments must be rerun as the paper evolves; and notation needs to be redone for the sake or readability.

In such a situation, it’s a blessing to have coauthors who will go the extra mile to keep pushing and pushing the paper to completion.  So I would now really like to thank my students Jeffrey Knockel and George Saad for their hard work on our latest paper: “Self-Healing of Byzantine Faults” (abstract below, full paper here).

Note: I wouldn’t exactly compare the research process with serving on a U-boat mission during the decline of the Third Reich.  For me it’s most similar to mountaineering, whose ethos is captured by the motto of the Seattle mountaineers: “Like fun, only different!”

Paper Abstract:

Recent years have seen significant interest in designing networks that are self-healing in the sense that they can automatically recover from adversarial attack. 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 \leq (1/4-\epsilon)n$ nodes, for any positive $\epsilon$. First, the network provides point-to-point communication with bandwidth and latency costs that are asymptotically optimal. Second, $O(t (log*n)^2)$ message corruptions occur in expectation, before the adversarially controlled nodes are effectively quarantined so that they cause no more corruptions. We present empirical results showing that our approach may be practical.

Special thanks to Prof. Jared for giving me an opportunity to work on the paper “Self-Healing of Byzantine Faults”. This is an exceptional experience for me in the research field.