home · mobile · calendar · colloquia · 2009-2010 · 

Colloquium - Bunn

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

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.

Department of Computer Science
University of Colorado Boulder
Boulder, CO 80309-0430 USA
May 5, 2012 (14:13)