skip to main content
Department of Computer Science University of Colorado Boulder
cu: home | engineering | mycuinfo | about | cu a-z | search cu | contact cu cs: about | calendar | directory | catalog | schedules | mobile | contact cs
home · events · colloquia · 2009-2010 · 

Colloquium - Bunn

ECCR 265

Optimal-Rate Routing in Adversarial Networks
Paul Bunn
University of California, Los Angeles
Paul Bunn photo

Our work seeks to optimize communication flow through a dynamic network in which some of the nodes can be corrupted by a malicious adversary. In networking literature, extensive work has been done to find optimal routing protocols that work in networks whose links are unreliable, modeled by a graph with dynamic topology. In a separate line of research, "Fault Detection" and "Fault Localization" study networks in which the nodes themselves are unreliable, and seek to develop protocols that are robust against nodes maliciously deviating from the proscribed protocol. Work in this area to-date has focused on End-to-End communication via a single (fixed) path between the sender and receiver, and the added protection against misbehaving nodes has come at the cost of a reduction in communication efficiency in transferring packets from the sender to the receiver.

We show how to construct a protocol that guarantees success in a network setting that simultaneously allows for unreliable edges (dynamic topology) and unreliable nodes. We model the unreliability by introducing a malicious adversary that controls the edges and corrupt nodes, and is limited only by the restriction that he always leave a path connecting the sender and receiver through un-corrupted nodes. Our work is the first to protocol that protects simultaneously against both forms of unreliability (edges and nodes), and surprisingly, we achieve the extra robustness at no additional cost: our protocol is as throughput-efficient as any protocol that works only in an honest setting (where nodes are not allowed to misbehave).

Paul Bunn is a sixth-year graduate student in the math department at the University of California, Los Angeles. His research focuses on problems in number theory and theoretical computer science, including cryptography and network and distributed algorithms. He was awarded with a NSF VIGRE research fellowship in 2007 and again in 2008, he was a core participant in the "Securing Cyberspace" program hosted by the Institute for Pure and Applied Mathematics in 2006, and is an active member of the Cryptography research group and Number Theory group at UCLA. Bunn graduated with distinction from Duke University in 2001 with a double-major in Physics and Computer Science.

Joint work with Yair Amir and Rafail Ostrovsky.

Hosted by John Black.

The Department holds colloquia throughout the Fall and Spring semesters. These colloquia, open to the public, are typically held on Thursday afternoons, but sometimes occur at other times as well. If you would like to receive email notification of upcoming colloquia, subscribe to our Colloquia Mailing List. If you would like to schedule a colloquium, see Colloquium Scheduling.

Sign language interpreters are available upon request. Please contact Stephanie Morris at least five days prior to the colloquium.

See also:
Department of Computer Science
College of Engineering and Applied Science
University of Colorado Boulder
Boulder, CO 80309-0430 USA
Send email to

Engineering Center Office Tower
ECOT 717
FAX +1-303-492-2844
XHTML 1.0/CSS2 ©2012 Regents of the University of Colorado
Privacy · Legal · Trademarks
May 5, 2012 (13:29)