Monday, February 25, 2002
11:00 AM
CSB 209
Gopal Pandurangan
Brown University
Stochastic Analysis of Dynamic Computer Processes
Stochastic processes can model a variety of dynamic computer phenomena such as growth of the World Wide Web, traffic in communication networks, structure of dynamic networks, and input for caching and load balancing. Stochastic analysis enables us to characterize properties of such processes that dynamically change with time.

In this talk, I will present two results in different settings in which stochastic processes serve as natural models for dynamic computer phenomena. The models are useful not only in understanding these phenomena but also in designing practical algorithms/schemes for the associated algorithmic problems. The two results are:

(1) Stochastic Analysis of Peer-to-Peer (P2P) Networks : I will first motivate the problem of building connected low-diameter P2P networks. Then I will present a simple distributed protocol for building P2P networks and prove (under a reasonable stochastic model) that it results in connected networks of constant degree and logarithmic diameter. An important feature of our protocol is that it operates without any global knowledge of all the nodes in the network. To our knowledge, this is the first such protocol with provable guarantees on connectivity and diameter.

(2) Stochastic Analysis of Online Computation: In the second part of the talk, I will discuss a novel way of measuring online performance based on the characteristics of the input sequence; this is fundamentally different from the traditional competitive analysis of online computation. Assuming a very general stochastic model for the input sequence, I will present bounds between entropy of the input and the performance of the best online algorithm for various online problems. In particular, I will present a simple online algorithm for prefetching and show that it performs well on any input sequence. I will also mention a few practical applications of our approach.