University of Minnesota
University Relations
myU OneStop

Go to unit's home.

Home | Seminars and Symposia | Past seminars/symposia: Wednesday, November 26, 2003

DTC Seminar Series

Fundamental Lower Bound and Tradeoff Problems in Networking


Jun (Jim) Xu
College of Computing
Georgia Institute of Technology

Wednesday, November 26, 2003
1:00 pm

402 Walter Library

Jun (Jim) Xu

Download slides (pdf 448 KB) Lower bound, fundamental tradeoff, and impossibility results are the deepest and most fundamental results in many fields of computer science. Such results are important since they typically end the vigorous search for a better algorithm that does not exist at all, or lead to provably optimal algorithms. In this talk, Professor Xu will focus on his past and current work on the following lower bound and tradeoff results in computer networks:

  1. Delay bound vs. computational complexity: It has been widely believed as a "folklore theorem" that scheduling algorithms which can provide tight end-to-end delay bounds require Omega (log_2 n) complexity, typically used for maintaining a priority queue. However, this has never been carefully formulated and proved. We rigorously define this tradeoff problem and establish some foundational results. Our recent work explores further along this line, and answers a "sister question" to this delay-complexity tradeoff.
  2. Routing table size vs. network diameter: Distributed hash table (DHT) schemes have been proposed to support scalable object search and retrieval in a peer-to-peer (P2P) file-sharing system. Existing DHT schemes either have a routing table of size O(log_2 n) and network diameter of O(log_2 n), or have a routing table of size d and network diameter of O(n^{1/d}), including. It was posed as an open problem whether this represents the best asymptotic "state-efficiency" tradeoffs. We clarified this question and established some foundational results. This work leads to our recent work named Ulysses, a DHT scheme that achieves the desired optimal "state-efficiency" tradeoff.
Xu presenting


Jun (Jim) Xu is an Assistant Professor in the College of Computing at Georgia Institute of Technology. He received his B.S. in Computer Science from Illinois Institute of Technology in 1995 and a Ph.D. in Computer and Information Science from The Ohio State University in 2000. His current research interests include data streaming algorithms for networking, discrete algorithms for networking, network security, theoretical computer science applied to computer networks, and performance modeling and simulation. He received the NSF CAREER award in 2003 for his ongoing efforts in establishing fundamental lower bound and tradeoff results in networking.