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.

Advertisements

4 Comments so far
Leave a comment

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.

Comment by George Saad

Nice direction and good work, Jared, Jeffrey and George .. seems promising 🙂

Comment by amitabht

This sounds like really interesting work, definitely on my list of papers to read.
-Max

Comment by Max

thanks max, amitabh and george. we’re currently trying to extend the ideas to distributed *computation*, which I think will be cool.

Comment by Jared




Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s



%d bloggers like this: