Title: Randomized Algorithms for Reliable Broadcast
Speaker: Vinod Vaikuntanathan (IBM Watson Research Center)
Place: 32-G531
Time:   1-2:30pm
Date:   Friday March 20th, 2009

Abstract:

A reliable broadcast channel is a mechanism to transmit messages where the
recipients are *guaranteed* that everyone received the same message. Although
very useful, traditional networks such as point-to-point networks and wireless
and radio networks do not provide such a guarantee by themselves. Thus, we
would like to design protocols that simulate the functionality of a reliable
broadcast channel over traditional networks: this is the reliable
broadcast problem.


A landmark result of Fischer and Lynch showed that deterministic algorithms for
reliable broadcast tolerating t faulty players require at least t+1 rounds.
In this talk, I will show an efficient randomized algorithm for
reliable broadcast
over point-to-point networks, in the synchronous full-information model. The
full-information model is a strong adversarial model, which imposes no
restrictions on the computational power of the faulty players nor on
the information
available to them. Namely, there are *no private channels* and the faulty
players are infinitely powerful and are privy to all communication in
the network.

We construct reliable broadcast protocols among $n$ participants, where
any $t < (1/3-\epsilon)n$ are corrupted by a full-information adversary.
The protocols have an expected complexity of $O(\log n)$ rounds, which
is an exponential improvement over the best previous protocol in the
full-information model that had an almost-linear round-complexity.

Bio: Vinod Vaikuntanathan is a postdoctoral fellow in the cryptography group
at the IBM T.J. Watson Research Center, where he is a recipient of the
Joseph Raviv postdoctoral fellowship. He obtained his Ph.D from MIT in
2008, under the supervision of Shafi Goldwasser.